合并石子问题(1)

mathe

4# 056254628 为什么$E(6)$和$E(8)$都小于$2$？ 我觉得对于所有的$N$，都有$E(2N)>=2$。 KeyTo9_Fans 发表于 2012-1-20 18:44

是的，很容易归纳证明

056254628

9# wayne N＝6 1,1,1,1,1,1 －－>1,1,1,1,2 －－>1，1，1，1 （2/5 的概率） 2/5*E(4) 1，1，2，2 （3/5的概率） －－> 2,2,2（1/6的概率） －－>2 －－> 1，1，3（1/6的概率） －－>2 －－> 1，1，2（4/6的概率） －－> 1，1（2/3的概率） －－>2 －－> 2，2（1/3的概率） －－>3 所以E(6 ) =2/5*E(4)+3/5*(1/6*2+1/6*2+4/6*(2/3*2+1/3*3))=34/15

mathe

4 2.33333333 6 2.26666667 8 2.30476190 10 2.30617284 12 2.31181017 14 2.31424707 16 2.31633276 18 2.31781010 20 2.31897922 22 2.31990620 24 2.32066314 26 2.32129084 28 2.32181957 30 2.32227054 32 2.32265944 34 2.32299801 36 2.32329525 38 2.32355813 40 2.32379218 42 2.32400180 44 2.32419054 46 2.32436132 48 2.32451652 50 2.32465814 52 2.32478785 54 2.32490706 56 2.32501697 58 2.32511860 60 2.32521284 62 2.32530044 64 2.32538207 66 2.32545830 68 2.32552964 70 2.32559654 72 2.32565939 74 2.32571853 76 2.32577428 78 2.32582692 80 2.32587669 82 2.32592382 84 2.32596851 86 2.32601093 88 2.32605125 90 2.32608963 92 2.32612618 94 2.32616105 96 2.32619433 98 2.32622614 100 2.32625657

056254628

