婓波那契(Fibonacci)数列

有人说婓波那契起源于一对繁殖力惊人，基因非常优秀的兔子，也有人说远古时期的 *** 就知道这个规律。

婓波那契由如下递推关系式定义：

1: F(n)=F(n-1)+F(n-2)" src="https://latex.codecogs.com/gif.latex?if%20n%3E1%3A%20F%28n%29%3DF%28n-1%29+F%28n-2%29" />

解法 1

使用递归法，由上到下求解

def Fibonacci(n):
    if n == 0 or n==1:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
print(Fibonacci(3))

解法 2

采用类似动态规划的方法，由下到上求解

def Fibonacci(n):
    dp = [0]*(n+1)
    dp[0], dp[1] = 1, 1
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
print(Fibonacci(3))

解法 3

由递推公式F(n) = F(n-1) + F(n-2)，知道F(n)的特征方程为：

推导：

设有数列c(n) = a*c(n-1)+b*c(n-2)。

假设存在x，y满足下式：

c(n)-x*c(n-1) = y*(c(n-1)-x*c(n-2))

c(n)=(x+y)*c(n-1)-x*y*c(n-2)

则对婓波那契数列有

x+y=1,  -xy=1

消去y得：

 根据求根公式得:

所以存在A，B使得：

代入F(0)和F(1)得：

该方法的缺点是公式中引入了无理数。

解法 4

注意到婓波那契数列是二维递推数列，所以存在一个二维矩阵使得：

可得：

通过推导得：

代码就不给了，这就是矩阵得大数幂。