python求解斐波那契数列的两个方法

Fibonacci斐波那契数列，很简单，就是一个递归嘛，学任何编程语言可能都会做一下这个。这次在，python中也不例外，最基本的那种递归（如下fib1)效率太低了，只要n数字大了运算时间就会很长；而通过将计算的指保存到一个dict中，后面计算时直接拿来使用，这种方式成为备忘(memo)，如下面的fib2函数所示，则会发现效率大大提高。在n=10以内时，fib1和fab2运行时间都很短看不出差异，但当n=40时，就太明显了，fib1运行花了35秒，fab2运行只花费了0.00001秒。n=40时，输出如下：

jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py 2014-10-16 16:28:35.176396fib1(40)=1023341552014-10-16 16:29:10.479953fib2(40)=1023341552014-10-16 16:29:10.480035

这两个计算Fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py

import datetimedef 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 resif __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())

Original article: python求解斐波那契数列的两个方法

环境不会改变，解决之道在于改变自己。

相关文章：

你感兴趣的文章：

标签云：