斐波那契数列的求法

旧城等待， 2023-07-25 11:25 13阅读 0赞

**1、斐波那契数列的递归求法（不推荐使用，一般都会超时）：**

原理：把fib(n) 问题的计算拆分成 fib(n-1)和fib(n−2) 两个子问题的计算，并递归，以 f(0) 和 f(1) 为终止条件。

缺点：需要大量的递归计算，用该很容易超时。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70][]

#include<iostream>
    using namespace std;
    
    long fib(int n){
    	if(n==0 || n==1){
    		return n;
    	}
    	return fib(n-1)+fib(n-2);
    }
    
    int main(){
    	int n;
    	cin>>n;
    	cout<<fib(n);
    }

**2、记忆化递归法（以空间换时间的方法）：**

原理：在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。因为fib(n)的n是一定的，无论调用多少次都会得到相同的结果。比如我们求fib(10),如果使用上面的递归方式会多次调用fib(7)。如果我们用一个数组将fib(7)的结果存起来，那么当再需要用fib(7)的时候直接使用就可以了，就不需要重复计算，这时候时间复杂度就得到了极大的优化降到了O(n)。

缺点：因为需要开一个数组，长度为n,空间复杂度较高。但是将这两种一块运行比较，你会发现当n比较大的时候，这两种方法得出结果的时间相差很大。

#include<iostream>
    using namespace std;
    
    //申请一个足够大的数组
    long memo[1000000] = {0};
    long memo2[1000000] = {0};
    
    //写法1: 
    long fib(int n){
    	if(n==0 || n==1){
    		return n;
    	}
    	if(memo[n] != 0){
    		return memo[n];	//如果计算过，就返回 
    	}
    	//没有计算过则继续算 
    	return memo[n] = fib(n-1) + fib(n-2);
    }
    
    //写法2：
    long fib2(int n){
    	if(n==0 || n==1){
    		return n;
    	}
    	if(memo2[n] == 0){
    		memo2[n] = fib2(n-1) + fib2(n-2);
    	}
    	return memo2[n];
    } 
    
    int main(){
    	int n;
    	cin>>n;
    	cout<<fib(n)<<endl;
    	cout<<fib2(n);
    	return 0;
    }

**3、优化后的动态规划算法（以时间换空间的方法）：**

原理：由于斐波那契数列第 n 项只与第 n−1 和第 n−2 项有关，因此只需要初始化三个整形变量 sum,a,b,利用辅助变量 sum 使 a,b 两数字交替前进即可。

时间复杂度：O(n) 原因：计算fib(n)要循环 n 次，每次循环内的计算操作时间复杂度为O(1)

空间复杂度：只需要定义几个变量，因此空间复杂度为O(1)

#include<iostream>
    using namespace std;
    
    long fib(int n){
    	int a = 0,b = 1;
    	long sum;
    	for(int i=0;i<n;i++){
    		sum = a + b;
    		a = b;
    		b = sum;
    	}
    	return a;	//注意应该return a;而不是sum,sum是fib(n+1) 
    }
    
    int main(){
    	int n; 
    	cin>>n;
    	cout<<fib(n);
    	return 0;
    }

**4、循环求余法以及大数的处理：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 1][]

#include<iostream>
    using namespace std;
    
    long fib(int n){
    	int a = 0,b = 1;
    	long sum;
    	for(int i=0;i<n;i++){
    		sum = (a + b)%1000000007;
    		a = b;
    		b = sum;
    	}
    	return a;	//注意应该return a;而不是sum,sum是fib(n+1) 
    }
    
    int main(){
    	int n; 
    	cin>>n;
    	cout<<fib(n);
    	return 0;
    }

--------------------

**相关题目练习：[力扣 面试题10- I. 斐波那契数列][_10- I.]**

class Solution {
    public:
        int fib(int n) {
            int a = 0,b = 1,sum;
    	    for(int i=0;i<n;i++){
    		    sum = (a + b) % 1000000007;
    		    a = b;
    		    b = sum;
    	    }
    	    return a;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20230528/0c77842fadf64569ae2fc0d43e2d9685.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 1]: /images/20230528/85faa1bc210b48849d80fb23852581d7.png
[_10- I.]: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/