原文来自我的博客: 常青园晚 の 博客
在我的博客上取得更好的阅读体验
原文发布日期: 2021-09-04
同步日期: 2022-02-11

引子

现在, 你有一个递推式, 或者称之为递归关系, 如下:
$$f(n)=f(n-1)+f(n-2)$$
$$f(1)=f(2)=1,n>=1$$
聪明人一看, 啊这不是斐波那契数列吗, 这我会!!!
于是, 我们的聪明人同学很快啊, 很快写出了这样的代码:

循环法

// C++
#include <bits/stdc++.h>
using namespace std;
int main(){long long n, fab[10001];fab[1] = 1, fab[2] = 1;for(int i = 3; i <= 10000; ++ i){fab[i] = fab[i - 1] + fab[i - 2];}scanf("%d", &n);printf("%d\n", fab[n]);return 0;
} // 此代码计算到 f(79) 就出现了越界的情况

// CSharp
using System;
namespace Faboric
{class Program{static void Main(string[] args){long[] fab = new long[10001];fab[1] = 1;fab[2] = 1;for (int i = 3; i < 10001; ++ i){fab[i] = fab[i - 1] + fab[i - 2];}int n = int.Parse(Console.ReadLine());Console.WriteLine(fab[n]);Console.ReadLine();}}
} // 此代码计算到 f(197) 出现越界

// Python
fab = []
fab.append(1)
fab.append(1)
n = int(input("n:"))
for i in range(3, n + 1, 1):fab.append(fab[len(fab) - 1] + fab[len(fab) - 2])
print(fab[n - 1])
# 此代码理论上可以无限计算, 本人 python 学的不好, 计算到 f(500000) 时出现明显卡顿

这三个代码都使用了循环来计算斐波那契数列, 聪明人同学看了一眼书本目录, 又立马大喊道:“老师, 我还可以用递归写!!!”
于是, 他马上又写出了这样的代码:

递归法

// C++
#include <bits/stdc++.h>
using namespace std;
long long f(int n){if(n == 1 || n == 2) return 1;else return f(n - 1) + f(n - 2);
}
int main(){int n;scanf("%d", &n);printf("%lld\n", f(n));return 0;
}

此代码计算到 f(48) 时等待了约莫 16 秒, 因为这个递归会完全忽略上一轮已经计算过的, 造成时间复杂度高昂
配合记忆化的思想, 这个代码可以这么写:

// C++
#include <bits/stdc++.h>
using namespace std;
long long via[100001];
long long f(int n){if(n == 1 || n == 2) return 1;else{long long tmp = (via[n - 1] == 0 ? f(n - 1) : via[n - 1]) + (via[n - 2] == 0 ? f(n - 2) : via[n - 2]);via[n] = tmp;return tmp;}
}
int main(){via[1] = via[2] = 1;int n;scanf("%d", &n);printf("%lld\n", f(n));return 0;
}

此时 f(48) 已经降到了 0.2 秒左右, 已经很快了, 同时运行到 f(93) 才出现越界的情况:

92
7540113804746346429--------------------------------
Process exited after 0.6031 seconds with return value 0
请按任意键继续. . .

// CSharp
using System;
namespace Faboric
{class Program{static long[] via = new long[100001];static long f(int n){if(n == 1 || n == 2) return 1;else{long tmp = (via[n - 1] == 0 ? f(n - 1) : via[n - 1]) + (via[n - 2] == 0 ? f(n - 2) : via[n - 2]);via[n] = tmp;return tmp;}}static void Main(string[] args){for (int i = 0; i < 100001; ++i) via[i] = 0;via[1] = 1;via[2] = 1;int n = int.Parse(Console.ReadLine());Console.WriteLine(f(n));Console.ReadLine();}}
} // 依旧是计算到 f(197) 出现越界

// Python
via = []def f(n):if(n == 1 or n == 2): return 1else:tmp = (f(n - 1) if via[n - 1] == 0 else via[n - 1]) + (f(n - 2) if via[n - 2] == 0 else via[n - 2])via[n] = tmpreturn tmpif __name__ == "__main__":n = int(input("n:"))for i in range(0, n + 1, 1):via.append(0)print(f(n))
# 同样地使用记忆化的思想, python 的递归也可以达到较高的速度

终于, 老师开口了:“骚年, 你的计算机程序设计基础学的还是可以的, 但是你的数学, 可就没那么好了”
于是, 老师开始了今天的课程

特征方程

特征方程详解:

对于任意一个递归关系如果满足:
$$F(n)=a_{1}F(n-1)+a_{2}F(n-2)+\cdots +a_{k}F(n-k),a_k\ne 0$$
则称此递归关系为 k 阶的线性常系数齐次递归关系

如果你的递归关系符合📎线性常系数齐次递归关系, 那么你的递归关系就可以简单地求出一个通项公式, 也就是你的递推式的通解
所谓的线性常系数齐次递归关系就是指:

