原帖：http://hi.baidu.com/atyuwen/blog/item/160bd024531e3034c995591d.html

Project Euler上最近的題目都還比較意思，來看看前些天剛剛新鮮出爐的一道題：Problem232，大意如此：說，有這樣一個硬幣游戲，需要兩個玩家參與，我們不防分別將他們稱為玩家1和玩家2。游戲規則如下：兩個玩家輪流來擲硬幣。玩家1每次只能擲一次，若是正面向上，則得1分，否則不得分。玩家2每次可以選擇拋擲硬幣的次數T（T>0），若每次都是正面向上，則得分為2的(T-1)次方，否則不得分。首先由玩家1先擲，先得分超過100者為贏家。現在問：假設玩家2每次都選擇最優的投擲次數，則他贏的概率是多少？當然，每次的投擲都是完全公正和隨機的，否則要來個劉謙，這概率就沒法算了。

首先，可以憑直覺猜猜這個概率大概是多少。毫無疑問，大于1/2是肯定的，因為玩家2至少可以選擇每次都只擲一次，在得分目標（100分）相對較大的時候，后擲的劣勢可以忽略。嗯，好像沒有其它線索了，不太好猜啊，還是老老實實算吧。

像這種算概率的題通常都比較麻煩，雖然很容易想到思路，但很難得到準確的答案。比如在這里，一個很容易想到的思路是動態規則。設P ( i, j )是當玩家1得到i分，玩家2得到j分，并且此時輪到玩家2拋擲時玩家2獲勝的最大概率。從后往前推，先看P(99, 99)。此時，玩家2選擇的拋擲次數肯定為1，得一分就夠了，多了也浪費，還降低了得分的概率。當玩家2拋出硬幣后，得到兩種結果：得1分，不得分。得1分就直接贏了，而不得分就把主動權交給了玩家1，而當玩家1再次拋出后，又得到兩種結果：得1分，則玩家1贏得游戲，不得分，則整個局勢又回到P(99,99)的初始狀態。上述過程有表達式如下：

P（99，99）= 1/2 + （1/2 * 1/2）* P（99，99）

解上述方程，可得P(99, 99)得2/3。注意到，上述表達式是一個邊界情況，因為兩個玩家都是再得一分即可獲得勝利，現在推導一個更一般的狀態轉移方程。設在該輪玩家2選擇的投擲次數為n, 這樣可以得的分數s為2^(n-1)，得分概率o 為1/2^(n+1)。則有：

P'（i, j）= o*(1/2)*P(i, j+s) + o*(1/2)*P(i+1, j+s) + (1-o)*(1/2)*P(i+1,j) + (1-o)*(1/2)*P'(i,j)

注意到上邊的式子兩邊都有 P'( i, j )，所以是個隱式表達式。(昨天寫漏了，加上一句)枚舉所有使得(s+j)小于或者剛好大于100的n，計算上式中的P'(i, j)，則有P(i, j)為這些P'(i, j)的最大值。當然，玩家2也可以選擇令(s+j)遠遠大于100的投擲次數n， 但比較顯然的是這樣得到的P’(i, j)不會是最大的，比如前面所說的，在P(99, 99)的局勢中玩家2明顯不會選擇超過1的投擲次數。有的地方只所以乘了二分之一是因為狀態轉移還需要玩家1的過渡，因為我們的狀態定義是在當輪到玩家2拋擲時玩家2獲勝的最大概率。為了表達方便，沒有考慮一些邊界的情況。然后按照上面的轉移方程編寫程序就行了，這道題的答案為：0.83648556.

這個答案是不是比用直覺猜的要高些呢。（我是猜的大概在2/3左右，誤差不小），這首題其實非常適合用來做面試題：生動有趣，即不是太簡單，也不是太難（比起以其相似的poj1074算是小烏見大烏了），雖然比較容易想到算法，卻也不容易一次性算對。爺爺的，要是本人以后有榮幸當上面試官，一定要出出這道題。

轉載于:https://www.cnblogs.com/atyuwen/archive/2009/11/09/ProjectEuler232.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的硬币游戏 Project Euler 232的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。