Resolução
do Problema
do
Troco de
Um Dólar
Wanderley Gazeta
São
Carlos, 08 de abril de 1999.
Half-dólar | US$ 0,50 |
Quarter | US$ 0,25 |
Dime | US$ 0,10 |
Nickel | US$ 0,05 |
Peniie | US$ 0,01 |
[ H , Q , D , N , P ]
em que H, Q, D, N e P representam, na respectiva posição, a quantidade necessária de moedas, que multiplicada pelo valor correspondente, gera o valor necessário daquela moeda para compor o resultado final. Esse valor final sempre será equivalente a 100 (1 dólar). Por exemplo, a primeira solução apresentada para uma chamada troco(X) é a seguinte:
[ 0 , 0 , 0 , 0 , 100 ]
Nesse caso, todas as posições estão zeradas, com exceção da última posição, que corresponde ao pennie, informando que, para essa solução apresentada, são necessários 100 pennies, totalizando 1 dólar. Depois seguem-se as outras soluções (ver exemplos de execução do programa).
[ H , Q , D , N , P ]
Nessa lista H, Q, D, N e P representam, na respectiva posição, a quantidade necessária de moedas, que multiplicada pelo valor correspondente à posição, gera o valor necessário de cada moeda, cuja somatória representa o valor do troco. Por exemplo, a partir da execução do comando troco(X,91) o programa irá listar todas as possibilidades de troco que somem US$ 0,09, o que resultaria em apenas duas soluções:
[ 0 , 0 , 0 , 0 , 9 ] (9 pennies)
[ 0 , 0 , 0 , 1 , 4 ] (1 nickel e 4 pennies)
São bastante genéricos considerando que basta alterar o número e o valor dos componentes para que sejam utilizados para outras moedas e valores. Também pode ser parametrizada a entrada de um valor para permitir o cálculo para valores diferentes de um dólar.
Para este caso existem mais de duzentas listas retornadas. Aqui foram apresentados alguns recortes desta solução.
?- consult(dolar1).
yes
?- troco(X).
X = [0,0,0,0,100] ;
X = [0,0,0,1,95] ;
X = [0,0,0,2,90] ;
X = [0,0,0,3,85] ;
X = [0,0,0,4,80] ;
X = [0,0,0,5,75] ;
X = [0,0,0,6,70] ;
X = [0,0,0,7,65] ;
....
X = [0,0,0,20,0] ;
X = [0,0,1,0,90] ;
X = [0,0,1,1,85] ;
X = [0,0,1,2,80] ;
X = [0,0,1,3,75] ;
X = [0,0,1,4,70] ;
X = [0,0,1,5,65] ;
X = [0,0,1,6,60] ;
X = [0,0,1,7,55] ;
X = [0,0,1,8,50] ;
X = [0,0,1,9,45] ;
...
X = [0,0,9,1,5] ;
X = [0,0,9,2,0] ;
X = [0,0,10,0,0] ;
X = [0,1,0,0,75] ;
X = [0,1,0,1,70] ;
X = [0,1,0,2,65] ;
X = [0,1,0,3,60] ;
X = [0,1,0,4,55] ;
X = [0,1,0,5,50] ;
X = [0,1,0,6,45] ;
X = [0,1,0,7,40] ;
...
X = [1,1,0,4,5] ;
X = [1,1,0,5,0] ;
X = [1,1,1,0,15] ;
X = [1,1,1,1,10] ;
X = [1,1,1,2,5] ;
X = [1,1,1,3,0] ;
X = [1,1,2,0,5] ;
X = [1,1,2,1,0] ;
X = [1,2,0,0,0] ;
X = [2,0,0,0,0] .
yes
?-
Exemplo de execução do programa dolar.pro com para listar as possibilidades de troco para 1 dolar mediante uma despesa de 0,91:
?- consult(dolar2).
yes
?- troco(A,91).
A = [0,0,0,0,9] ; (9 pennies)
A = [0,0,0,1,4] ; (1 nickel e 9 pennies)
no
?-
Exemplo de execução do programa dolar.pro com para listar as possibilidades de troco para 1 dolar mediante uma despesa de 0,78:
?-
?- troco(A,78).
A = [0,0,0,0,22] ;
A = [0,0,0,1,17] ;
A = [0,0,0,2,12] ;
A = [0,0,0,3,7] ;
A = [0,0,0,4,2] ;
A = [0,0,1,0,12] ;
A = [0,0,1,1,7] ;
A = [0,0,1,2,2] ;
A = [0,0,2,0,2] ;
no
?-
dolar1.pro
dolar2.pro
dolar2.pro
troco(L,S):-
C is 100-S,
troco(L, [50, 25, 10, 5, 1], [C/50, C/25, C/10, C/5, C/1], 0, C).
troco([], [], [], R, R).
troco([N|Ns], [V|Vs], [Max|Maxs], Subt,Tot):-
entre(N, 0, Max),
/* procura todos os valores possíveis para cada moeda */
Subt2 is N*V + Subt,
/* calcula a qtde necessária de cada moeda */
troco(Ns, Vs, Maxs, Subt2, Tot). /* chama a recursão
*/
entre(_,Min,Max):- Min > Max, /* qdo
o mín > máx, não há necessidade */
!,
/* de continuar com as comparações */
fail.
entre(Min,Min,_).
/* transfere o valor de Min para N */
entre(N, Min, Max) :-
/* incrementa o Min */
ProxMin is Min+1,
entre(N, ProxMin, Max).
/* chama a recursão */