斐波那契据数列的几种计算机解法

斐波那契数列的几种计算机解法

斐波那契数列传说起源于一对非常会生的兔子。定义：

这个数列有很多奇妙的性质（比如 F(n+1)/F(n) 的极限是黄金分割率），用计算机有效地求解这个问题的解是一个比较有意思的问题，本文一共提供了4种解法。

解法一：递归

这是最最最直观的想法，是每个人都能编写的简单程序，优点是非常明显的：简单易懂，清晰明了。但是缺点就是效率非常低，时间复杂度是指数级的。举个例子，比如要计算F(5)，那么就要就算F(4)+F(3)，而在计算F(4)的时候又要计算F(3)，导致了 F(3)的重复计算，如果n越来越大，重复的计算量是无比巨大的，这就是瓶颈所在。

代码：

int F(int n)
{
	if(n <= 0)
		return 0;
	else if(n == 1)	
		return 1;
	else
		return F(n-1) + F(n-2);
}

那么怎么克服这个问题？这就引出了解法二。

解法二：动态规划

解法一的缺点是因为重复计算，那么我们只需要把一些已经计算过的答案存放起来，那这个缺点就解决了。我们用一维数组来实现，比如 F(5)就存放在数组下标为5的数据单元里。

代码：

int F(int n)
{
	if(n <= 0)
	if(n == 1)
		return 1;
		return 0;

	int* ans = new int[n+1];
	ans[0] = 0;
	ans[1] = 1;

	for(int i=2; i<=n; i++)
		ans[i] = ans[i-1] + ans[i-2];
	
	int tmp = ans[n];
	delete[] ans;
	return tmp;
}

这个算法的时间复杂度是 O(n)，空间复杂度也是O(n)。复杂度来到了线性，这是我们所高兴的，但是，是否还有比线性更好的复杂度？

解法三：求解通项公式

如果我们知道了通项公式，那么我们就能在 O(1)的时间内得到F(n)。这是一个完美的时间复杂度。

这里只介绍一种求解通项公式的技巧——矩阵。矩阵作为一个强大的数学工具有太多不为人知的应用。当然还有其它方法，比如高中数学竞赛里面的特征方程，有兴趣的读者可以自行搜索一下。

我们很容易发现：

所以剩下的问题就是只要求出了就求出了F(n)。

求这个矩阵的 n次方的解法也有很多，这里介绍一种方法——相似对角化。

令

于是

上述方程的解为

 

于是解得

 的基础解系为

的基础解系为

所以令

 

我们有：

所以,

 

两边取n次方，我们得到：

最后，做矩阵运算（实际上我们只需要 Aⁿ 里左下角的数据），便可以得到：

通项公式的计算就完成了。（推导过程需线性代数基础）

时间复杂度是完美了，那么有没有缺点呢？当然有，公式里引入了无理数，所以不能保证运算结果的精度。

解法四：分治

解法三的缺点是精度无法保证，那么我们自然就想到，然计算机自己去计算，进行n-1次矩阵乘法不就行了。这是最直观的想法，虽然是线性的，但复杂度还是不令人满意，有没有更好的复杂度？比如 log₂ (n)？答案是有的。

先来看一个背景知识：一个十进制正数 n的用二进制表示要用floor( log₂(n) )+1 位。(floor(x)返回不大于 x的最大整数)

用二进制方式表示 n：

所以

如果能得到的值就可以经过 log₂ (n)次乘法得到。

显然可以通过递推得到：

代码：

Class Matrix;	//假设已经实现了矩阵类

Matrix MatrixPow(const Matrix &m, int n)	//计算m的n次方
{
	Matrix result = Matrix::identity;	//单位矩阵
	Matrix tmp = m;
	for(; n; n >>= 1)
	{
		if(n & 1)
			result *= tmp;
		tmp *= tmp;
	}
}


int F(int n)
{
	Matrix an = MatrixPow(A, n);
	return F1*an(1,0) + F0*an(1,1);		//an(1,0)表示an的第1行第0列的元素
}

时间复杂度仅为O(log₂ (n))。