PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 114 / ブロックの組み合わせ方の数え上げ その1

長さ 7 ユニットからなる 1 列上に最低 3 ユニットの長さを持つ赤ブロックが置かれている。ただしどの赤ブロック同士も少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい)。これを敷き詰める方法は 17 通りある。

f:id:variee:20170321174044p:plain

50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか。

(注意)上の例では起こりえないが,ブロックの大きさが複数混ざっていてもよい。たとえば 8 ユニットの長さの 1 列では赤(3), 黒(1), 赤(4) を使うことができる。

Problem 114 - Project Euler


連立漸化式を使います。長さが n で右端が黒のものが black[n] 個,赤のものが red[n] 個あるとします。

  • black[n] = black[n-1] + red[n-1]
  • red[n] = Sum[black[k], {k, 1, n - 3}] + 1

red[n] 末尾の 1 は,何もないところに長さ n の赤を置く場合の1通りです。

これらの漸化式を繰り返し使うと答えが出ます。