Concurso/Encontro Nacional de Programação em Lógica
CeNPL'03
Universidade de Évora
9-11 Maio de 2003
Divisões
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)
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.
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