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

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

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



*Problem 116 「赤タイル, 緑タイル, あるいは青タイル」 †
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで, この色のついた長方形のタイルでいくつか置き換える.

もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.

図略
もし緑のタイルを選んだ場合は, 3 通りである.

図略
もし青のタイルを選んだ場合は, 2 通りである.

図略
複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.

50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか. ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.

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


解法
一種類ずつ個別に漸化式を立てるだけです。
翻訳でpluckと出てきたのですがスラングかもしれません。


 pluck_r([_,_,X3,X4],Result):-!,Result is X3+X4.
 pluck_g([_,X2,_,X4],Result):-!,Result is X2+X4.
 pluck_b([X1,_,_,X4],Result):-!,Result is X1+X4.
 
 calc(50,_,[_,_,_,Ans],Result):-!,Result is Ans-1.
 calc(Len,Pluck,[X1,X2,X3,X4],Result):-
 	!,
 	call(Pluck,[X1,X2,X3,X4],X5),
 	Len1 is Len+1,
 	calc(Len1,Pluck,[X2,X3,X4,X5],Result).
 
 
 main116:-
 	Seed=[0,0,0,1],
  	calc(0,pluck_r,Seed,AnsR),
 	calc(0,pluck_g,Seed,AnsG),
 	calc(0,pluck_b,Seed,AnsB),
 	Ans is AnsR+AnsG+AnsB,
 	write([r,AnsR,g,AnsG,b,AnsB,all,Ans]).