求斐波那契数列的三种方法------递归法、for循环法、快速幂矩阵法

àì夳堔傛蜴生んèń 2023-06-27 06:25 10阅读 0赞

### **1 递归法求斐波那契数列，时间复杂度O(n^2),实现代码如下：** ###

#include <iostream>
    using namespace std;
    
    int Fib(int n) {
    	if(n <= 2) return 1;
    	else {
    		return Fib(n-1) + Fib(n-2);
    	}
    	
    } 
    int main(){
    	int n, result;
    	cin >> n;
    	result = Fib(n);
    	cout << result;
    	return 0;
    }

### **2 for循环法求斐波那契数列，时间复杂度O（n)， 其实改进的方法并不复杂。** ###

上述递归代码之所以慢是因为重复的计算太多，我们只要想办法避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查找一下，如果前面已经计算过就不用再重复计算了。 更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f.(....依此类推就可以算出第n项了。很容易理解，这种.思路的时间复杂度是0(n)。实现代码如下:

#include <iostream>
    using namespace std;
    
    long long Fib(int n) {
    	int result[2] = {0, 1};
    	if(n < 2) {
    		return result[n];
    	}
    	long long fibone = 1;
    	long long fibtwo = 0;
    	long long fibN = 0;
    	for(int i = 2; i <= n; i++) {
    	 fibN = fibone + fibtwo;
    	 fibtwo = fibone;
    	 fibone = fibN; 
    	} 
    	return fibN;
    }
    int main(){
    	long long n;
    	cin >> n;
    	cout << "第" << n << "项的斐波那契数为： " << Fib(n);
    	return 0;
    }

### **3 快速幂法求斐波那契数列，时间复杂度O(logN)** ###

**(1)为什么要用快速幂？**

例如：现在有一个题目让你求 ,你可能觉得很简单啊，来一个`for`循环，循环`b-1`次就行了。但是如果b非常大的情况下，那这个做法是非常低效的，时间复杂度大致为 `O(b)`。

当用快速幂之后，时间复杂度为`O(logn)`。

**(2)数的快速幂**

例如我们用快速幂求 。

将指数拆分能够得到如下的结果。  
学过进制转换看到11拆开的样子肯定会很眼熟，其实这里就是跟二进制有关。

11的二进制为`1011` ,我们只需要把11的二进制代码中为1的位数对应的2^n累乘起来即可，如2^11=2^8\*2^2\*2,对应二进制数中的第0、1、3位(从右往左数）均为1，故把它们累乘起来即可得到2^11。

这样一来，我们求2^11就不需要算10次了，现在三次就够了。

实现代码如下：

// 利用快速幂求x^n 
    #include <iostream>
    using namespace std;
    
    int pow(int x, int n) {
    	int ans = 1, base = x; //base 为底数， ans为最后累乘的结果x^n 
    	while(n != 0) {
    		if(n&1 != 0) {
    			ans *= base;
    		}
    		base *= base;
    		n >>= 1; // 等价于把n右移一位并吧结果赋给n 
    	}
    	return ans;
    }
    int main(){
    	int x, n;
    	cout << "请输入底数："; 
    	cin >> x;
    	cout << endl;
    	cout << "请输入指数："; 
    	cin >> n;
    	cout << x << "^" << n << "=" << pow(x, n); 
    	return 0;
    }

**（3）矩阵的快速幂**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70][]

于是我们得到如下公式： 其中Fn则对应结果矩阵result\[0\]\[1\]的值

![20200105112759648.png][]

利用矩阵的快速幂书写如下代码：

//用矩阵快速幂求斐波那契数列
    #include <iostream>
    #include<cstring>
    using namespace std;
    
    struct Matrix { //定义矩阵结构体 
    	int a[2][2];
    }; 
    
    Matrix muliMatrix(Matrix x, Matrix y) { //求两个矩阵相乘
    	Matrix result; //结果矩阵result 
    	memset(result.a, 0, sizeof(result.a)); //将结果矩阵的元素全部初始化为0
    	for(int i = 0; i < 2; i++) {
    		for(int j = 0; j < 2; j++) {
    			for(int k = 0; k < 2; k++){
    				result.a[i][j] += x.a[i][k] * y.a[k][j]; //矩阵的乘法 
    			}
    		}
    	} 
    	return result; 
    } 
    
    int matrixPow(int n) { //快速幂求斐波那契数列
    	Matrix res, c;
    	memset(res.a, 0, sizeof(res.a));  
    	for(int i = 0; i < 2; i++) {
    		res.a[i][i] = 1; //将res初始化为单位矩阵，因为任何矩阵和单位矩阵相乘都是它本身 
    	} 
    	c.a[0][0] = 1; //构造斐波那契矩阵 
    	c.a[0][1] = 1;
    	c.a[1][0] = 1;
    	c.a[1][1] = 0;
    	
    	while(n) {
    		if(n&1 != 0){ //这里和求x^n的快速幂类似 
    			res = muliMatrix(res, c);
    		}
    		c = muliMatrix(c, c);
    		n >>= 1; // 等价于把n右移一位并把结果赋给n即n=>>1 
    	} 
    	return res.a[0][1]; //由于斐波那契第n项Fn对应结果举证中res.a[0][1]的值 
    }
    
    int main(){
    	int n;
    	cout << "请输入斐波那契数列的项数: ";
    	cin >> n;
    	cout << endl;
    	cout << "第" << n << "项斐波那契数列的值=" <<  matrixPow(n);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200105093802921.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw,size_16,color_FFFFFF,t_70
[20200105112759648.png]: https://img-blog.csdnimg.cn/20200105112759648.png