読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 117 / 赤タイル,緑タイル,青タイル

黒い正方形のタイルと,2 ユニットの長さの赤のタイル,3 ユニットの長さの緑のタイル,4 ユニットの長さの青のタイルから選んで組み合わせて,5 ユニットの長さの 1 列をタイルで敷く方法は 15 通りある。

f:id:variee:20170321100450p:plain

長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか。

Problem 117 - Project Euler


これは漸化式の問題ですね。長さ n の場合が a[n] 通りだとします。一番右にどのタイルを置くか考えると

a[n]=a[n-1] + a[n-2] + a[n-3] + a[n-4]

これを繰り返し使って a[50] を求めます。

易しい問題なのに正解者は8000人ほど。第1問の64万人とえらく違います。100問を超えた当たりで回答者がガクンと減っている印象を受けます。