Fibonacci Sequence

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

0 递归

斐波那契数列定义：

$F(n)=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
F(n-1)+F(n-2), & n>1
\end{matrix}\right.$

递归解法最直观，但是复杂度也最高：$O(2^n)$

int Fibonacci(int n)
{
if (n <= ) //细节可以处理非法输入
return ;
else if ( == n)
return ;
return Fibonacci(n - ) + Fibonacci(n - );
}

为了避免重复计算，可以将每一步计算得到的$F(i)$存起来，这样的话时间复杂度降为$O(n)$，但空间复杂度升为$O(n)$。

1 通项

求解通项的方法有好几种，下面展示一种用线性代数求解的方法：

斐波那契数列的递推公式是二阶差分方程，先用一点小技巧将其化为一阶：

$$
\begin{cases}
F_{k+2}=F_{k+1}+F_{k}& \text{}\\
F_{k+1}=F_{k+1}& \text{}\\
\end{cases}$$

我们令$u_k=\begin{bmatrix}
F_{k+1}\\
F_{k}\\
\end{bmatrix}$，那么$u_{k+1}=\begin{bmatrix}
F_{k+2}\\
F_{k+1}\\
\end{bmatrix}=\begin{bmatrix}
1 & 1\\
1 & 0\\
\end{bmatrix}u_k$。

矩阵$A=\begin{bmatrix}
1 & 1\\
1 & 0\\
\end{bmatrix}$，令$det(A-\lambda I)=\lambda^2-\lambda-1=0$，求得$\lambda=\frac{1\pm \sqrt5}{2}$，对应于两个特征值的特征向量为$x_1=\begin{bmatrix}
\lambda_1\\
1\\
\end{bmatrix},x_2=\begin{bmatrix}
\lambda_2\\
1\\
\end{bmatrix}$。
求得特征值和特征向量后，我们将$u_0=\begin{bmatrix}
F_1\\
F_0\\
\end{bmatrix}=\begin{bmatrix}
1\\
0\\
\end{bmatrix}=c_1x_1+c_2x_2$，解得$c_1=-\frac{1}{\sqrt5}, c_2=\frac{1}{\sqrt5}$

故

$u_k=S\Lambda^{k}c=\begin{bmatrix}
c_1\lambda_1^{k+1}+c_2\lambda_2^{k+1}\\
c_1\lambda_1^{k}+c_2\lambda_2^{k}\\
\end{bmatrix}$

所以通项公式可以表示为$F(n)=C_1\lambda_1^n+C_2\lambda_2^n$。

故斐波那契数列的通项公式为：
$F(n)=\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n]$

用公式求解的复杂度为$O(1)$，但是由于无理数在计算机中的存储不是精确的，所以结果的精度很难保证。

2 分治

通过矩阵形式的递推：

$$\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix}=\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}\begin{bmatrix}
F(n-1)\\
F(n-2)
\end{bmatrix}$$

不断向下递推，可以得到：

$$\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix}={\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}}^{n-1}\begin{bmatrix}
F(1)\\
F(0)
\end{bmatrix}$$

接下来就是求解矩阵的高次方，通过快速幂（https://baike.baidu.com/item/快速幂/5500243?fr=aladdin）可以在$O(logn)$时间内进行计算：
整数的快速幂代码：

int QuickPow(int a,int n)
{
int ans = ;
while (n)
{
if (n & )
ans *= a;
a *= a;
n >>= ;
} return ans;
}

// 递归版本
int raise(int base, int exp) {
if (exp == )
return ;
int half = raise(base, exp / );
if (exp % )
return base * half * half;
else
return half * half;
}

将传入的参数改为矩阵，乘法改为矩阵乘法，就可以得到矩阵快速幂：

以二阶矩阵为例，求解斐波那契数列：

#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; struct Matrix {
int a[][];
}base,ans; Matrix multi(Matrix a, Matrix b)
{
Matrix res;
for (int i = ; i < ; i++) //第i行
{
for (int j = ; j < ; j++) //第j列
{
res.a[i][j] = ;
for (int k = ; k < ; k++)
res.a[i][j] += a.a[i][k] * b.a[k][j];
}
} return res;
} Matrix QuickPow(int n)
{
base.a[][] = base.a[][] = base.a[][] = ;
base.a[][] = ; //初始化矩阵 //结果矩阵初始化为单位阵
ans.a[][] = ans.a[][] = ;
ans.a[][] = ans.a[][] = ; while (n)
{
if (n & )
{
ans = multi(ans, base);
}
base = multi(base, base);
n >>= ;
} return ans;
} int main()
{
int n;
cin >> n; QuickPow(n);
cout << ans.a[][] << endl; return ;
}