このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1268699491/881
# アルゴリズムのヒントを教えてもらえませんか。Cの実装は自分でやります。
# ネタ元は↓の課題２です。
# ttp://cdn.cs50.net/2009/fall/psets/1/hacker1.pdf
#
# レジに入ってる小銭の枚数（25セント、10セント、５セント、１セント）と、
# お釣りの額を入力して、釣り銭の枚数が最少となる枚数を表示する。
# 釣り銭切れも考慮する。支払い不能な時は０を返す。
#
# 例えば、硬貨がそれぞれ10枚、10枚、0枚、10枚あって、41セントのお釣りの時、
# 枚数が最少となるのは10セント×４枚＋1セントとなって５枚が正解。
# 単純なgreedy algorithmだと最初に25セントを使うので、
# 残り16セントを支払うのに10セント＋１セント×６枚となって計８枚になってしまう。
#
'レジに入ってる小銭の枚数（25セント、10セント、５セント、１セント）と、お釣りの額を入力して、釣り銭の枚数が最少となる枚数を表示する。'(_25セント枚数,_10セント枚数,_5セント枚数,_1セント枚数,_お釣り,_最少枚数) :-
findmin(_枚数,(
for(0,A,_25セント枚数),
for(0,B,_10セント枚数),
for(0,C,_5セント枚数),
for(0,D,_1セント枚数),
_お釣り is 25 * A + 10 * B + 5 * C + 1 * D,
_枚数 is A + B + C + D),
_最少枚数),!.
'レジに入ってる小銭の枚数（25セント、10セント、５セント、１セント）と、お釣りの額を入力して、釣り銭の枚数が最少となる枚数を表示する。'(_,_,_,_,_,0) :- '釣り銭切れも考慮する。支払い不能な時は０を返す'.
'釣り銭切れも考慮する。支払い不能な時は０を返す'.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'レジに入ってる小銭の枚数（25セント、10セント、５セント、１セント）と、お釣りの額を入力して、釣り銭の枚数が最少となる枚数を表示する。'(_25セント枚数,_10セント枚数,_5セント枚数,_1セント枚数,_お釣り,_最少枚数) :-
_25セント枚数_1 is _お釣り // _25セント枚数,
少ない方は(_25セント,_25セント_1,_25セント_2),
_10セント枚数_1 is _お釣り // _10セント枚数,
少ない方は(_10セント,_10セント_1,_10セント_2),
_5セント枚数_1 is _お釣り // _5セント枚数,
少ない方は(_5セント,_5セント_1,_5セント_2),
findmin(_枚数,(
for(0,A,_25セント枚数_2),
for(0,B,_10セント枚数_2),
for(0,C,_5セント枚数_2),
E is 25 * A + 10 * B + 5 * C,
D is _お釣り - E,
_枚数 is A + B + C + D),
_最少枚数),!.
'レジに入ってる小銭の枚数（25セント、10セント、５セント、１セント）と、お釣りの額を入力して、釣り銭の枚数が最少となる枚数を表示する。'(_,_,_,_,_,0) :- '釣り銭切れも考慮する。支払い不能な時は０を返す'.
'釣り銭切れも考慮する。支払い不能な時は０を返す'.
少ない方は(M,N,M) :- M =< N,!.
少ない方は(M,N,N) :- M > N,!.