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