Fibonacci斐波那契数列，很简单，就是一个递归嘛，学任何编程语言可能都会做一下这个。
这次在，python中也不例外，最基本的那种递归（如下fib1)效率太低了，只要n数字大了运算时间就会很长；而通过将计算的指保存到一个dict中，后面计算时直接拿来使用，这种方式成为备忘(memo)，如下面的fib2函数所示，则会发现效率大大提高。
在n=10以内时，fib1和fab2运行时间都很短看不出差异，但当n=40时，就太明显了，fib1运行花了35秒，fab2运行只花费了0.000082秒。
n=40时，输出如下：
|
1 2 3 4 5 6 |
jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py 2014-10-16 16:28:35.176396 fib1(40)=102334155 2014-10-16 16:29:10.479953 fib2(40)=102334155 2014-10-16 16:29:10.480035 |
这两个计算Fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import datetime def fib1(n): if n == 0: return 0 elif n == 1: return 1 else: return fib1(n - 1) + fib1(n - 2) known = {0: 0, 1: 1} def fib2(n): if n in known: return known[n] res = fib2(n - 1) + fib2(n - 2) known[n] = res return res if __name__ == '__main__': n = 40 print(datetime.datetime.now()) print('fib1(%d)=%d' % (n, fib1(n))) print(datetime.datetime.now()) print('fib2(%d)=%d' % (n, fib2(n))) print(datetime.datetime.now()) |
要说省一半有点道理， 什么原因差异这么大， 说不通啊！
试试就知道了 说得通啊 减少了太多的递归调用了
a,b = 0,1
l = []
for i in range(40):
l.append(a)
a,b = b,a+b
def there(x):
if x in l:
print(l)
print("yes")
z = int(input("please type in int 0 - 63245986: "))
t = there(z)
t