/*===========================================================================*/
/* 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 a partir de um determinado valor (S) combinando as */ /* moedas de 0,50 0,25 0,10 0,05 e 0,01 centavos de dólar.				 */
/*============================================================================*/

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 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                      */