Concurso/Encontro Nacional de Programação em Lógica

CeNPL'03

Universidade de Évora

9-11 Maio de 2003

Divisões

O Problema

Como estão certamente fartos de saber, os números racionais são aqueles que se podem obter a partir da divisão de dois números inteiros. Quando passado para a forma decimal, um número racional nem sempre pode ser representado com um número finito de casas decimais. Por exemplo: 1/3 = 0.33333... Mas, para os números racionais, essa sequência (mesmo que infinita) de casas decimais não pode ser qualquer: a partir de certa altura há sempre uma sequência de algarismos que se repete indefinidamente. Por isso mesmo, até é usual representar esses números na forma decimal com a dita sequência no fim e entre parêntesis.

Por exemplo:

1/3 = 0.(3)        8/15 = 0.5(3)        1/7 = 0.(142857)        10/7  = 1.(428571)
 

Tarefa

Escrever um predicado Prolog que, dados dois números inteiros positivos n e m, calcule a sequência de algarismos que se repete indefinidamente na representação decimal do número racional n/m.

 

Os Resultados

Deverá implementar o predicado ciclo(N,M,C) que, quando chamado com N e M instanciados com números inteiros positivos, devolve em C uma lista com a sequência de algarismos que se repete indefinidamente na representação decimal de N/M.

Se N/M se conseguir representar com um número finito de casas decimais, então em C deve ser devolvido [0].
Note que, em rigor, essa é uma sequência que se repete indefinidamente: por exemplo, 1/4 = 0.25(0).

No caso de haverem várias sequências possíveis (por exemplo 1/11 = 0.(09) = 0.0(90)), o seu predicado deverá
devolver apenas uma delas. E, já agora, que seja aquela que dá origem a uma representação mais curta do número (o 0.(09) é mais
curto que o 0.0(90), pelo que deverá ser devolvido [0,9] e não [9,0]).

Exemplo de uso do predicado:

| ?- ciclo(1,3,C).
C = [3];
no
| ?- ciclo(8,15,C).
C = [3];
no
| ?- ciclo(1,7,C).
C = [1,4,2,8,5,7];
no
| ?- ciclo(10,7,C).
C = [4,2,8,5,7,1];
no
| ?- ciclo(1,11,C).
C = [0,9];
no
| ?- ciclo(1,4,C).
C = [0];
no
| ?- ciclo(7,7,C).
C = [0];
no