「プロジェクトオイラー問117」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問117 - (2014/03/06 (木) 18:55:03) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20117

*Problem 117 「赤タイル, 緑タイル, そして青タイル」 †
黒い正方形のタイルと, 2 ユニットの長さの赤のタイル, 3 ユニットの長さの緑のタイル, 4 ユニットの長さの青のタイルから選んで組み合わせて, 5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.

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

注: この問題は Problem 116 に関連する
詳細はリンク先参照のこと。

解法
黒いブロックも1ブロックを置くものだと考えると単純な漸化式になります。
前4つの項から決まるフィナボッチ数列と考えればよいだけです。
ね、簡単でしょ。

 calc(50,[_,_,_,Ans],Result):-!,Result is Ans.
 calc(Len,[X1,X2,X3,X4],Result):-
 	!,
  	X5 is X1+X2+X3+X4,
 	Len1 is Len+1,
 	write([Len1,X5]),
 	calc(Len1,[X2,X3,X4,X5],Result).
 
 
 main117:-
 	calc(0,[0,0,0,1],Ans),
 	write(Ans).