「プロジェクトオイラー問１１４」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問１１４ - (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).