PEをMathematicaで

Project Eulerに挑戦してみよう

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

5 個の黒い正方形のタイルの列を赤(長さ 2),緑(長さ 3),青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える。

赤のタイルを選んだ場合は 7 通りの方法がある。

f:id:variee:20170321170640p:plain

緑のタイルを選んだ場合は, 3 通りである。

f:id:variee:20170321170648p:plain

青のタイルを選んだ場合は, 2 通りである。

f:id:variee:20170321170654p:plain

複数の色を混ぜられない場合,5 ユニットの長さの 一列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある。

50 ユニットの長さの一列に並んだ黒いタイルを置き換える方法は何通りあるか。ただし複数の色を混ぜることはできず,少なくとも 1 個は色のついたタイルを使うこと。

Problem 116 - Project Euler


問題117番と同様,漸化式の問題です。赤を使う場合を考えましょう。「少なくとも 1 個は色のついたタイルを使う」を一旦無視して,右端におくタイルに注目します。

red[n] = red[n - 1] + red[n - 2]

全部黒の場合は不適ですから,赤を使う場合の並べ方は a[50]-1 通りです。緑,青についても同様に考えて足しあわせます。


variee.hatenadiary.com