斐波那契数列（Fibonacci Sequence）
斐波那契数列的几种求法
写此文是恰好学校校队第一次选拔练习题里有，当时就有些好奇其他解法，恰好结合y总的分享和大家分享几种斐波那契数列的求法，其中的解法涉及很多算法思想，很有启发性。
题目：定义$a_0=1，a_1=1，a_n=a_{n-1}+a_{n-2}$，求$a_n$ % $10^9+7$是多少。
法一：递归
利用递归进行简单的计算过程模拟。
写递归的三个要点：
- 确定递归参数：递归参数为第n个斐波那契数。
- 确定递归终点：n-1与n-2会返回第1个和第2个斐波那契数，所以当n=0和1时初始化斐波那契数列为1.
- 递归从最后一层开始计算。
但是很明显能看出这个算法时间复杂度较高，为$O(n^2)$很容易TLE。
#include <iostream>
const int MOD = 1000000007;
int f(int n)
{
if (n <= 1) return 1;
return (f(n - 1) + f(n - 2)) % MOD;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n-1));
}
法二：记忆化搜索
我们发现，在法一中，假设n = 5，那么会重复计算f(2)、f(1)、f(0)，为了避免重复计算，我们将计算好的值存储到数组中，构成记忆化搜索，如此，每一个f(n) 就只计算了一次，故而时间复杂度为$O(n)$。
但这个方法也有缺点，和法一一样，容易爆栈。计算规模大概在$n=10^5$级别。
#include <iostream>
const int MOD = 1000000007,N = 1000000;
int st[N];
int f(int n)
{
if (st[n]) return st[n];
if (n <= 1) return 1;
st[n] = f(n - 1) + f(n - 2);
st[n] %= MOD;
return st[n];
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n-1));
}
法三：递推
其实就是暴力把前n 个数的斐波那契数也算出来，这样自然就能算出第n 个斐波那契岁数了。
但是如此做法空间复杂度会极高，消耗内存极大，很可能被程序规定大小所限制。
#include <iostream>
const int MOD = 1000000007,N = 100000000;
int st[N];
int f(int n)
{
st[0] = st[1] = 1;
for (int i = 2; i <= n; i++)
st[i] = (st[i - 1] + st[i - 2])%MOD;
return st[n];
}
int main()
{
int n;
scanf_s("%d", &n);
printf("%d", f(n-1));
}
法四：递归 + 滚动数组
观察一下公式：f(n) = f(n-1) + f(n-2)，很容易得出对于f(n+1) = f(n) + f(n-1)，所以可以想到使用滚动数组去优化我们的空间复杂度，对于每一个f(n)，我们只需要两层数据，上一层的结果是我们的第一个数据，第一个加数是我们的第二个数据。从而写出时间复杂度$O(n)$，空间复杂度$O(1)$的代码。
#include <iostream>
const int MOD = 1000000007;
int st[N];
int f(int n)
{
int x, y, z;
x = y = z = 1;
for(int i = 1;i<n;i++)
{
z = (x + y) % MOD;
y = x;
x = z;
}
return z;
}
int main()
{
int n;
scanf_s("%d", &n);
printf("%d", f(n-1));
}
法五：矩阵运算 + 快速幂
关于快速幂的学习参考此文：快速幂
我们首先定义矩阵： \(M_n=\begin{bmatrix} a_{n}&a_{n-1} \end{bmatrix} \quad n\geq 1\)
根据已知的信息，我们可以推出通式： \(M_n = M_{n-1}\times A\) \(A = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\)
（你不信可以试试，因为刚看到我也不信 XD）
由此，我们可以得出： \(M_n=M_1\times A^{n-1}\)
我们的答案太大需要对MOD取模，因为矩阵的结合性，我们可以利用快速幂先求$A^{n-1}$%$P$
其实这题代码上的难点在于对矩阵运算的模拟实现，对于稍微复杂的代码建议分块实现且写一下伪代码防止思维逻辑的错误。
#include <iostream>
const int MOD = 1000000007;
//模拟矩阵X乘
void matrix_mul(int a[][2],int b[][2],int M[][2])
{
int temp[][2] = { {0,0},{0,0} };
for(int i = 0;i<2;i++)
{
for(int j = 0;j<2;j++)
{
for(int k = 0;k<2;k++)
{
long long x = temp[i][j] + static_cast<long long>(a[i][k]) * b[k][j];
temp[i][j] = x % MOD;
}
}
}
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
M[i][j] = temp[i][j];
}
int f(long long n)
{
if (n < 2) return 1;
int M_0[2] = { 1,1 };
int A[][2] = { {1,1},{1,0} };
//将答案初始化为单位矩阵I
int res[][2] = { {1,0},{0,1} };
long long k = n - 1;
while(k)
{
if (k & 1) matrix_mul(res, A, res);
matrix_mul(A, A, A);
k >>= 1;
}
int M_n[2] = { 0,0 };
for(int i = 0;i<2;i++)
{
for(int j = 0;j<2;j++)
{
long long x = M_n[i] + static_cast<long long>(M_0[j]) * res[j][i];
M_n[i] = x % MOD;
}
}
return M_n[0];
}
int main()
{
//从下标为1开始计算
long long n;
scanf_s("%lld", &n);
printf("%d", f(n-1));
}