作者LPH66 (1597463007)
看板Prob_Solve
标题Re: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)
时间Tue Dec 16 04:54:12 2014
如果是纯随机的话其实有个方法可以做
令 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1418676855.A.7EC.html
※ 编辑: LPH66 (123.195.39.85), 12/16/2014 04:54:55
1F：推 GenialPP: 感谢大大回应，目前苦恼正常翻的机率. 确认至少有3对 12/16 09:30
2F：→ GenialPP: 6对的机率跟随机一样，然後又卡关了 XD 12/16 09:31