1. 线性 : 所有的 f 都是一次的
2. 常系数 : $c_1$, $c_2$, $\dots$ $c_n$ 这些系数都是常数
3. 齐次 : 所有的 f 的次数都是相同的
   而特征方程的一般形式是:
   $$f(n)=c_1{x}_1^n+c_2{x}_2^n+\cdots +c_n{x}_n^n$$
   所有的这些 $x_1$ , $x_2$, $\dots$ $x_n$ 这些就叫做特征根
   我们只需要通过原递归关系解出这些特征根, 再通过一些已知值解出 $c_1$, $c_2$ 这些东西, 那么原递归关系的通解就出来了

使用特征方程解出斐波那契数列的通项公式

以斐波那契为例:
$$f(n)=f(n-1)+f(n-2)n\in N$$
$$\Rightarrow x^n=x^{n-1}+x^{n-2}$$
移项, 提取公因式得:
$$x^{n-2}(x^2-x-1)=0$$
由斐波那契的性质可知:
$$f(n)\ne 0$$
$$\therefore x^{n-2}\ne 0$$
$$\therefore x^2-x-1=0$$
解得:
$$x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}$$
带入特征方程, 得:
$$f(n)=c_1{(\frac{1+\sqrt{5}}{2})}^n+c_2{(\frac{1-\sqrt{5}}{2})}^n$$
再带入 f(0) = f(1) = 1,

这里有的同学可能就要问了, 不是 f(1) = f(2) = 1 嘛
其实是这样的, 当 n 为 0 时 可以得到一个方程为 $c_1+c_2=1$ 方便计算
等计算完之后再把等式右边的所有 n 都减一就恢复成了 f(1) = f(2) = 1 了

得到方程组:
$$\{\begin{array}{l}{c}_1+c_2=1\\ \\ c_1(\frac{1+\sqrt{5}}{2})+c_2(\frac{1-\sqrt{5}}{2})=1\\ \end{array}$$
解得:
$$\{\begin{array}{l}{c}_1=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})\\ \\ c_2=-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})\\ \end{array}$$
带回到特征方程, 得到完整的通解表达式:
$$f(n)=\frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})}^{n+1}-\frac{1}{\sqrt{5}}{(\frac{1-\sqrt{5}}{2})}^{n+1}$$
对其进行复原到 f(1) = f(2) = 1 的操作, 得:
$$f(n)=\frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})}^n-\frac{1}{\sqrt{5}}{(\frac{1-\sqrt{5}}{2})}^n$$
简单验算可以看到这个公式是正确的
将其转化为等效的代码时只需注意一下精度的问题, 别整溢出了

实战演练

打开📎信息学奥赛一本通官网, 关于 Pell 数列 这题就是应用特征根的绝佳之处
虽然我用这个法子没过😭
关于这题的大致情况是, 对于每个输入的 k , 要求 f(k) 的值 mod 32767 的值
对于 f(k) 定义如下:
$$f(k)=2f(k-1)+f(k-2),k>2且k\in N$$
且已知: $f(1)=1,f(2)=2$
咋一看, 与斐波那契数列如同一个模子刻出来的, 再仔细一看, 完全符合线性常系数齐次递归关系的定义, 于是, 我们有了以下求解过程:
$$\begin{array}{r}f(n)=2f(n-1)+f(n-2)\\ \\ \\ \\ \Rightarrow x^n=2x^{n-1}+x^{n-2}\\ \\ \\ \\ \therefore x^n-2x^{n-1}-x^{n-2}=0\\ \\ \\ \\ x^{n-2}(x^2-2x-1)=0\\ \\ \\ \\ \because x^{n-2}\ne 0\\ \\ \\ \\ \therefore x^2-2x-1=0\\ \end{array}$$
$$\Rightarrow \{\begin{array}{l}{x}_1=1+\sqrt{2},\\ \\ \\ \\ x_2=1-\sqrt{2}\\ \end{array}$$
$$\therefore f(n)=c_1(1+\sqrt{2}{)}^n+c_2(1-\sqrt{2}{)}^n$$
令 $f(0)=1,f(1)=2$
则:
$$\{\begin{array}{l}{c}_1+c_2=1,\\ \\ \\ \\ c_1(1+\sqrt{2})+c_2(1-\sqrt{2})=2\\ \end{array}$$
解得:
$$\{\begin{array}{l}{c}_1=\frac{2+\sqrt{2}}{4}\\ \\ \\ \\ c_2=\frac{2-\sqrt{2}}{4}\\ \end{array}$$
再考虑复原 $f(0)=1,f(1)=2$ 到 $f(1)=1,f(2)=2$ 的操作:
最终, 通解为:
$$f(n)=\frac{2+\sqrt{2}}{4}(1+\sqrt{2}{)}^{n-1}+\frac{2-\sqrt{2}}{4}(1-\sqrt{2}{)}^{n-1}$$

参考资料

《程序员数学从零开始》，孙博(@我是8位的)

完