Project Euler - Probrem 31

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　ProjectEuler.net（英語サイト）

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を作る方法は何通りあるか?
－－－－－


私の解答例は以下です。畳んでいます。

def f(n, L, i=0):
	cnt, imax = 0, len(L)-1
	for s in xrange(0, n+1, L[i]):
		t = n-s
		if t<0: break
		if i<imax: cnt += f(t, L, i+1)
		if i==imax and t==0: cnt += 1
	return cnt
	
L = [1, 2, 5, 10, 20, 50, 100, 200]
print f(200, sorted(L, reverse=True))

１．関数f(n, L, i)
・nペンスをリストLの硬貨（単位:ペンス）で作る方法が何通りあるかを返します。
　iは試行する硬貨がリストLの何番目かというインデックス値です。
・関数fは、自分で自分自身を呼び出すという再帰呼び出しをしますので、
　どの硬貨で試行するかというインデックス値をiとします。初期値は0です。
・Lは大きい順に並べておきます。
　大きい順に硬貨を当てはめていった方が少ない試行回数で済むからです。

・cnt, imax = 0, len(L)-1
　初期値です。通り数カウンターcntは0クリアしておきます。
硬貨リストのインデックス値iの最大値imaxは硬貨リストの要素数-1です。

・for s in xrange(0, n+1, L[i]):
　ループ変数sは、0からnの範囲で試行する硬貨金額刻みの値です。
　つまり、試行する硬貨を0枚から順に増やしたときのその硬貨での金額です。
　例えば、100ペンスならば、0,100,200・・・と変化します。

・t = n-s
　対象金額nから使用硬貨による金額を差し引き、余りをtとしています。
　つまり、tはまだこの時点では割り当て切れていない余り金額です。

・if t<0: break
　余り金額tが0より小さい場合、現時点での割り当て枚数での金額では
　もう大きすぎてダメなので、ループ変数sのループを終了します。

・if i<imax: cnt += f(t, L, i+1)
　硬貨リストのインデックス値iがその最大値imaxよりも小さい場合は、
　余り金額tを１つ小さい金額の硬貨（i+1番目の硬貨）で割り当ててできる通り数を
　求めて、件数カウンタに累積します。
　このときの１つ小さい金額の硬貨の場合を当関数を再帰呼び出しして求めます。

・if i==imax and t==0: cnt += 1
　硬貨リストの最後まで検討した結果、余り金額が0ならば、現在の割り当てで
　元の金額がくずせたわけなので、件数カウンタを当パターン分として+1します。

２．関数の外側
・L = [1, 2, 5, 10, 20, 50, 100, 200]
　硬貨リストです。問題の通り、小さい順に並べてリストに設定しました。

・print f(200, sorted(L, reverse=True))
　sorted関数でリストLをソートします。reverseキーワードをTrueにして降順（値の大きい順）に直しています。
　なお、似た関数でsort関数もありますが、引数にリストオブジェクトしか許容せず、その引数に設定したリストオブジェクトを直接並び替えてしまうので、私はあまり使いません。sorted関数は引数に設定したイテラブルオブジェクトはそのままで、ソート結果を別オブジェクトとして作成します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。73682