01先把问题说具体
F₀=0、F₁=1、Fₙ=Fₙ₋₁+Fₙ₋₂,要计算很大的 n,能否不逐项填 n 个状态?
02一步步得到方法
把需要记住的状态放进向量
令 sₖ=[Fₖ₊₁,Fₖ]ᵀ,则 sₖ₊₁=[[1,1],[1,0]]·sₖ。第一行把前两项相加,第二行把原第一项向下搬移。矩阵的每一行都对应下一状态的一条计算规则。
反复 n 次就是 sₙ=Mⁿs₀,s₀=[1,0]ᵀ。矩阵乘法有结合律,因此可用快速幂;不需要交换律,只要乘法顺序保持正确。
适用范围是固定线性转移
若递推包含 max、非线性函数或每步使用不同矩阵,不能直接套一个固定 M 的幂。可扩展常数项时增加一个恒为 1 的状态分量,但应先逐项验证矩阵乘出来的式子。
指数 0 返回单位矩阵 I,因为不推进状态。矩阵尺寸 d 决定一次乘法成本,不能仅写 O(log n) 而省掉 d³。
状态向量的方向决定矩阵写法
先规定状态用列向量还是行向量。例如列向量 [F(n+1),F(n)]ᵀ 左乘转移矩阵得到下一状态;换成行向量时矩阵位置和索引也要相应调整。
重复相同线性转移才等价于矩阵幂。若每一步矩阵随时间变化,不能简单求某个固定矩阵的 k 次幂;零次幂应是单位矩阵,保证不执行转移时原状态不变。
03把一个小例子完全算清楚
M=[[1,1],[1,0]],求 F₅。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| M² | [[2,1],[1,1]] | 推进两步 |
| M⁴ | [[5,3],[3,2]] | 再次平方 |
| M⁵=M⁴M | [[8,5],[5,3]] | 取第 0 行第 1 列得 5 |
窄屏可左右滑动表格,阅读完整计算与理由。
F₅=5;矩阵还同时保留了相邻 Fibonacci 项的信息。
04为什么这个方法成立
- 一阶转移矩阵按行准确实现下一状态公式。
- 矩阵幂的乘法次数合成相应步数。
- 快速幂不变量保持累计矩阵与剩余幂的乘积为目标 Mⁿ,结束后得到准确转移。
05把推导翻译成代码
Python · 可独立运行的教学实现
def multiply(a,b):
return [[sum(a[i][k]*b[k][j] for k in range(len(b)))
for j in range(len(b[0]))] for i in range(len(a))]
def matrix_power(a,n):
assert n >= 0 and all(len(row)==len(a) for row in a)
size = len(a)
result = [[int(i==j) for j in range(size)] for i in range(size)]
while n:
if n & 1:
result = multiply(result,a)
a = multiply(a,a)
n //= 2
return result
def fibonacci(n):
return matrix_power([[1,1],[1,0]],n)[0][1]逐个理解关键决定
int(i==j)- 构造单位矩阵,主对角线为 1,其他为 0。
multiply(result,a)- 矩阵乘法不交换,保持累积方向,不按标量直觉任意换顺序。
06时间、空间与实现范围
普通 d×d 矩阵乘法 O(d³),总 O(d³ log(n+1)),矩阵工作存储 O(d²)。
Fibonacci 本身有指数增长的数值,若不取模,大整数乘法不能视为常数;常见应用在每次乘加后按指定模数取模。
07改变条件,检查哪里会出错
把 F₀、F₁ 的状态顺序写反
先实际乘一次,检查输出是否确实变为 [F₂,F₁]。
把矩阵元素逐项求幂
A² 表示 A×A 的矩阵乘法,通常完全不同于每个元素平方。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
n=0 返回什么矩阵?
需要一点提示
零次转移。
查看解析与答案
单位矩阵,F₀ 对应非对角元素 0。
Fₙ=2Fₙ₋₁+3Fₙ₋₂ 的转移矩阵?
需要一点提示
第一行写系数,第二行搬移。
查看解析与答案
[[2,3],[1,0]],状态顺序保持 [Fₖ₊₁,Fₖ]。
如果递推每步还加 5 怎么扩展?
需要一点提示
增加恒定分量。
查看解析与答案
使用 [Fₖ₊₁,Fₖ,1]ᵀ,第一行 [2,3,5],第二行 [1,0,0],第三行 [0,0,1]。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