Crossin的编程教室

标题: 裴波那契数列 [打印本页]

作者: 我是一个小菜鸟 时间: 2015-12-11 14:56
标题: 裴波那契数列
思维一直转不过弯，感觉很别扭，最后谷歌_Luc_先生的不同角度，才知道是赋值的问题。
运行效果：
>>> fib(10)
1
1
2
3
5
8
13
21
34
55
55
代码如下：
def fib(n):
x,y=0,1
while(n):
x,y,n=y,x+y,n-1
print(x)
return x

20140722045820777.gif (403.19 KB, 下载次数: 504)

笨牛

作者: 我是一个小菜鸟 时间: 2015-12-11 15:33
代码优化：
用python实现斐波那切数列，正常我们的思路肯定是嵌套函数：
count = 0
def fibonacci (n):
global count
count += 1
if n == 0 or n == 1:
      return 1
else:
      return fibonacci(n-1) + fibonacci(n-2)

fibonacci(20)
print count
这个count是考察函数调用次数，打印结果是21891，也就是说，
我们计算20的数列居然要调用这么多次函数，那有个更好的方式
来写这个fibonacci函数
previous = {0:1, 1:1}
def fibonacci_s(n):
global count
count += 1
if previous.has_key(n):
      return previous[n]
else:
      newValue = fibonacci_s(n-1) + fibonacci_s(n-2)
      previous[n] = newValue
      return newValue
它是用了一个字典来保存已经计算过的值，这样就能避免重复调用，所以由这个
函数执行打印出的count很小，只有几十，而且速度很快，虽然只是加了一个小
技巧，却带来这么大方便，看来平时自己写程序的时候的确需要多思考优化，
才能让自己写的程序更完善。
本文出自 “只想简单” 博客，请务必保留此出处http://gmingzhe.blog.51cto.com/810664/165921

作者: crossin先生 时间: 2015-12-11 21:50
斐波那契数列以前被我用做过笔试题

欢迎光临 Crossin的编程教室 (https://bbs.crossincode.com/)