掷硬币选择策略

wayne

进一步优化的话，就是从生成函数$\frac{1}{\sqrt{(2 x^2-x+1)^2-4 x^2}}$的系数推导出来的一般表达，$\sum _{k=0}^{\lfloor \frac{n}{2}\rfloor } C_{2 k}^{k} C_{n-2 k}^{k}$, A217615
打印全部1-n的值，空间复杂度为O(n),时间复杂度应该是O(n^2)，系数很小。$n=10^5$，时间是10秒钟。

1. Block[{level=100,y},y=Table[Sum[Binomial[2k,k]Binomial[nn-2k,k],{k,0,Floor[nn/2]}],{nn,level-1,level}];
   
2. Association[-1->1/2(2^level-1-y[[-2]]),0->1/2(y[[-1]]+2y[[-2]]+1),1->1/2(2^level-y[[-1]]-y[[-2]])]]

复制代码

再进一步优化，用递推公式，空间复杂度为O(n),时间复杂度O(n)。

1. Block[{level=100,y},y=RecurrenceTable[{(8+4 n) y[n]+(-10-4 n) y[n+1]+(3+n) y[n+2]+(-7-2 n) y[n+3]+(n+4) y[n+4]==0,y[0]==1,y[1]==1,y[2]==1,y[3]==3},y,{n,level}][[-2;;-1]];
   
2. Association[-1->1/2(2^level-1-y[[-2]]),0->1/2(y[[-1]]+2y[[-2]]+1),1->1/2(2^level-y[[-1]]-y[[-2]])]]

复制代码

空间复杂度为O(1),时间复杂度O(n),计算$n=10^5$，时间是1秒钟。$n=5*10^5$，时间是17秒钟。$n=10^6$需要61秒钟。

