欧拉计划770：Delphi翻转

〇〇 · 发表于 2021-11-14 06:34

python n=3000 没有溢出，不知对错

'''
3拿1给：1+X = (1-X)*8/7，X=1/15, 最后得分 16/15
2拿2给：最后得分 16/11
1拿3给：(1+X)*2 = (1-X)*8，X=3/5, 最后得分 16/5
'''
v_res=dict()
def f(p_take,p_give):

   v_idx =str(p_take)+','+str(p_give)
   #print(v_idx)
   if (v_idx)in v_res:
      return v_res.get(v_idx)
   #print(v_idx)
   if p_give==p_take+1:return 2
   #if p_give==1:return 1+1/(pow(2,p_take+1)-1)
   if p_take==0:
      v_ret = pow(2,p_give)
   elif p_give==0:
      v_ret = 1
   else:
      # (1+x)*f(p_take,p_give-1) = (1-x)*f(p_take-1,p_give)
      #x = (f(p_take-1,p_give)-f(p_take,p_give-1))/(f(p_take-1,p_give)+f(p_take,p_give-1))
      #v_ret =  (1+x)*f(p_take,p_give-1)
      a,b=f(p_take-1,p_give),f(p_take,p_give-1)
      v_ret=2*a*b/(a+b)

   v_res[v_idx] = v_ret
   return v_ret

#手工设置递归调用深度：

import  sys
import time
t=time.time()
sys.setrecursionlimit(1000000) #例如这里设置为一百万
print(f(3000,3000))
print(time.time()-t)
#[print(i,j,round(f(i,j),4))for i in range(1,11)for j in range(1,11)]

〇〇 · 发表于 2021-11-21 10:42

用分数表示，

import fractions as fs

v_fres=dict()
def ff(p_take,p_give):

   v_idx =str(p_take)+','+str(p_give)
   #print(v_idx)
   if (v_idx)in v_fres:
      return v_fres.get(v_idx)
   #print(v_idx)
   if p_give==p_take+1:return fs.Fraction(2)

   if p_take==0:
      v_ret = fs.Fraction(pow(2,p_give))
   elif p_give==0:
      v_ret = fs.Fraction(1)
   else:

      a,b=ff(p_take-1,p_give),ff(p_take,p_give-1)
      v_ret=2*a*b/(a+b)

   v_fres[v_idx] = v_ret
   return v_ret
看看有什么规律，分母总是2的幂，遇到2的倍数就翻倍

1 1 1.3333 4/3
2 2 1.4545 16/11
3 3 1.5238 32/21
4 4 1.5706 256/163
5 5 1.605 512/319
6 6 1.6319 2048/1255
7 7 1.6537 4096/2477
8 8 1.6717 65536/39203
9 9 1.6871 131072/77691
10 10 1.7004 524288/308333
11 11 1.7121 1048576/612467
12 12 1.7224 8388608/4870343
13 13 1.7316 16777216/9688683
14 14 1.74 67108874/38569007
15 15 1.7475 134217728/76803709
16 16 1.7545 4294967296/2448023843
17 17 1.7608 8589934592/4878368851
18 18 1.7667 34359738368/19448653009
19 19 1.7721 68719476736/38777896343
20 20 1.7772 549755813888/309339539149

[Program finished]

〇〇 · 发表于 2021-11-21 11:18

本帖最后由〇〇于 2021-11-21 11:19 编辑

分母d（n）=d（n-1）*2^x -y，其中 y是这个序列 http://oeis.org/A098597