“哥德巴赫猜想”中的“四个悖论”，其中有一个是“斐波那契数列”，它的出现使猜想最终得到了证实。这是一个关于代数数列的著名问题。这个问题在数学上是很难求解的，其中有一种特殊的数列——斐波那契数列。数学家们在研究该数列出后，发现它在数学上有许多重要的应用，如在科学计算中可以用它来求某些代数数、几何数字等等。下面我们就一起来看一下这个数列吧！
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1) F(n - 2)（n ≥ 2，n ∈ N*）
因为是个经典的问题，在算法面试中经常直接或间接（变体）遇到求解斐波那契数列的第n项的值，下面介绍两种解法（一种极其常规，一种极其不常规）
常规解法，通过递归的方式，这也是很多小伙伴常用的解法，这种解法也非常简单。
"""
斐波那契数列 F(n) = F(n-1) F(n-2)
1、1、2、3、5、8、13、21、34
"""
def fibonacci_digui(self,n):
"""
递归实现斐波那契数列
"""
return self.f2(n)
def f2(self,n):
if n == 1 or n == 2:
return 1
return self.f2(n-1) self.f2(n-2)
下面来个骚操作，会用到线性代数的一些知识。
def fibonacci_matrix(self,n):
"""
矩阵实现斐波那契数列
因为 F(n) = F(n-1) F(n-2) 符合严格递推的格式
故有 ｜F(n),F(n-1)｜ = |F(2),F(1)| * Matrix^(n-2)
而且因为当前项的值只与前两项的值有关，故 Matrix 是 2X2 的矩阵
如何求 Matrix ？，通过代入前几项进行多项式求解
例如：
假设 Matrix = [[a,b],[c,d]]
｜F(3),F(2)｜ = |F(2),F(1)| * [[a,b],[c,d]]
｜F(4),F(3)｜ = |F(3),F(2)| * [[a,b],[c,d]]
将F(1),F(2),F(3),F(4)代入上述式子，
则可以求得 Matrix = [[1,1],[1,0]]
***************************************************
推广：当所求问题可以表达成如下形式时
F(n) = a*F(n-1) b*F(n-2) ... k*F(n-k) 的形式时,
都有｜F(n),F(n-1),...,F(n-(k-1))｜ = |F(k),...,F(2),F(1)| * Matrix^(n-k) 成立
其中 Matrix 维度时 k X k 维，Matrix 需要手工代入求解
"""
a = np.array([1, 1])
b = self.muti_mat(n-2)
res_mat = np.matmul(a, b)
return res_mat[0]
def muti_mat(self,n):
mat = np.array([[1, 1], [1, 0]])
# 初始化单位矩阵
res = np.eye(2)
while n != 0 :
if n & 1 == 1:
res = np.matmul(res,mat)
mat = np.matmul(mat,mat)
n = n >> 1
return res
其中 muti_mat()方法是对矩阵乘法通过位运算等做了些优化
比如 mat^79 = mat^64 * mat^8 * mat^4 * mat^2 * mat^1
64 32 16 8 4 2 1
因为79的二进制表示为 1 0 0 1 1 1 1 ，选取“1”的进行指数相乘。
运行结果如下：
========n:5=========
递归：5
矩阵：5.0
========n:6=========
递归：8
矩阵：8.0
========n:7=========
递归：13
矩阵：13.0
========n:8=========
递归：21
矩阵：21.0
========n:9=========
递归：34
矩阵：34.0
矩阵的方式是不是很骚气～
对作者感兴趣的可以关注wx公众hao，“斜杆小刘”。
