Re: [問題] 記憶遊戲 (更新暴力法解隨機翻的情況, 求正常翻的機率)
如果是純隨機的話其實有個方法可以做
令 P(n,k,m) (n,k≧m) 是 n 對牌翻 k 次翻出 m 對的機率
由於 n 對牌隨機翻兩張翻到一對牌的機率是 n/C(2n,2) = 1/(2n-1)
可以簡單得到下面的遞迴式:
P(n,k,m) = (1/(2n-1))*P(n-1,k-1,m-1) + (1-1/(2n-1))*P(n,k-1,m), n,k,m > 0
初始條件很容易得到:
P(n,0,m) = 1
P(n,k,0) = (1-1/(2n-1))^k
P(n,k,k) = 1/(2n-1)(2n-3)(2n-5)...(2n-2k+1)
有了這些就可以很簡單的寫程式 DP 了
(或者如果覺得計算順序很難決定的話用筆記法也是 OK)
我的程式 (筆記法 on Mathematica) 計算結果是:
P(6,6,0) = 1000000/1771561 ≒ 0.564473930
P(6,6,1) = 33518456608/104608905489 ≒ 0.320416856
P(6,6,2) = 2124501072016/22833271098099 ≒ 0.093044096
P(6,6,3) = 536959299248/28829887750125 ≒ 0.018625092
P(6,6,4) = 122612704/41601569625 ≒ 0.002947310
P(6,6,5) = 14282/36018675 ≒ 0.000396517
P(6,6,6) = 1/10395 ≒ 0.000096200
--
至於正常翻則還要考慮使用的策略, 這就不容易化為遞迴式了
--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1418676855.A.7EC.html
※ 編輯: LPH66 (123.195.39.85), 12/16/2014 04:54:55
推
12/16 09:30, , 1F
12/16 09:30, 1F
→
12/16 09:31, , 2F
12/16 09:31, 2F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 4 篇)：