Re: [問題] 機率問題
看板Prob_Solve作者AmosYang (LetMeGoogleThatForYou)時間14年前 (2010/03/07 22:19)推噓0(0推 0噓 0→)留言0則, 0人參與討論串6/11 (看更多)
: ※ 引述《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)
討論串 (同標題文章)
本文引述了以下文章的的內容：
問題
3
25
完整討論串 (本文為第 6 之 11 篇)：
問題
3
3
問題
1
2
問題
1
3
問題
1
5
問題
3
25
問題
0
7
問題
0
1
問題
1
2