このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1276810079/5
#  次の問題を解くプログラムを再帰を使って実装せよ。 
#  問題 コインの種類として、1,5,8,10,15の5種類を与える。
#  に対して、最小枚数のコインでmを支払うときの枚数を求めよ。 
# 

金種([15,10,8,5,1]).

'与えられた金額に対して、最小枚数のコインでmを支払うときの枚数を求める'(_m,_最小コイン枚数) :-
        金種(_金種ならび),
        sort(_金種ならび,_整列された金種ならび),
        reverse(_整列された金種ならび,_大きい順の金種ならび),
        最小コイン枚数(_大きい順の金種ならび,_m,_最小コイン枚数).

最小コイン枚数([],X,X) :- !.
最小コイン枚数([N|R],U,X) :-
        M is U mod N,
        Y is U // N,
        U2 is U + M,
        最小コイン枚数(R,U2,M,Y,X).

最小コイン枚数(R,U,M,Y,X) :- M =< 2,X is Y + M,!.
最小コイン枚数(R,U,M,Y,X) :- M  >= 5,最小コイン枚数(R,M,Z),X is Y + Z,!.
最小コイン枚数(R,U,M,Y,4) :- M  >= 3,M =< 4,U2 is U + M,最小コイン枚数(R,U2,Z),X is Z + Y - 1,!.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

'与えられた金額に対して、最小枚数のコインでmを支払うときの枚数を求めよ。'(_m,_最小コイン枚数) :-
        暫定候補枚数を得る(_m,[15,10,8,5,1],0,_暫定候補枚数),
        最小枚数のコインでmを支払うときの枚数(_暫定候補枚数,_最小コイン枚数).

暫定候補枚数を得る(0,_,X,X) :- !.
暫定候補枚数を得る(_m,[P|R1],S1,X) :-
        D is _m // P,
        _m_2 is _m mod P,
        S2 is S + D,
        暫定候補枚数を得る(_m_2,S2,X).

最小枚数のコインでmを支払うときの枚数(_m,_暫定候補枚数,_最小コイン枚数) :-
        findmin(_枚数,暫定候補枚数より少ない支払いを探す(_m,_暫定候補枚数,_枚数),_最小コイン枚数),!.

暫定候補枚数より少ない支払いを探す(_m,_暫定候補枚数,_枚数) :-
        for(0,A,_暫定候補枚数),
        for(0,B,_暫定候補枚数),
        for(0,C,_暫定候補枚数),
        for(0,D,_暫定候補枚数),
        for(0,E,_暫定候補枚数),
        _m is 1 * A + 5 * B + 8 * C + 10 * D + 15 * E,
        _枚数 A + B + C + D + e,
        _枚数 =< _暫定候補枚数.