小练习：20170129 考察2的平方根的展开

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即2.6 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序




题目：

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 次迭代的展开中，有多少个的分子位数超过分母位数？

Craigyu

1. from time import time
   
2. stime = time()
   
3. m = [1, 1]
   
4. n = [0, 1]
   
5. count = 0
   
6. for i in range(0, 1000):
   
7.     m.append(m[-1])
   
8.     n.append(n[-1])
   
9.     m[-1] = m[0] + m[1] + m[2]
   
10.     n[-1] = n[0] + n[1] + n[2]
    
11.     m.pop(0)
    
12.     n.pop(0)
    
13.     if len(str(m[-1])) > len(str(n[-1])):
    
14.         count += 1
    
15. print(count)
    
16. print(time() - stime)

复制代码

153
0.027019023895263672

小Q学Python

1. counts = 0
   
2. n = 1000
   
3. a, b = 1, 1
   
4. while n:
   
5.     a, b = a+2*b, a+b
   
6.     n -= 1
   
7.     if len(str(a)) > len(str(b)):
   
8.         counts += 1
   
9. print(counts)

复制代码

153

jerryxjr1220

这题的解题思路如果是按照常规解法的话，应该是依次算出所有分子和分母的值，然后比较分子和分母的位数，如果分子的位数大于分母，则计数。

其实，这题还有一种思路，就是只需要计算分子（或者只需要计算分母）就能知道结果，这样可以减少一半以上的计算量。
分析：
由于√ 2 = 1.414213...，已知条件：1393/985, 是第一个分子的位数超过分母的位数，如果要使分子的位数大于分母，那么分子的开头4位必然是在1000至1414之间，（可以自行代入数值验证）。
同理，如果要使分子的位数大于分母，那么分母的开头三位必然是在707至999之间。
两种方法任取一种都可以。

代码：

1. import time
   
2. start = time.time()
   
3. fz0,fz1,c = 3,7,0
   
4. for i in range(3,1001):
   
5.         fz1, fz0 = fz1*2+fz0, fz1
   
6.         if 1000 <= int(str(fz1)[:4]) <= 1414:
   
7.                 c += 1
   
8. print (c)
   
9. print ('Time used: %f sec' % (time.time()-start))
   
10. 
    
11. import time
    
12. start = time.time()
    
13. fm0,fm1,c = 2,5,0
    
14. for i in range(3,1001):
    
15.         fm1, fm0 = fm1*2+fm0, fm1
    
16.         if 707 <= int(str(fm1)[:3]) < 1000:
    
17.                 c += 1
    
18. print (c)
    
19. print ('Time used: %f sec' % (time.time()-start))

复制代码

输出：
Python 3.5.2 (default, Dec 2015, 13:05:11)
[GCC 4.8.2] on linux
   
153
Time used: 0.002108 sec
153
Time used: 0.002109 sec

正常解法用时大约在5~6毫秒左右，只算分子或者只算分母只需要2毫秒

余欲渔

0次展开的时候分子分母是1,1；一次是3,2；两次是7,5，排列下去可以发现其规律，于是有了一下代码

1. y=1
   
2. x=1
   
3. n=0
   
4. for i in range(1000):
   
5.     y2=y+x
   
6.     x=y+y2
   
7.     if len(str(x))>len(str(y2)):
   
8.         n+=1
   
9.     y=y2
   
10. print(n)
    

复制代码

结果：

1. >>>
   
2. RESTART: C:/Users/ASUS/AppData/Local/Programs/Python/Python35-32/考察2的平方根的展开.py
   
3. 153
   
4. >>>

复制代码

spid3

jerryxjr1220 发表于 2017-2-3 10:07
这题的解题思路如果是按照常规解法的话，应该是依次算出所有分子和分母的值，然后比较分子和分母的位数，如 ...

感觉位数多了的话1414的精度是不是有可能不够.不过你这思路不错,分子第一位是1,分母第一位不是1的肯定符合要求

jerryxjr1220

spid3 发表于 2017-2-3 19:54
感觉位数多了的话1414的精度是不是有可能不够.不过你这思路不错,分子第一位是1,分母第一位不是1的肯定符 ...

对于前1000次迭代4位的精度已经够了，如果要是迭代再多的话，可以根据需要增加精度。

spid3

jerryxjr1220 发表于 2017-2-3 20:06
对于前1000次迭代4位的精度已经够了，如果要是迭代再多的话，可以根据需要增加精度。

这个具体位数精度我不大会估算,所以觉得不保险,你能确保精度够那方法确实好用
另外有个python的问题想请教下,麻烦大神解答下,谢谢:
就是在shell中能用python脚本切换目录吗,好像os.chdir只能切换python子进程的工作目录,不知道怎么样才能切换shell的当前工作目录