: ※ 引述《Sany (小美眉)》之銘言： : : 以前玩過一個遊戲, : : 規則是這樣的... : : 猜拳贏一次得一分，平手不影響分數，輸一次倒扣一分至０分為止 : : 你得五分則本局勝利與結束，你猜輸三次則本局失敗與結束 : : 我覺得那真是很難贏的遊戲, : : 後來想算算贏的機率, : : 但都沒人會算, : : 我只好自己用程式試, : : 玩10萬次的勝率是13.02% : : 不知道有沒有人能列式算出勝率呢? : 也就是這樣: : : → AmosYang:0.130859375 這個應該沒錯了 03/07 20:45 : → AmosYang:解出來了，但有一種"輸了"的感覺，因為我是一項一項列出 03/07 20:49 : → AmosYang:慢慢加;一開始原本以為DP建表直接算就好，結果答案出 03/07 20:50 : → AmosYang:來差十萬八千里… <囧> 03/07 20:50 : → AmosYang:<囧><囧><囧><囧><囧> 03/07 21:34 : → AmosYang:事實上之前DP解法的方向是對的，但有一個小typo... 03/07 21:35 : → AmosYang:總之…DP解、暴力解、模擬解三管齊下…那答案應該是正確 03/07 21:36 : 推 Sany:dp解系啥米? 03/07 21:51 : → AmosYang:dynamic programming 03/07 21:59 總之，這題可以用 DP 這樣解: 先開 2D table row index 為猜輸的次數 column index 為目前分數 table 開出來後就不難看出這個 table 可以紀錄這個遊戲的狀態 且，遊戲目前停在某個 cell 的機率就是「所有通往此 cell 的路徑的機率的總和」 而每個 cell 要記得的就是「從 (R=0,C=0) 走到我這格走了 X 步有 Y 種走法」 然後讓 (R=0,C=0) 這格初始化為 「從 (R=0,C=0) 走到我這格走了 0 步有 1 種走法」 然後要記得處理一些 special case, 假設目前在計算 (R,C) 這格 當 R=0 或 C=4 時，只需要看 (R,C-1) 這格 當 C=0 時，要看的是 (R-1,C) 與 (R-1,C+1) 這兩格 其他的時候，要看的是 (R,C-1) 與 (R-1,C+1) 這兩格 最後，啟動 DP 去算 (0,4) (1,4) (2,4) 把所有的 "走了 X 步有 Y 種走法" 換成 (Y * 2^-X) 就是該路徑的機率總和 那三個 cell 裡的機率通通加起來即可得解… 我覺得這題還算善良的，猜贏與猜輸的機率相同， 有空有閒的人可以想想若猜贏與猜輸機率不同要怎麼解… (我已經不行了…) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 65.87.177.87 hmm... 若猜贏與猜輸機率不同...事實上沒有想像中複雜…算法幾乎一樣… (自言自語…) ※ 編輯: AmosYang 來自: 65.87.177.87 (03/07 22:45)