「プロジェクトオイラー問３１」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問３１」(2014/02/14 (金) 12:21:27) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031
Problem 31 「硬貨の和」 †
イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?
解法
初めてこの問題にPrologで挑戦した時は破壊的代入も配列もstd::mapもないPrologでどうやって動的計画法をするか悩みました。
基本がわかれば考え方は簡単。
1ペンスで作れる組み合わせを全部計算し、[金額、組み合わせ数]を基本に
[0,1],[1,1][2,1],,[200,1]
と集合を作ります。
この集合に今度は２ペンスを0～200個まで足した場合の集合で金額が200以下になるものをを新しく作ります。
この集合をソートして同じ金額のものを集計していけば1と２を使った組み合わせが出ます。
以下これの繰り返しです。
calc(Vs,Coin,[NV,Count]):-
member([V,Count],Vs),
between(0,200,C),
NV is V+C*Coin,
(NV=<200).
union_sum([],V,[V]):-!.
union_sum([[V,Count1]|Vs],[V,Count2],Result):-
!,
Count3 is Count1+Count2,
union_sum(Vs,[V,Count3],Result).
union_sum([V|Vs],V1,[V1|Result]):-
union_sum(Vs,V,Result).
next_calc([],Vs,Ans):-
!,
member([200,Ans],Vs).
next_calc([Coin|Coins],Vs,Ans):-
findall(NV,calc(Vs,Coin,NV),NVs),
msort(NVs,NVs1),
[Top|NVs2]=NVs1,
union_sum(NVs2,Top,NVs3),
next_calc(Coins,NVs3,Ans).
main31:-
next_calc([1,2,5,10,20,50,100,200],[[0,1]],Ans),
write(Ans).
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031
Problem 31 「硬貨の和」 †
イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?
解法
初めてこの問題にPrologで挑戦した時は破壊的代入も配列もstd::mapもないPrologでどうやって動的計画法をするか悩みました。
基本がわかれば考え方は簡単。
1ペンスで作れる組み合わせを全部計算し、[金額、組み合わせ数]を基本に
[0,1],[1,1][2,1],,[200,1]
と集合を作ります。
この集合に今度は２ペンスを0～200個まで足した場合の集合で金額が200までになるものだけを取り出して新しく集合を作ります。
この集合をソートして同じ金額のものを集計していけば1と２を使った組み合わせが出ます。
以下これの繰り返しです。
calc(Vs,Coin,[NV,Count]):-
member([V,Count],Vs),
between(0,200,C),
NV is V+C*Coin,
(NV=<200).
union_sum([],V,[V]):-!.
union_sum([[V,Count1]|Vs],[V,Count2],Result):-
!,
Count3 is Count1+Count2,
union_sum(Vs,[V,Count3],Result).
union_sum([V|Vs],V1,[V1|Result]):-
union_sum(Vs,V,Result).
next_calc([],Vs,Ans):-
!,
member([200,Ans],Vs).
next_calc([Coin|Coins],Vs,Ans):-
findall(NV,calc(Vs,Coin,NV),NVs),
msort(NVs,NVs1),
[Top|NVs2]=NVs1,
union_sum(NVs2,Top,NVs3),
next_calc(Coins,NVs3,Ans).
main31:-
next_calc([1,2,5,10,20,50,100,200],[[0,1]],Ans),
write(Ans).
