Q：斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？
A：因为斐波那契数列在数学和生活以及自然界中都非常有用。
1.斐波那契数列 概念引入
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
数学上，斐波那契数列以递归的形式进行定义：
F 0 = 0 F 1 = 1 F n = F n − 1 + F n − 2 F_{0} = 0\\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2} F0=0F1=1Fn=Fn−1+Fn−2
场景
先来开看看“兔子数列”以及其他数学应用场景！！
1. 1兔子数列
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
1.2排列组合
有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?
更多数学方面知识，请戳：
斐波那契数列
斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？
…
2.数列数学方法解答
2.1兔子繁殖问题
斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
我们不妨拿新出生的一对小兔子分析一下：
第一个月小兔子没有繁殖能力，所以还是一对
两个月后，生下一对小兔对数共有两对
三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对
－－－－－－
依次类推可以列出下表：
幼仔对数=前月成兔对数
成兔对数=前月成兔对数+前月幼仔对数
总体对数=本月成兔对数+本月幼仔对数
可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：
前面相邻两项之和，构成了后一项。
2.2排列组合
2.2.1跨楼梯组合
有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?
这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……
1，2，3，5，8，13……所以，登上十级，有89种走法。
2.2.2掷硬币不连续情形
一枚均匀的硬币掷10次，问不连续出现正面的可能情形有多少种？
答案是:
（ 1 / √ 5 ) ∗ [ ( 1 + √ 5 ) / 2 ] ( 10 + 2 ) − [ ( 1 − √ 5 ) / 2 ] ( 10 + 2 ) = 144 （1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144 （1/√5)∗[(1+√5)/2](10+2)−[(1−√5)/2](10+2)=144
…
3.Python代码实现斐波那契数列
时间复杂度
空间复杂度
通过时间复杂度和空间复杂度评判代码的执行效率。
例如：从规模上来说，如果需要计算F(4)的值，需要进行9次元素操作
设T(n)为计算n的时间复杂度，那么
T ( n ) = T ( n − 1 ) + T ( n − 2 ) + O ( 1 ) T(n) = T(n-1) + T(n-2)+O(1) T(n)=T(n−1)+T(n−2)+O(1)
一般情况，可以得出： T ( n ) < 2 ∗ T ( n − 1 ) + O ( 1 ) T(n)< 2* T(n-1) + O(1) T(n)<2∗T(n−1)+O(1)
粗略估算， T （ n ） < O （ 2 n ） T（n） < O（2^n） T（n）<O（2n），上述代码求解F(n)的计算，它的时间复杂度是$O(2^n)
3.1python特有写法
打印正整数n之内的斐波那契数列
# Python特有， 常规写法def fib(self, n):a = 0b = 1while a <= n:print(a, end=" ", flush=True)a, b = b, a + b # python不借助变量交换两数的值fib(100) # 求n之内的斐波那契数列
时 间 复 杂 度 ： O ( n ) ， 空 间 复 杂 度 ： O ( 1 ) 时间复杂度：O(n)， 空间复杂度：O(1) 时间复杂度：O(n)，空间复杂度：O(1)
3.2递归
打印斐波那契数列前10位数字
# 递归def fibonacci(i):num_list = [0, 1]if i < 2:return num_list[i]elif i >= 2:return (fibonacci(i - 2) + fibonacci(i - 1))print(fibonacci(10))
时 间 复 杂 度 ： O ( n ) ， 空 间 复 杂 度 ： O ( n ) 时间复杂度：O(n)， 空间复杂度：O(n) 时间复杂度：O(n)，空间复杂度：O(n)
3.3类对象
# 迭代的方式class FibIterator(object):"""斐波那契数列迭代器"""def __init__(self, n):""":param n: int, 指明生成数列的前n个数"""self.n = n# current用来保存当前生成到数列中的第几个数了self.current = 0# num1用来保存前前一个数，初始值为数列中的第一个数0self.num1 = 0# num2用来保存前一个数，初始值为数列中的第二个数1self.num2 = 1def __next__(self):"""被next()函数调用来获取下一个数"""if self.current < self.n:num = self.num1self.num1, self.num2 = self.num2, self.num1+self.num2self.current += 1return numelse:raise StopIterationdef __iter__(self):"""迭代器的__iter__返回自身即可"""return selfif __name__ == '__main__':fib = FibIterator(10)for num in fib:print(num, end=" ")
3.4 矩阵解决问题
从定义开始：
F 0 = 0 F 1 = 1 F n = F n − 1 + F n − 2 F_{0} = 0\\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2} F0=0F1=1Fn=Fn−1+Fn−2
转化为矩阵形式
( F n + 1 F n ) = ( 1 1 1 0 ) ∗ ( F n F n − 1 ) \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}* \begin{pmatrix} F_{n}\\ F_{n-1} \end{pmatrix} (Fn+1Fn)=(1110)∗(FnFn−1)
可以得出： ( F n + 1 F n ) ( 1 1 1 0 ) ( F 1 F 0 ) \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}\begin{pmatrix} F_{1}\\ F_{0} \end{pmatrix} (Fn+1Fn)(1110)(F1F0)
我们设定
A = ( 1 1 1 0 ) A=\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} A=(1110)
很显然可以变为如下：
A = ( F 2 F 1 F 1 F 0 ) A=\begin{pmatrix} F_{2}&F_{1}\\ F_{1}&F_{0} \end{pmatrix} A=(F2F1F1F0)
通过数学归纳法可以推出以下公式：
A n = ( F n + 1 F n F n F n − 1 ) = ( 1 1 1 0 ) n A^{n}=\begin{pmatrix} F_{n+1}&F_{n}\\ F_{n}&F_{n-1} \end{pmatrix}= \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}^{n} An=(Fn+1FnFnFn−1)=(1110)n
很显然计算F(n)的值，只需要进行矩阵的n次幂运算，取出结果矩阵第二行第一个元素值即可
时 间 复 杂 度 ： O ( n ) ， 空 间 复 杂 度 ： O ( 1 ) 时间复杂度：O(n)， 空间复杂度：O(1) 时间复杂度：O(n)，空间复杂度：O(1)
这里可以利用快速幂运算求解，假设计算A的N次幂,二阶矩阵的乘法满足结合律
设A,B,C都是任意的二阶矩阵，则
A ( B C ) = ( A B ) C A(BC)=(AB)C A(BC)=(AB)C
我们设定： m = [ n 2 ] m=[\frac{n}{2}] m=[2n]
当n为偶数: A N = A m ∗ A m A^{N}=A^{m}∗A^{m} AN=Am∗Am
当n为奇数: A N = A m ∗ A m ∗ A A^{N}=A^{m}∗A^{m}∗A AN=Am∗Am∗A
相当于 A 6 = A 3 ∗ A 3 ， A 7 = A 3 ∗ A 3 ∗ A A^{6}=A^3∗A^3，A^7=A^3∗A^3∗A A6=A3∗A3，A7=A3∗A3∗A
这样可以减少计算次数，因为 A 6 = A ∗ A ∗ A ∗ A ∗ A ∗ A A6=A∗A∗A∗A∗A∗A A6=A∗A∗A∗A∗A∗A这里有5个乘, A 6 = （ A ∗ A ∗ A ） ∗ （ A ∗ A ∗ A ） A6=（A∗A∗A）∗（A∗A∗A） A6=（A∗A∗A）∗（A∗A∗A） 计算完 A ∗ A ∗ A A*A*A A∗A∗A 得到结果 A 3 A^3 A3，再乘以 A 3 A^3 A3 这里用了3个乘
以下是普通数据的快速幂运算，运算改为矩阵乘法,ret改为单位矩阵即可
def qpow(base, exp):if exp == 0:return 1ret = 1while exp:if exp & 1:ret = ret * basebase = base * baseexp >>= 1return ret
3.5 矩阵再推导
我们可以设定： n = 2 m n=2m n=2m
那么
A 2 m = ( F 2 m + 1 F 2 m F 2 m F 2 m − 1 ) = A m ∗ A m A^{2m}=\begin{pmatrix} F_{2m+1}&F_{2m}\\ F_{2m}&F_{2m-1} \end{pmatrix}=A^{m}*A^{m} A2m=(F2m+1F2mF2mF2m−1)=Am∗Am
已知
A m = ( F m + 1 F m F m F m − 1 ) A^{m}=\begin{pmatrix} F_{m+1}&F_{m}\\ F_{m}&F_{m-1} \end{pmatrix} Am=(Fm+1FmFmFm−1)
所以：
( F m + 1 F m F m F m − 1 ) ∗ ( F m + 1 F m F m F m − 1 ) = ( F 2 m + 1 F 2 m F 2 m F 2 m − 1 ) \begin{pmatrix} F_{m+1}&F_{m}\\ F_{m}&F_{m-1} \end{pmatrix}* \begin{pmatrix} F_{m+1}&F_{m}\\ F_{m}&F_{m-1} \end{pmatrix}= \begin{pmatrix} F_{2m+1}&F_{2m}\\ F_{2m}&F_{2m-1} \end{pmatrix} (Fm+1FmFmFm−1)∗(Fm+1FmFmFm−1)=(F2m+1F2mF2mF2m−1)
计算后可以得出：
( F 2 m + 1 F 2 m ) = ( F m + 1 2 + F m 2 F m ∗ ( F m + 1 + F m − 1 ) ) \begin{pmatrix} F_{2m+1}\\ F_{2m} \end{pmatrix}= \begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(F_{m+1}+F_{m-1}) \end{pmatrix} (F2m+1F2m)=(Fm+12+Fm2Fm∗(Fm+1+Fm−1))
这里需要注意一点 n 需要进行奇偶性判定：
当n为奇数时： m = [ n 2 ] ， n = 2 ∗ m + 1 m=[\frac{n}{2}]，n=2*m+1 m=[2n]，n=2∗m+1 此时， ( F n + 1 F n ) ( F 2 m + 2 F 2 m + 1 ) ( F m + 1 ∗ ( F m + 2 + F m ) F m + 1 2 + F m 2 ) \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}\begin{pmatrix} F_{2m+2}\\ F_{2m+1} \end{pmatrix}\begin{pmatrix} F_{m+1}*(F_{m+2}+F_{m})\\ F_{m+1}^{2}+F_{m}^{2} \end{pmatrix} (Fn+1Fn)(F2m+2F2m+1)(Fm+1∗(Fm+2+Fm)Fm+12+Fm2)
由于 F m + 2 = F m + 1 + F m F_{m+2}=F_{m+1}+F_{m} Fm+2=Fm+1+Fm ，因此，可以推导出
( F n + 1 F n ) = ( F m + 1 ∗ ( F m + 1 + 2 ∗ F m ) F m + 1 2 + F m 2 ) \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} F_{m+1}*(F_{m+1}+2*F_{m})\\ F_{m+1}^{2}+F_{m}^{2} \end{pmatrix} (Fn+1Fn)=(Fm+1∗(Fm+1+2∗Fm)Fm+12+Fm2)当n为偶数时： m = n 2 ， n = 2 ∗ m m=\frac{n}{2}，n=2*m m=2n，n=2∗m，此时
( F n + 1 F n ) = ( F 2 m + 1 F 2 m ) = ( F m + 1 2 + F m 2 F m ∗ ( F m + 1 + F m − 1 ) ) \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} F_{2m+1}\\ F_{2m} \end{pmatrix}= \begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(F_{m+1}+F_{m-1}) \end{pmatrix} (Fn+1Fn)=(F2m+1F2m)=(Fm+12+Fm2Fm∗(Fm+1+Fm−1))
由于 F m + 2 = F m + 1 + F m F_{m+2}=F_{m+1}+F_{m} Fm+2=Fm+1+Fm，因此，可以推导出：
( F n + 1 F n ) = ( F m + 1 2 + F m 2 F m ∗ ( 2 ∗ F m + 1 − F m ) ) \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}= \begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(2*F_{m+1}-F_{m}) \end{pmatrix} (Fn+1Fn)=(Fm+12+Fm2Fm∗(2∗Fm+1−Fm))
所以计算F(N)的值，只需要知道F(n/2+1)和F(n/2)即可
def fib(n):if n < 1:return (1, 0)f_m_1, f_m = fib(n >> 1)if n & 1:return f_m_1 * (f_m_1 + 2 * f_m), f_m ** 2 + f_m_1 ** 2else:return f_m_1 ** 2 + f_m ** 2, f_m * (2 * f_m_1 - f_m)
时 间 复 杂 度 ： O ( log 2 n ) ， 空 间 复 杂 度 ： O ( 1 ) 时间复杂度：O(\log_2 n)， 空间复杂度：O(1) 时间复杂度：O(log2n)，空间复杂度：O(1)
