小练习结果揭晓：考察2的平方根的展开

冬雪雪冬

原帖子：http://bbs.fishc.com/thread-82007-1-1.html
题目：

2 的平方根可以被表示为无限延伸的分数：

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

将其前四次迭代展开，我们得到：

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

接下来三次迭代的展开是 99/70, 239/169, 和 577/408, 但是第八次迭代的展开, 1393/985, 是第一个分子的位数超过分母的位数的例子。

在前 1000 次迭代的展开中，有多少个的分子位数超过分母位数？

题目很简单，用迭代就可以，如果用递归由于次数太多速度会成问题。
正确答案是：
153

答案正确的鱼油：
Craigyu  0.00429s
小Q学Python  0.00325s
jerryxjr1220  0.00227s  0.00219s
余欲渔  0.00325s

无论是用时还是思路的巧妙jerryxjr1220都是优胜。

我的写法，程序的效率比大家的差多了。

1. from time import time
   
2. from fractions import Fraction as fr
   
3. start = time()
   
4. a = fr(1 / 2)
   
5. count = 0
   
6. for i in range(2, 1001):
   
7.     a = 1 / (2 + a)
   
8.     sq = 1 + a
   
9.     if len(str(sq.numerator)) > len(str(sq.denominator)):
   
10.         count += 1
    
11. print(count)
    
12. print(time() - start)
    

复制代码

浅笑无痕111

棒棒棒！