计算拿牌所得价值的期望值

KeyTo9_Fans

Alice和Bob在玩一个轮数为n的抽牌拿牌游戏，一开始牌堆是空的

第1轮Bob会抽取2张价值均为X1的牌放到牌堆左边数起的第1、2个位置

第2轮Bob会抽取2张价值均为X2的牌放到牌堆左边数起的第3、4个位置

第3轮Bob会抽取2张价值均为X3的牌放到牌堆左边数起的第5、6个位置

……依次类推

第n轮Bob会抽取2张价值均为Xn的牌放到牌堆的第(2n-1)、2n个位置

其中，Xi（i=1,2,...,n）都是独立的、从 1,2,3,...,a(i) 里以等概率抽取得到的随机数

里面的 a(n) 是这个数列：https://oeis.org/A033485

即 a(n) 满足递推式 a(n) = a(n-1) + a(floor(n/2))，a(1) = 1

n轮抽牌结束后，Alice和Bob都可以看到牌堆里每张牌的价值

接下来每人轮流地从牌堆里任选1张牌拿到自己手里，Alice先选，直到牌堆里的牌全都拿光为止，此时两人手上都有了n张牌

Bob选牌的策略比较简单，他总是拿剩余的牌里排在最左边的那张牌

Alice知道Bob的拿牌策略，并据此采取最佳策略选牌，使得自己拿到的n张牌的价值之和最大

给定n，求Alice和Bob拿到的n张牌的价值之和的期望值分别是多少

当n=1时，抽牌结果只有1种情况（11：1比1），求解结果好像是1和1

当n=2时，有2种情况(1111：2比2，1122：4比2)，平均值好像是3和2

当n=3时，有6种情况（111111：3比3，111122：5比3，111133：7比3，112211：5比3，112222：6比4，112233：8比4），平均值好像是17/3和10/3

当n增大时，情况数目增长得好像比阶乘还快得多，暴力算法好像在n等于10左右就算不过来了

我希望能不断地优化求解算法，最终求出n=500时的结果

KeyTo9_Fans

为了方便核对数据，我把我的暴力算法的求解结果展示一下：

n Alice Bob
1 1 1
2 3 2
3 17/3 10/3
4 52/5 23/5
5 584/35 221/35
6 4551/175 1399/175
7 257209/6825 70391/6825
8 51406/945 11909/945
9 212709683/2825550 44415367/2825550
10 728940322/7063875 132852428/7063875

暴力算法n=10就很慢了，等了6分钟才出结果
n=11估计需要4小时，我就不去算了，等贴吧里的大神们帮我优化算法吧

KeyTo9_Fans

我把算法的时间复杂度从O(n^2*a(1)*a(2)*a(3)*...*a(n))优化到了O(n^3*(a(n))^2)，5分钟内可以计算到n=40了，计算结果如下：

1. n=1: 1/1 1/1
   
2. n=2: 3/1 2/1
   
3. n=3: 17/3 10/3
   
4. n=4: 52/5 23/5
   
5. n=5: 584/35 221/35
   
6. n=6: 4551/175 1399/175
   
7. n=7: 257209/6825 70391/6825
   
8. n=8: 51406/945 11909/945
   
9. n=9: 212709683/2825550 44415367/2825550
   
10. n=10: 728940322/7063875 132852428/7063875
    
11. n=11: 5117548883/37337625 856471117/37337625
    
12. n=12: 2222945430196/12284078625 332142923804/12284078625
    
13. n=13: 490632977826497/2100577444875 68120622510253/2100577444875
    
14. n=14: 21998350539283556/73520210570625 2777960423017069/73520210570625
    
15. n=15: 2296107383073711196/6102177477361875 272909334895638179/6102177477361875
    
16. n=16: 290520046357430087803/616319925213549375 31815274529256235322/616319925213549375
    
17. n=17: 6103596064267122336536/10477438728630339375 633397038242185881589/10477438728630339375
    
18. n=18: 14929504078861643171129977/20829148192517114677500 1442206400456808965385023/20829148192517114677500
    
19. n=19: 43415464184153190032839571/49808832634280056837500 4002544483681424076460429/49808832634280056837500
    
20. n=20: 236031119468503918223624347303/223392614364746054916187500 20423601822224552820158902697/223392614364746054916187500
    
21. n=21: 21256845211757224282871051648201/16754446077355954118714062500 1763763698529856676242070226799/16754446077355954118714062500
    
22. n=22: 1110541444499564853758512037490721/731610812044543329850514062500 87105454817352577206779482821779/731610812044543329850514062500
    
23. n=23: 22727604410957158190544658891335788/12620286507768372439921367578125 1717890554590179225583030107492337/12620286507768372439921367578125
    
24. n=24: 16494779463405317855691002177784775802/7740824824355746259286315186328125 1185264435423206600518941707788661698/7740824824355746259286315186328125
    
25. n=25: 251384091734948395825540258138639547536097/100390757147069673236684221651489453125 17462355904904189102300087444049207932653/100390757147069673236684221651489453125
    
26. n=26: 132559548819721440847197176892654528823124611/45175840716181352956507899743170253906250 8795656781210012553716041403725195649531639/45175840716181352956507899743170253906250
    
