「プロジェクトオイラー問１１４」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１１４」(2014/03/06 (木) 10:45:56) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

*Problem 114 「ブロックの組み合わせ方の数え上げ その1」 †
直列な５０マスを特定の規則のもと赤ブロックで埋めるとき何通りの埋め方があるか計算する問題。
詳細はリンク先参照のこと。



解法
手前から埋めていく動的計画法で片が付きます。
計算量は48回。


 search(52,[_,_,Sum],_,_):-!,write([ans,Sum]).
 search(Len,[X1,X2,X3],Sum,Add):-
  	!,
 	Add1 is Add+X1,
 	Sum1 is Sum+Add,
 	Len1 is Len+1,
 	write([Len1,Sum1,Add1]),nl,
 	search(Len1,[X2,X3,Sum1],Sum1,Add1).
 
 main114:-
 	search(4,[1,1,1],1,1).