星月夜语

什么是斐波那契数列？#

从 0 和 1 开始，后面每个数都是前两个数之和：

1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

递推关系很简单：

斐波那契数列具有如下的形式：

（有些定义里 F(0)=1, F(1)=1，我习惯用上面这套，跟 LeetCode 统一。）

常见用途#

• 自然界：向日葵的螺旋排列、贝壳的螺线、树枝分叉，很多都跟斐波那契数有关
• 算法题：爬楼梯问题、兔子繁殖问题、矩形覆盖问题，本质都是斐波那契
• 黄金分割：相邻两项比值趋近于 1.618，也就是黄金分割比 φ
• 搜索算法：斐波那契搜索，类似二分查找但用斐波那契数分割

通项公式（比奈公式）#

这公式看着唬人，但推导出来挺有意思的：

平时写代码基本用不上，因为浮点数有精度问题，但理解它有助于理解线性递推的求解思路。

矩阵表示#

把递推写成矩阵形式，可以用矩阵快速幂在 O(log n) 时间内算出第 n 项：

递推下去就是：

代码实现对比#

1
def fib(n):
2
    if n <= 1:
3
        return n
4
    return fib(n-1) + fib(n-2)

1
def fib(n):
2
    if n <= 1:
3
        return n
4
    a, b = 0, 1
5
    for _ in range(2, n + 1):
6
        a, b = b, a + b
7
    return b

1
import numpy as np
2

3
def fib(n):
4
    if n <= 1:
5
        return n
6
    base = np.array([[1, 1], [1, 0]], dtype=object)
7
    result = np.linalg.matrix_power(base, n - 1)
8
    return result[0, 0]

小结#

斐波那契数列是个很好的”从小见大”的例子——从简单的递推出发，可以引出递归优化、矩阵运算、甚至生成函数这些更深的数学工具。面试的时候遇到爬楼梯之类的问题，能快速想到斐波那契就已经赢了一半。