[中譯] ProjectEuler 470 Super Ramvok

作者: tml (流刑人形)   2014-05-06 04:52:15
Super Ramvok
http://projecteuler.net/problem=470
一場Ramvok遊戲的規則如下:
令t表示一場遊戲的總回合數。如果t=0則遊戲立即終止。否則,每個回合玩家都能擲一顆
骰子。若目前回合數i<t,則玩家可以選擇得到等同當前骰子點數的獎金,或是放棄這回
合的結果,在下個回合重新嘗試一次。但如果i=t則無法放棄,直接得到最後一次骰出的
點數的獎金。在遊戲開始之前,玩家可以自行選擇t值,並先支付ct的賭金,其中c是一個
常數。如果c=0則即使選擇t為無限大也不需支付任何賭金。令d為一場遊戲所使用的公正
骰子的面數,則R(d,c)代表在給定d和c的情況下,使用最佳策略時,一場遊戲的淨利
(奬金減去賭金)的期望值。例如R(4,0.2) = 2.65。並假設玩家有足夠的資金能夠付出
任意賭金。
現在,我們更進一步考慮一場超級Ramvok遊戲規則如下:
一場超級Ramvok中,我們會重覆執行一般的Ramvok,並加上一些附加條件。在每場Ramvok
之後,都會改變一次骰子。改變的方法如下:先擲一次骰子,如果骰出的結果是數字,則
將其換成空白。反之,如果是已經空白,則回復成原本的數字。再用這個改變過的骰子執
行下一次的遊戲。(遊戲進行中時,將反覆擲骰直到數字出現為止。)玩家自始至終都能
得知哪些數字是空白、哪些不是。一場超級Ramvok會在骰子的每一面都是空白時才結束。
令S(d,c)為給定d和c時,在最佳策略下,玩家在一場超級Ramvok中所能獲得的淨利的期
望值。在一開始遊戲時,d面骰的每一面都是有數字的。舉例而言,S(6,1) = 208.3。
令F(n) = ΣΣS(d,c)對4≦d≦n以及0≦c≦n的雙重和。
請求出F(20),並四捨五入至整數位。
作者: tml (流刑人形)   2014-05-06 09:08:00
Ramvok是這題的自創字,其實是Markov的重排…不知道算不算提示
作者: LPH66 (-6.2598534e+18f)   2014-05-06 23:50:00
這 Markov 很討厭啊 QAQ 它是個 d 維超立方體的圖理論上應該離開某個距離的點的值會有共同性但一下子找不出來(因為這是一個很顯然的對稱性...但還想不到要怎麼利用)

Links booklink

Contact Us: admin [ a t ] ucptt.com