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

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

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

*Problem 115 「ブロックの組み合わせ方の数え上げ その2」 †
注意: これは Problem 114 をより難しくした問題である.

長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている. ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする.

例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である.

m = 3 の時, n = 30 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.

同様に, m = 10 では F(10, 56) = 880711, F(10, 57) = 1148904 であることがわかり, つまり n = 57 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.

m = 50 のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の n の値を求めよ.


解法
問１１４のコードを改良して使います。
配列やキューのある言語なら計算量ＢｉｇＯ（168）
Ｐｒｏｌｏｇ言語に配列はないのでナイーブに実装した結果、Ａｐｐｅｎｄ述語でコスト50かかり計算量はＢｉｇＯ（168*50）
となっています。



 seed(0,N):-
  between(1,N,_).
 
 search(Len,_,Ans,_):-Ans>1000*1000,!,write([ans,Len,Ans]).
 search(Len,[X1|Rest],Sum,Add):-
  !,
  Add1 is Add+X1,
  Sum1 is Sum+Add,
  Len1 is Len+1,
  append(Rest,[Sum1],List),
  search(Len1,List,Sum1,Add1).
 
 
 main115:-
  Len is 50,
  Start is -2,
  findall(C,seed(C,Len),Seed),
  search(Start,Seed,1,0).