如何优雅的计算Fibonacci数列

2024-03-23 22:41:10

如何优雅的计算Fibonacci数列

前言
简介
解决方法

递归
迭代
通项公式
矩阵乘法

前言

程序员在面试的时候，算法是经常需要被考察，而算法问题中，又有这么一个登场率非常高的问题，叫做斐波那契数列。
这个问题看似简单，其实里面有很多的门道，从最初级的程序员到算法高手，都能写出来答案。每个人都觉得自己写的对，但是很少人能写出最终完美的答案。这个题目之所以这么受面试官欢迎，主要是有三个特点，一是这个题目的答案简单，是个程序员都能写出来点什么；二是区分度高，不同水平的程序员能写出完全不同的代码，另外最主要的一点是这一题马甲很多，很多应用问题最终都能归结到斐波那契数列。

简介

所谓斐波那契数列，就是一个每一项都等于他前两项和的数列，它最早来自于一个兔子繁殖的应用问题，就是斐波那契这个人，他研究的一个应用问题，所以他有一个别称叫兔子数列。
最原始的兔子问题就是：
假设：一堆成年兔子每年生一对小兔，小兔一年后成年。
提问：一开始有一对小兔，n年后共有多少只兔子？
这个问题里每年的兔子数就是一个斐波那契数列，典型的斐波那契数列呢，
它是 0 1 1 2 3 5 8 13 …
在面试题中很少会直接问求斐波那契数列第n项这样的问题，通常会拿它的其他马甲，比方说兔子问题，还有上一个n级的台阶，每次只能上1阶或2阶，有多少种走法的这样的问题。

解决方法

递归

递归大概是最多人写的了吧，作为一个程序员，很容易用递归的方式解决斐波那契数列

let fibonacci = n ==> 
		n <= 0 ? 0 :n == 1 ? 1 : fibonacci(n-2) + fibonacci(n-1);

这种方法简单易懂，但算到40项左右的时候就已经需要几秒钟的时间了，显然它的性能有很大的问题，这个函数的时间复杂度是指数级的，但我们计算到40项，最多只需要计算40次而已，因此这个问题可以用动态规划的思想做简化，把递归改成迭代。

迭代

let fibonacci = n ==> {
	if(n == 0)
		return 0;
	let a1 = 0,a2 = 1;
	for(let i=1; i < n; i ++){
		[a1, a2] = [a2, a1 + a2];
	}
	return a2;
}

这个算法的时间复杂度是O(n)，从算法的角度，这样的优化已经是极限了。那还有没有更好的解决方案呢，当然是有的。
在组合数学中，对于这样的递推公式，给出了几种通用的数学公式，比如特征方程，母函数，它们可以用于求解斐波那契数列的通项公式。具体的推导过程就不在这里演示了，下面给出通项公式

通项公式

let fibonacci = n ==> 
		(Math.pow((1 + Math.sqrt(5))/2,n)- Math.pow((1- Math.sqrt(5))/2,n)) / Math.sqrt(5);

它的通项公式是二分之一加根号五的n次方减去二分之一减根号五的n次方，再把结果除以根号五，
这个的时间复杂度是O(log(n)),因为我们可以不断用平方去接近n
实现pow运算的过程大概是这样的

let pow = (x , n) => {
	var r = 1;
	var v = x;
	while(n) {
		if(n % 2 == 0){
			r += v;
			n -= 1;
		}
		v = v * v;
		n = n / 2;
	}
	return r;
}

思路是把要求的这个数转成二进制的形式，凡是二进制有1的位，我们就乘以对应次数的x的倍数，
每次循环处理n的二进制的一位。
到这里我们实现了一个O(log(n))时间复杂度的斐波那契数列，这是不是就是最完美的方案呢？
受限于浮点数的精度问题，这个的答案还是要做一次Math.round()才能得到整数，此外浮点数运算在计算机中还是比较耗时的操作，我们可以借助线性代数的矩阵运算，构造出斐波那契数列通项的形式，再结合矩阵乘法，把斐波那契数列转化为矩阵的幂运算

矩阵乘法

从前面的迭代方式我们可以看出，实质上求后面项的过程就是把a , b这两个数，变成 b和 a+ b。
构造矩阵就是
a    b        b    a+b
0    0        0    0
要实现这样的转化我们需要乘上一个这样的矩阵
0    1
1    1
接下来我们就可以吧之前的乘方函数改成矩阵版

let matrix22_mul = (x, y) =>
{
	[x[0][0] * y[0][0] + x[0][1] * y[1][0],x[0][0] * y[0][1] + x[0][1] * y[1][1]],
	[x[1][0] * y[0][0] + x[1][1] * y[1][0],x[1][0] * y[0][1] + x[1][1] * y[1][1]]
}

let matrix22_pow (x, n) => {
	var r = [[1,0],[0,1]];
	var v = x;
	while(n) {
		if(n % 2 == 1){
			r = matrix22_mul(r, v);
			n -= 1;
		}
		v = matrix22_mul(v, v);
		n = n / 2;
	}
	return r;
}

最后就可以顺理成章的写出求斐波那契第n项的代码了

let fibonacci = n => n <= 0 ? 0 :
	matrix22_mul([[0,1],[0,0]],matrix22_pow([[0,1],[1,1]],n -1))[0][1];

码农公寓