Fibonacci数列是一个非常美丽、和谐的数列，有人说它起源于一对繁殖力惊人、基因非常优秀的兔子，也有人说远古时期的鹦鹉就知道这个规律。每一个学理工科的学生都知道斐波那契数列，斐波那契数列由如下递推关系式定义：
本文地址：http://wuyudong.com/2016/07/22/2237.html，转载请注明源地址。
F(0)=0, F(1)=1, n>1时，F(n)=F(n-1)+F(n-2)。
每一个上过算法课的同学都能用递归的方法求解斐波那契数列的第n+1项的值，即F(n)。
int Fibonacci(int n)
{
if (n <= 0) return 0;
else if (n == 1) return 1;
else return Fibonacci(n - 1) + Fibonacci(n - 2);
}
我们的问题是：有没有更加优化的解法？
解法一：递推关系式的优化
例如在计算F[5]=F[4]+F[3]的时候，计算F[4]需要计算F[3]，后面还需要计算一次F[3]，存在重复计算问题，可以使用变量存储已计算过的项。这样可以减少计算次数，代码如下：
int fibonacci(int n)
{
int i, s, t, ret;
s = 0, t = 1, ret = 0;
if (n == 0 || n == 1)
return n;
for (i = 2; i <= n; i++) {
ret = s + t;
s = t;
t = ret;
}
return ret;
}
解法二：求通项公式
如果我们知道一个数列的通项公式，使用公式来计算会更加容易。
特征方程为：x2=x+1，有两个特征根x1，x2。
则通项为F(n)=Ax1n+Bx2n，其中A，B可以通过F(0)和F(1)计算出来。
通过通项公式，我们可以在O(1)时间内求出F(n)。但公式中引入了无理数，所以不能保证结果的精度。
int Fibonacci(int n) {
double s = sqrt(5);
// floor 返回小于或者等于指定表达式的最大整数
return floor((pow((1 + s) / 2, n) - pow((1 - s) / 2, n)) / s + 0.5);
}
解法三：分治策略
存在2*2的矩阵A，使得：
[Fn Fn-1] = [Fn-1, Fn-2]*A
通过递推可以求得A={{1, 1}{1, 0}}
且：[Fn Fn-1] = [Fn-1, Fn-2]*A = [Fn-2, Fn-3]*A2= … = [F1, F0]*An-1
剩下的问题就是求解矩阵A的方幂。
核心代码如下：
struct Mat {
double mat[N][N];
};
Mat Mut(Mat a, Mat b) //计算矩阵的乘积
{
Mat c;
memset(c.mat, 0, sizeof(c.mat));
int i, j, k;
for (k = 0; k < n; ++k) {
for (i = 0; i < n; ++i) {
if (a.mat[i][k] <= 0)
continue;
for (j = 0; j < n; ++j) {
if (b.mat[k][j] <= 0)
continue;
c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
}
}
}
return c;
}
Mat matrix_pow(Mat a, int k) //计算矩阵的k次幂
{
Mat c;
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
c.mat[i][j] = (i == j);
for (; k; k >>= 1) {
if (k & 1)
c = c * a;
a = a * a;
}
return c;
}
Comments