工学1号馆

home

Fibonacci数列算法

Wu Yudong    July 22, 2016     Algorithm   690   

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

No comments yet.
To verify that you are human, please fill in "七"(required)