/*========================================================================================*/
/* Autor	: Wanderley Gazeta - ICMC - USP/SC						  */
/* data 	: 08/04/99									  */
/* disciplina	: Introdução à Inteligência Artificial
/*========================================================================================*/
/* programa para a solução do problema do troco de um dólar. Este programa retorna todas  */
/* possibilidades de troco combinando as moedas de 0,50 0,25 0,10 0,05 e 0,01 centavos de */
/* dólar.										  */
/*========================================================================================*/ 

troco(L):-
  troco(L, [50, 25, 10, 5, 1], [2, 4, 10, 20, 100], 0, 100).

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 e*/
   Subt2 is N*V + Subt,		    /* calcula a quantidade necessária de cada moeda       */
   troco(Ns, Vs, Maxs, Subt2, Tot). /* chama a recursão                                    */

entre(_,Min,Max):- Min > Max,       /* quando o mínimo > máximo, 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) :- 
    ProxMin is Min+1,
    entre(N, ProxMin, Max).         /* chama a recursão                                    */