我有一种思路： 合并石子的一个过程如上图。 最后一步，实际上是1+5 类型。 5个石子融合后最后和1个石子融合。 4+2类型是指4个石子先后融合，2个石子也先后融合，最后两者融合。 计算每种类型的值F() 如 F(1+5)=2 奇数个石子融合必等于1， 奇数＋奇数类型必等于2 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 2个石子的类型 F(1+1) ＝2 4个石子的类型 F(1+3)=2 概率2/3 F(2+2)=3 概率1/3 所以E(3)=2*2/3+3*1/3=7/3 6个石子的类型： F(1+5) =2 F(3+3) =2 F(2+4) =? F(2)=2 F(4)=2或3 所以F(2+4) =3或2 实际上F(2+4)分为 F(1+3+2)和F(2+2+2)两者情况 前者F(1+3+2)＝3，后者F(2+2+2)＝2 所以计算E(6)的值，只要知道F(1+3+2)＝3类型的概率p即可 ，其他类型的值都等于2 E(6)＝2*(1-p)+3*p=2+p 而p=4/15, 所以E(6）＝2+4/15=34/15 ---------------------------------------------------------------- 对于其他的N值，只要求出F值等于3的类型的概率p，E值就等于2＋p。 这也说明了所有大于2的偶数的E值大于2。 因此关键是如何正确的求出F值等于3的类型的概率p

056254628

其他N值，可能F值大于3，所以 需要求出F值不等于2的类型的概率p 如等于3的概率p1，等于4的概率p2，等于5的...... E(N)=2+(3-2)*p1+(4-2)*p2+(5-2)*p3+...... =2+p1+2*p2+3*p3+......

wayne

12# 056254628 嗯，是我算错了。 刚才编了一个小程序，很笨的思想，效率比较低。 不过，算出了 E(6) =34/15 E(8) = 242/105

2. f[x_] := If[Min[x] == Max[x], Min@x + 1, Min[x]];
3. g[long_, pair_] := Module[{tmp}, tmp = Flatten@Table[If[MemberQ[ii, pair[[1]]], Rest[ii], ii], {ii, Gather[long]}]; Flatten@Table[If[MemberQ[ii, pair[[2]]], Rest[ii], ii], {ii, Gather[tmp]}]];
4. s[sub_] := If[Length[sub] > 2, Subsets[sub, {2}], List@sub]
6. n = 6; x = List@PadLeft[{2}, n - 1, 1];
7. Do[x = Flatten[Table[Table[Join[{f[jj]}, g[kk, jj]], {jj, s[kk]}], {kk, x}], 1], {n - 2}];
8. Mean@Flatten@x

复制代码

wayne

晕死，改代码花了这么长时间 现在效率明显提高： E(10) =934/405 E(12) =360469/155925 E(14) = 2814622/1216215 E(16) = 44818433/19348875

wayne

1. {4, 7/3, 2.3333333333333333333}
2. {6, 34/15, 2.2666666666666666667}
3. {8, 242/105, 2.3047619047619047619}
4. {10, 934/405, 2.3061728395061728395}
5. {12, 360469/155925, 2.3118101651434984768}
6. {14, 2814622/1216215, 2.3142470698026253582}
7. {16, 44818433/19348875, 2.3163327583645043963}
8. {18, 3594168154/1550674125, 2.3178101033961600410}
9. {20, 36171339103/15597957375, 2.3189792248678971659}
10. {22, 90428309425574/38979295480125, 2.3199062043510287612}
11. {24, 12714348335602766/5478756531373125, 2.3206631400384943599}
12. {26, 1914048263079434/824562019771875, 2.3212908394798228431}
13. {28, 18719553371462258173/8062449634755140625, 2.3218195733920733463}
14. {30, 280059494536250948278/120597272957758471875, 2.3222705428367953621}
15. {32, 67359786835571062751804/29001146569682023996875, 2.3226594394715895785}
16. {34, 303000235021575126052361594/130434995499287619218203125, 2.3229980103248440346}
17. {36, 81008035454588784573959051881/34867731767889277340286328125, 2.3232952459841816804}
18. {38, 1684644565205504554896296858518/725027939213386357871275078125, 2.3235581335434425893}
19. {40, 1379534338939722609189264834285266774/593656501767616816756789390344140625, 2.3237921842549495637}
20. {42, 573691784542114615646064677029349374/246855137651848777758908367181640625, 2.3240018012151672664}
21. {44, 113266641551414870937145109286716564213/48733801917832544139216438134614453125, 2.3241905431960283913}
22. {46, 11494576970942130720478802489311164391605854/4945262549612057416526988059710001630859375, 2.3243613166390628652}
23. {48, 489932405826365101696295594250364472794052477/210767444363573386164596469598607990654296875, 2.3245165177466058759}
24. {50, 2655586357106340156196568421088439752575239714/1142355648960385263217734241793010376728515625, 2.3246581391032547662}

复制代码

发现mathe数值计算的精度相当高啊

mathe

C的精度还是不够呀，改用Pari/Gp计算结果: P[4]=7/3~=2.333333333333333333333333333 P[6]=34/15~=2.266666666666666666666666667 P[8]=242/105~=2.304761904761904761904761905 P[10]=934/405~=2.306172839506172839506172840 P[12]=360469/155925~=2.311810165143498476831810165 P[14]=2814622/1216215~=2.314247069802625358180913736 P[16]=44818433/19348875~=2.316332758364504396250427996 P[18]=3594168154/1550674125~=2.317810103396160041040215332 P[20]=36171339103/15597957375~=2.318979224867897165926189101 P[22]=90428309425574/38979295480125~=2.319906204351028761191353410 P[24]=12714348335602766/5478756531373125~=2.320663140038494359929997187 P[26]=1914048263079434/824562019771875~=2.321290839479822843109284352 P[28]=18719553371462258173/8062449634755140625~=2.321819573392073346279396598 P[30]=280059494536250948278/120597272957758471875~=2.322270542836795362089982819 P[32]=67359786835571062751804/29001146569682023996875~=2.32265943947158957850085 1972 P[34]=303000235021575126052361594/130434995499287619218203125~=2.322998010324844 034598593531 P[36]=81008035454588784573959051881/34867731767889277340286328125~=2.32329524598 4181680392194705 P[38]=1684644565205504554896296858518/725027939213386357871275078125~=2.32355813 3543442589289354060 P[40]=1379534338939722609189264834285266774/593656501767616816756789390344140625 ~=2.323792184254949563682406044 P[42]=573691784542114615646064677029349374/246855137651848777758908367181640625~ =2.324001801215167266356933736 P[44]=113266641551414870937145109286716564213/4873380191783254413921643813461445 3125~=2.324190543196028391284869228 P[46]=11494576970942130720478802489311164391605854/49452625496120574165269880597 10001630859375~=2.324361316639062865242714378 P[48]=489932405826365101696295594250364472794052477/2107674443635733861645964695 98607990654296875~=2.324516517746605875922781478 P[50]=2655586357106340156196568421088439752575239714/114235564896038526321773424 1793010376728515625~=2.324658139103254766227269383 P[52]=3386061530744337632684741324620617140285928199363/145650345242449121060261 1158286088230328857421875~=2.324787850731084723535321004 P[54]=1484710199197607933588392772966133681478194987167858/638610559185756464430 581237855800321352370849609375~=2.324907062436688300264175509 P[56]=37189294398026769612681880747230556842942343720439640914/15995278675925642 164592768264574230648912832670166015625~=2.325016972289458149733483302 P[58]=74195885473088900547775883882082524166839366070249075828922/31910580958471 656118362572687825590144581101176981201171875~=2.325118604692507025460906212 P[60]=2365608171964378337910842653525204661143495722820419454612427/101737274571 3260936991025376438563690758601194667357177734375~=2.325212840556186561251130563 P[62]=26807899766737700716008774623701993996823176066965941553905831282/11528789 694980694994833300256157462315700256537878594049072265625~=2.3253004414165949145 66567708 P[64]=31990534015064675055594124736786079231913712098481612611204171404532103/13 757108753595648665519665029568345104465749222289382342659100341796875~=2.3253820 68867007983988576791 P[66]=13196758823353444667011018178011214318737466760825300667240978682654/56749 06671724960261331435124811626559056905050032745789398193359375~=2.32545830032868 5671505623826 P[68]=45978113631211207947245097184833110309768074988071127207824824322786088779 49/1977102884522998647965158659724414716688295149481318583375252605621337890625~ =2.325529641938892612625195762 P[70]=66659101137736032470533304798113426052821244655000161710253318777375856848 2/286632268390245632686087147182886968566971970132441811679541627288818359375~=2 .325596539151015725528049332 P[72]=13402931052297542333664587957606619516685996526725319107042539440610448643 969229218/5763067083610511373946880803023995079748294972698842945273440696388665 924072265625~=2.325659385505664228772099192 P[74]=21569992999304933808532140839032991720196316831189492994114989240166573803 5381166/927455008923969619763159996959403494769045878031387584824164246791758361 81640625~=2.325718529929594293676002665 P[76]=14554553934936459932677335881140896437057773983569964839794832937492329624 122506250513/6257939148398805285405362958935838135509289867093634893834964408361 170932769775390625~=2.325774282842056305661612078 P[78]=24366033314088020470993916835183934883985071074565062450041508269264824694 06521845857826/10476288278829422838239057622150846637898114166061379131475259570 99229058292388916015625~=2.325826921289204953728499833 P[80]=30179488771674916333592773316573858314562335946920193287004875836413090801 9895425830650664211/129755325632035276093750436866063969135283640777453138598382 604447673534089673780059814453125~=2.325876693281859880028107687 P[82]=24553513069043895796634061058891996037207925186788081349244415105043214525 497064089387722255674/1055645625291998606965253622989868257425608376330600452025 6416346988079348820047626495361328125~=2.325923821476760313277377375 P[84]=15182345096083384421908902432408588532371283004048507307515956878957746653 7330605414835210027099610263/652732186823237567851651142960572589259515041855456 15755880006633930388621670908306575069427490234375~=2.32596850631403334254056158 9 P[86]=59710886974653514904927016114243900959026124669979894869441054892057053946 99288226607771443379078918/25670939993378700037790497062696853103933601024786596 18927133581015835893310475936440753936767578125~=2.326010928702054968740561254 P[88]=20277304959262546188862033517348874040329480510160780653139318533370560489 2440245230146089806494972407530186/871747986593346231655890612516134234141884940 45451035029760716419859489428620499867038348497982025146484375~=2.32605125232385 7819249813722 P[90]=99259045243580235735781924752590407604108180131613337074371782851032541992 7763879888165954247339358121846424286/426720639437442980395558454826647707612452 678352482816470678706875212200753097346849152715897622013092041015625~=2.3260896 25625703046570763417 P[92]=91342062579511697213188315003589418266263098508273961840806611373767148962 23649875681609306308072935113344131479/39267888056097281004939592640789266576921 20714277341872915571471132570701312210416510742408091600322723388671875~=2.32612 6183537610758244275181 P[94]=74122508229730261257333369748776196359765017034422167913880785915488144068 91345835560834044370507902506748336622402/31864736219638940674302451792922819554 62517956085643008051194614369047813211878982103864207036683908939361572265625~=2 .326161048966943037733305160 P[96]=38821811506442176249585296972323380664181650546398449088238609318224416540 906180523729266006859885872849977171323392808808/1668898033898668716399220046305 84656662273873565109705443026889770540976240674895154249730718232449554549145698 54736328125~=2.326194334099104033540765428 P[98]=80390675449847493979619025180274882977895674160167149372006891870847572653 4977107250433705646131475988481708532586340102/345584094402983417399966579004483 98981514051951502828067971838698660374358525862442102520201384503536877393722534 1796875~=2.326226141533714163464351417 P[100]=5226539659894128497233070710771117530692738619480669765678835924990181922 81866029110716455344070749740617794214017877146521/22467597675603446651024837496 65956066980639853832600872629389756550122874403831405346712609752485511903194928 16925048828125~=2.326256565279959920707809898

mathe

dumpall(N)={ local(c,v,m,s,p); v=vector(N); v[1]=vector(2); v[1][2]=1; for(u=2,N, m=2; for(h=1,u-1, s=1+min(length(v[h]),length(v[u-h])); if(s>m,m=s) ); v[u]=vector(m); v[u][2]=u/(2*u-1); for(h=1,u-1, for(i1=2,length(v[h]), for(i2=2,length(v[u-h]), p=v[h][i1]*v[u-h][i2]/(2*u-1); if(i1==i2, v[u][i1+1]+=p, if(i1

评分

参与人数 1	威望 +12	鲜花 +12	收起 理由
wayne	+ 12	+ 12	有才，我的代码有局限性，算不了那么大

查看全部评分