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

プロジェクトオイラー問116 - (2014/03/06 (木) 18:46:58) の1つ前との変更点

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

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

+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_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]).