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

「プロジェクトオイラー問１２１」(2014/03/08 (土) 06:37:56) の最新版変更点

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

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

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

Problem 121 「円盤ゲームの賞金額」 †
袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.

プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.

ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.

15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.


解法
地道に計算するだけです。
厳密にやるなら分数計算ですが手抜きして浮動小数点でも十分まにあいます。
計算量はBigO(15*15)
型システムと相性が悪いＰｒｏｌｏｇに分数型を導入するのはあまり考えられませんね。


 calc_next(Number,[P1,_],[P3]):-
 	!,
 	P3 is P1/Number.
 calc_next(Number,[P1,P2|Rest],[P3|Result]):-
 	!,
 	P3 is P1/Number+P2*(Number-1)/Number,
 	calc_next(Number,[P2|Rest],Result).
 
 sum([],0,8):-!.
 sum([X|Xs],ResultSum,ResultC):-
 	!,
 	sum(Xs,ReSum,ReC),
 	(0<ReC -> ResultSum is ReSum+X;ResultSum is ReSum),
 	ResultC is ReC-1.
 
 dp(16,DP):-!,sum(DP,Ans,_),Ans1 is floor(1/Ans),write(Ans1).
 dp(Turn,DP):-
 	!,
 	Number is Turn+1,
 	calc_next(Number,DP,DP1),
 	[Top|_]=DP,
 	Top1 is Top*(Number-1)/Number,
 	DP2=[Top1|DP1],
 	Turn1 is Turn+1,
 	dp(Turn1,DP2).
 
 seed(0):-
 	between(1,15,_).
 
 main121:-
 	findall(P,seed(P),Seed),
 	Seed1=[1|Seed],
 	dp(1,Seed1).

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

Problem 121 「円盤ゲームの賞金額」 †
袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.

プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.

ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.

15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.


解法
地道に計算するだけです。
厳密にやるなら分数計算ですが手抜きして浮動小数点でも十分まにあいます。
計算量はBigO(15*15)
型システムと相性が悪いＰｒｏｌｏｇに分数型を導入するのはあまり考えられませんね。
マジックナンバーがあるので少し手癖の悪いコードとなりました。


 calc_next(Number,[P1,_],[P3]):-
 	!,
 	P3 is P1/Number.
 calc_next(Number,[P1,P2|Rest],[P3|Result]):-
 	!,
 	P3 is P1/Number+P2*(Number-1)/Number,
 	calc_next(Number,[P2|Rest],Result).
 
 sum([],0,8):-!.
 sum([X|Xs],ResultSum,ResultC):-
 	!,
 	sum(Xs,ReSum,ReC),
 	(0<ReC -> ResultSum is ReSum+X;ResultSum is ReSum),
 	ResultC is ReC-1.
 
 dp(16,DP):-!,sum(DP,Ans,_),Ans1 is floor(1/Ans),write(Ans1).
 dp(Turn,DP):-
 	!,
 	Number is Turn+1,
 	calc_next(Number,DP,DP1),
 	[Top|_]=DP,
 	Top1 is Top*(Number-1)/Number,
 	DP2=[Top1|DP1],
 	Turn1 is Turn+1,
 	dp(Turn1,DP2).
 
 seed(0):-
 	between(1,15,_).
 
 main121:-
 	findall(P,seed(P),Seed),
 	Seed1=[1|Seed],
 	dp(1,Seed1).