27. n=27: 89446692313054893942128781731202103295485905397/26176172849261652513085148765471221406250000 5756048339709736247961904328816728959045344603/26176172849261652513085148765471221406250000
    
28. n=28: 68170986846894523537664432741238866529914202047/17171603400709406285585661176504509218750000 4207321487095623956079129117727639827117047953/17171603400709406285585661176504509218750000
    
29. n=29: 28529200787855307217060439385321473935156373891873231/6218585336672234180157003869439877848101718750000 1711779704381767601043070431764652040162284389376769/6218585336672234180157003869439877848101718750000
    
30. n=30: 18863275335068693505352051650582669616619970798444667481/3566802875248431461904338647971587080018342968750000 1089419949071032092540818746170388509002639768742832519/3566802875248431461904338647971587080018342968750000
    
31. n=31: 41047382987962403353815927697728465591974528014515751807531/6766225054346274483232530415202100690794796611718750000 2310587160288523534738127202886595634638528673377998192469/6766225054346274483232530415202100690794796611718750000
    
32. n=32: 7158930601159403479434742350280250176886096242512653251983433/1030721616612082479612422133249120005231074017185156250000 389043797290876518767024931503055621421058785334245966766567/1030721616612082479612422133249120005231074017185156250000
    
33. n=33: 49707420278993431960511516797252738526012782384877961446821869827/6277094645167582300839650791487140831857240764657601562500000 2637271967059036846190331152958528870844748351601777982865630173/6277094645167582300839650791487140831857240764657601562500000
    
34. n=34: 13745193383469859596432141817181124059992015005831264123287971365553/1525333998775722499104035142331375222141309505811797179687500000 705820920931335360079487121266324794574751252229702357071403634447/1525333998775722499104035142331375222141309505811797179687500000
    
35. n=35: 19523375722375785117840911510721398671517626221194232806562918237944159/1911243500465980291377356033341213153343060810782181866148437500000 980444550623251448055364014963136037546730156877014253477519262055841/1911243500465980291377356033341213153343060810782181866148437500000
    
36. n=36: 215763911082080182456869977293581895134888067147486082346560528332520279177/18663292782050297545299881665576946442394988817288005922939492187500000 10509850607497624982345788019873003532708777273313701463157874948729720823/18663292782050297545299881665576946442394988817288005922939492187500000
    
37. n=37: 374059475431186119094548477307112355733440007008636629230184243018820493694161/28685481006011307327125918119991766681961097812171665103557999492187500000 17841566072940361608645816048215160675512511301252659414625146043445131305839/28685481006011307327125918119991766681961097812171665103557999492187500000
    
38. n=38: 90407116368653326355190034763154597471051742701598661952359015496276270401/6156715036492006304014041964772463381756822956437041409416117187500000 4190810167046350505985720025574302389641842024056479303319625089661229599/6156715036492006304014041964772463381756822956437041409416117187500000
    
39. n=39: 1117951471927395315481540220173118681772626738417219804712681014819078099822041478/67821398624297421538039017633409164827877061819406470885178139998778076171875 50814690565122149883486170703421455706178667916611908051593871779864486847880397/67821398624297421538039017633409164827877061819406470885178139998778076171875
    
40. n=40: 17108880644919007067759092328506112196045306461660862226661873072805649935973882616629/925888379343236081951579284039214551448822078708631015493985046140559843750000000 757061522888076369578581536314571788711164369100881848310062377522592809026117383371/925888379343236081951579284039214551448822078708631015493985046140559843750000000

复制代码

我的优化方法是先把E(∑(...))写成∑(E(...))，然后把E(X)写成pr(X≥1)+pr(X≥2)+pr(X≥3)+...+pr(X≥a(i))，其中X是样本值为{1,2,3,...,a(i)}的随机变量

然后分别计算pr(X≥1)、pr(X≥2)、……、pr(X≥a(i))，得出左边数起的第i对牌，双方从中获得的价值的期望值

最后对i=1,2,...,n时的上述期望值进行求和，得出总价值的期望值

即使这样，离n=500的目标还差了很远，而且上面的分数我找不出什么规律

接下来还能怎么优化呢？

KeyTo9_Fans

注意到当m超过a(n/2)时，pr(X>=m)就等于0了，因此无需将m循环到a(n)，只需循环到a(n/2)

这样就把算法的时间复杂度从O(n^3*(a(n))^2)优化到了O(n^3*(a(n/2))^2)，5分钟内可以计算到n=80了：

n=80:

203798511466794172371784726496208792310434411006010476051134939162188265170868441514152376562040354796142638873800268573632502076649931715179713650565332510286755599228214314101507120669172970761245721870973081930491693504638249931347828741859053 / 367657129395225713440732492318106334652991925594793726631296512705245692502015144926404314619848330617534115015146709403643015315991508631908647421345640742500483740900492278097823958294348195420273277192073916416622427661523437500000000000

4939559061604016885618027482380715401471060734284851831236918519240387238535661048103525872007774608623589994279305983704627155034879293603684740198497712549379045635521977773088627300359805885005271801381268262878523045047004756152171258140947 / 367657129395225713440732492318106334652991925594793726631296512705245692502015144926404314619848330617534115015146709403643015315991508631908647421345640742500483740900492278097823958294348195420273277192073916416622427661523437500000000000

这样离n=500的目标又近了一点

接下来还能怎么优化呢？