1. Block[{level=100,y},y=Nest[{#[[1]]+1,{#[[2,2]],#[[2,3]],#[[2,4]],-{8+4 #[[1]] ,-10-4 #[[1]],3+#[[1]] ,-7-2 #[[1]] }.#[[2]]/(#[[1]]+4)}}&,{0,{1,1,1,3}},level-1][[2,1;;2]];
   
2. Association[-1->1/2(2^level-1-y[[-2]]),0->1/2(y[[-1]]+2y[[-2]]+1),1->1/2(2^level-y[[-1]]-y[[-2]])]]

复制代码

1. ans=Block[{level=100,y},y=RecurrenceTable[{(8+4 n) y[n]+(-10-4 n) y[n+1]+(3+n) y[n+2]+(-7-2 n) y[n+3]+(n+4) y[n+4]==0,y[0]==1,y[1]==1,y[2]==1,y[3]==3},y,{n,level}];
   
2. Table[{1/2(2^i-1-y[[i]]),1/2(y[[i+1]]+2y[[i]]+1),1/2(2^i-y[[i+1]]-y[[i]])}/2^i,{i,level}]];data=N[Transpose[ans]];ListLinePlot[data,PlotLegends->{"HH<HT","HH=HT","HH>HT"}]

复制代码

wayne

rust原生支持128位整数，计算$n=100$刚好可以不用大数运算库GMP.

1. use std::collections::VecDeque;
   
2. use std::time::SystemTime;
   
3. 
   
4. fn main() {
   
5.     let epoch = SystemTime::now();
   
6.     println!("{:?}",SystemTime::now().duration_since(SystemTime::UNIX_EPOCH));
   
7. 
   
8.     let mut pool = VecDeque::from([1,1,1,3]);
   
9.     let n: u128 = 127;
   
10.     let mut all: u128 = 1;
    
11.     for i in 0..n{
    
12.         all *=2;
    
13.         if i>=n-30{
    
14.             let bob = (all-1-pool[0])/2;
    
15.             let equal = pool[0]+(1+pool[1])/2;
    
16.             let alice = (all-pool[0]-pool[1])/2;
    
17.             print!("{:<5}(hh<ht): {:<w$}\t(hh=ht): {:<w$}\t\t(hh>ht): {:<w$}",i+1,bob,equal,alice,w=36);
    
18.             // println!();
    
19.             let a = all as f64;
    
20.             println!("\t\t({:>.p$},{:>.p$},{:>.p$})",(bob as f64)/a, (equal as f64)/a, (alice as f64)/a,p=6);
    
21.         }
    
22.         // let tmp = ((7+2*i)*pool[3]-(3+i)*pool[2]+(10+4*i)*pool[1]-(8 + 4*i)*pool[0])/(i+4);
    
23.         let tmp =(pool[3]-pool[2])-(pool[3]-pool[2]+6*(pool[1]-pool[0])-2*pool[0])/(i+4)+pool[3]+4*(pool[1]-pool[0]);
    
24.         pool.push_back(tmp);
    
25.         pool.pop_front();
    
26.     }
    
27.     println!("cost {:?}",SystemTime::now().duration_since(epoch));
    
28. }
    

复制代码

1. Ok(1715305152.343156169s)
   
2. 99   (hh<ht): 307887475013879139393113690181            (hh=ht): 36009411781510700350786269593                  (hh>ht): 289928413318724861004451642914                 (0.485761,0.056813,0.457426)
   
3. 100  (hh<ht): 615866238418960422359689555420            (hh=ht): 71656412569848144755925222552                  (hh>ht): 580127949239420834381088427404                 (0.485833,0.056527,0.457640)
   
4. 101  (hh<ht): 1231912311048689813518102077359           (hh=ht): 142598837466334784225524791615                 (hh>ht): 1160790051941434205249779541778                (0.485904,0.056245,0.457851)
   
5. 102  (hh<ht): 2464178941349203194725083875170           (hh=ht): 283790833663728134305743692045                 (hh>ht): 2322632625899986276955985254289                (0.485974,0.055968,0.458059)
   
6. 103  (hh<ht): 4929056085463700688217714200622           (hh=ht): 564809220414940052524497334288                 (hh>ht): 4647339495947194471231414108098                (0.486042,0.055694,0.458263)
   
7. 104  (hh<ht): 9859488212309328994987325550483           (hh=ht): 1124154023142340240517695767352                (hh>ht): 9298767368200001188442229968181                (0.486110,0.055425,0.458465)
   
8. 105  (hh<ht): 19721688759542342617402155703713          (hh=ht): 2237536306817887597387407464263                (hh>ht): 18605594140943110633104939404056               (0.486177,0.055160,0.458663)
   
9. 106  (hh<ht): 39448724588704108863597286272374          (hh=ht): 4453835870066236514894489349075                (hh>ht): 37227077955836336317297229522615               (0.486243,0.054898,0.458859)
   
10. 107  (hh<ht): 78907991781738909149488948394304          (hh=ht): 8865797301684336543573865432290                (hh>ht): 74485487745790117698515196461534               (0.486308,0.054640,0.459052)
    
11. 108  (hh<ht): 157836772793264571940604258355357         (hh=ht): 17649015920351808224546987292201               (hh>ht): 149032764944810346618004774928698              (0.486372,0.054385,0.459243)
    
12. 109  (hh<ht): 315714545809972501460556537149596         (hh=ht): 35135160858420086644545191816522               (hh>ht): 298187400648460865461210312186394              (0.486435,0.054134,0.459430)
    
13. 110  (hh<ht): 631509962155341817566965816189309         (hh=ht): 69949047969318139938823935347876               (hh>ht): 596615204509046949626834330767839              (0.486498,0.053887,0.459616)
    
14. 111  (hh<ht): 1263179456987412039192492596883553        (hh=ht): 139264282409834451857875506251785              (hh>ht): 1193704689870167323214880061474710             (0.486559,0.053643,0.459798)
    
15. 112  (hh<ht): 2526673662150169098287635629201204        (hh=ht): 277278013488731622057191671178350              (hh>ht): 2388345182895926908185669028840542             (0.486620,0.053402,0.459979)
    
16. 113  (hh<ht): 5053968379280585438428529728859433        (hh=ht): 552088315797063400567108419567985              (hh>ht): 4778537021992006418065354510012774             (0.486679,0.053164,0.460156)
    
17. 114  (hh<ht): 10109162359781076236697817439593532       (hh=ht): 1099306519191176387162010826312597             (hh>ht): 9560718555167057890262157050974255             (0.486738,0.052930,0.460332)
    
18. 115  (hh<ht): 20220743629525292167686324928261106       (hh=ht): 2189000577664067438060679252058024             (hh>ht): 19128630661089261422496966453441638            (0.486797,0.052698,0.460505)
    
19. 116  (hh<ht): 40446261899842590283054612158941299       (hh=ht): 4359026223737111015710426807047457             (hh>ht): 38271461612977540757722902301532780            (0.486854,0.052470,0.460676)
    
20. 117  (hh<ht): 80901949449692192531156231410113016       (hh=ht): 8680591820566911868155191617122762             (hh>ht): 76570958202855379713664459507807294            (0.486911,0.052244,0.460845)
    
21. 118  (hh<ht): 161822508226277671295484110632737349      (hh=ht): 17287220013959439466838213064540052            (hh>ht): 153197270705991857463629441372808743           (0.486967,0.052022,0.461011)
    
22. 119  (hh<ht): 323681761425943154394097095810157537      (hh=ht): 34428387568130491981716156981180721            (hh>ht): 306503848898384290076090277348834030           (0.487022,0.051802,0.461176)
    
23. 120  (hh<ht): 647436085364899072133896711678848780      (hh=ht): 68568341261558583848909110250321227            (hh>ht): 613223569158458216921001238351174569           (0.487077,0.051585,0.461338)
    
24. 121  (hh<ht): 1295015479578475017690911586952670364     (hh=ht): 136567004343852607108827635393852672           (hh>ht): 1226873507647504121007874898214166116          (0.487131,0.051371,0.461499)
    
25. 122  (hh<ht): 2590314019638860849124577431822184903     (hh=ht): 272008735229095616113668527840944172           (hh>ht): 2454589228271707026376982281458249229          (0.487184,0.051159,0.461657)
    
26. 123  (hh<ht): 5181187191772509668867633090757442629     (hh=ht): 541794513810454007132444249630601521           (hh>ht): 4910842260696363307230379141854712458          (0.487237,0.050950,0.461813)
    
27. 124  (hh<ht): 10363479035203180621593202533340026436    (hh=ht): 1079197176467460732607108771855237206          (hh>ht): 9824971720888012612260601659290249574          (0.487288,0.050744,0.461968)
    
28. 125  (hh<ht): 20729140618243485957128312090435736353    (hh=ht): 2149716601081303960665650399258721969          (hh>ht): 19656438645792518015127863439276568110         (0.487340,0.050540,0.462121)
    
29. 126  (hh<ht): 41462593892666339990921377277811858188    (hh=ht): 4282285373105186235493617732141960711          (hh>ht): 39325712464463089639428656847988233965         (0.487390,0.050338,0.462272)
    
30. 127  (hh<ht): 82933710302031365514350931428118428640    (hh=ht): 8530682219042260845520404662961773086          (hh>ht): 78676790939395605371815967624803904002         (0.487441,0.050139,0.462421)
    
31. cost Ok(82.057µs)
    

复制代码