日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問１１７「赤タイル, 緑タイル, そして青タイル」
黒い正方形のタイルと,
2 ユニットの長さの赤のタイル,
3 ユニットの長さの緑のタイル,
4 ユニットの長さの青のタイルから選んで組み合わせて,
5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.
長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか.
注: この問題は Problem 116 に関連する
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def e(n, m, d):
if n not in d:
d[n] = sum([e(n-i, m, d) for i in xrange(1, m+1)])
return d[n]
def f(n, m):
d = {0:0}
for i in xrange(1, m+1): d[i] = e(i, i-1, d)+1
return e(n, m, d)
n = 50
m = 4
s = f(n, m)
print s
4個以下の長さのブロック4種類を使って一列にタイルを敷きます。
パターン数辞書dに使うタイルの分の初期化をして求めます。
１．関数e(n, m, d):
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書（連想配列）です。
1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
ループ変数iが1からmまで１つずつ変化しながら、全体がn-i個の状態の直後にi個ブロックを1つ置く場合のパターン数の累積値です。
２．関数f(n, m)
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・まず、パターン数辞書の初期状態を準備します。
キー=0の場合、パターン数は0です。
・d[n] = e(i, i-1, d)+1
0<キーi<mの場合、パターン数は全体がi個で、i-1個以下の長さのブロックからできているパターン数とi個ブロック1つだけ置くパターン数1の和です。
・ここまででパターン数辞書の初期状態が準備できたら、
関数e(n, m, d)が求める値なので、これを求めて返します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
100808458960497
