python之斐波那契序列算法的总结

斐波那契序列为1,1,2,3,5,8,13.......序列中的下一个数字为之前前两个数字的运算和。

方法1：矩阵思想

                   [0,1]         [a]    [b]                                        

　               [1,1]    *    [b] = [a+b]       

import pandas as pd
import numpy as np


def func(n):
    a=np.mat([[0,1],[1,1]])
    b=np.mat([[1],[1]])
    return a**(n-1)*b
func(50)

 方法二：

递归思想，但递归由于较耗时，这里利用缓存将参数n和结果保存到字典a中，速度为0.007s。

a={}
def fun(n):
    if a.get(n):
        return a[n]

    if n in [1,2]:
        return 1
    else:
        a[n]=fun(n-1)+fun(n-2)
        return a[n]
start=time.time()
print(fun(400))
print(time.time()-start)

 方法三：

生成器，对于递归，若较多时，仍旧不合适。

#生成器思想
def fun(n):
    a=0
    b=1
    for i in range(1,n):
        sum=a+b
        yield sum
        a=b
        b=sum