题目64：10000以下的连分数中有多少拥有奇数周期？

jerryxjr1220

这题的思路就是找出除整数部分后面的无理数从第几位开始循环。
a是整数部分+无理数部分，d是整数部分，c就是无理数部分。
依次存入列表，然后比较。开始循环了就记录下来。
代码如下：

1. 
   
2. import math
   
3. def gao(n):
   
4.         m = int(math.sqrt(n))
   
5.         if m * m == n:
   
6.                 return 0
   
7.         dic = {}
   
8.         d = m
   
9.         a = n
   
10.         b = -m
    
11.         c = 1
    
12.         len = 0
    
13.         while True:
    
14.                 nc =  a - b * b
    
15.                 nc /= c
    
16.                 nd = int((math.sqrt(a) - b) / nc)
    
17.                 nb = -b - nd * nc
    
18.                 t = (nb, nc, nd)
    
19.                 b = nb
    
20.                 c = nc
    
21.                 d = nd
    
22.                 if not t in dic:
    
23.                         len += 1
    
24.                         dic[t] = 1
    
25.                 else:
    
26.                         break
    
27.                        
    
28.         return len
    
29. ans = 0
    
30. for i in range(1, 10001):
    
31.         k = gao(i)
    
32.         if k % 2 != 0:
    
33.                 ans += 1
    
34. print (ans)

复制代码

jerryxjr1220

结果1322

jerryxjr1220

另外一个暴力的的方法，用decimal库，把精度提高到250位以上（200位小数，仍有3个数有误差）
同样可以得到结果......1322......7秒多，速度也还行，简单粗暴，不用考虑复杂的数学方程式

1. import decimal as dc
   
2. dc.getcontext().prec = 250
   
3. def root(n):
   
4.     blist = []
   
5.     n0 = dc.Decimal(i).sqrt()
   
6.     a0 = int(n0)
   
7.     b0 = n0 - a0
   
8.     n1 = 1/b0
   
9.     a1 = int(n1)
   
10.     b1 = n1 - a1
    
11.     while str(b1)[:11] not in blist:
    
12.         blist.append(str(b1)[:11])
    
13.         n1 = 1/b1
    
14.         a1 = int(n1)
    
15.         b1 = n1 - a1
    
16.     return len(blist)
    
17. 
    
18. count = 0
    
19. for i in range(2,10000):
    
20.     if i**0.5 != int(i**0.5):
    
21.         if root(i) % 2 == 1:
    
22.             count += 1
    
23. print (count)

复制代码