算法-斐波那契数列

「爱情、让人受尽委屈。」 2022-06-10 13:07 308阅读 0赞

**题目：**  
写一个函数，输入为n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列定义如下：  
![这里写图片描述][SouthEast]

**解题思路：**  
斐波那契问题是个非常经典的递归问题，比如我们想要求得f(8)，f(8)=f(7)+f(6)，而f(7)=f(6)+f(5)，……，直到n=1或n=0时递归结束，那么我们很容易就编出来下面的代码：

#include "iostream"    
    using namespace std;
    long long Fibonacci(unsigned int n)
    {
        if(n <= 0)
            return 0;
    
        if(n == 1)
            return 1;
    
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    int main()
    {
        int sum = Fibonacci(8);
        cout<<sum<<endl;
        getchar();
        return 0;
    }

但是递归真的适合这个问题吗？我们可以分析下上面的代码，n=8时，需要求f(7)和f(6)，而求f(7)时需要求f(6)和(5)，所以这就造成了相求f(8)，但是递归的深度却远远不止8层，在执行`return Fibonacci(n - 1) + Fibonacci(n - 2);`代码时，递归总是先进入左边的函数，当左边函数满足退出条件时（n=1），递归才会逐层退出，退出一层后又进入右边的函数，这其中产生了大量的冗余计算，所以在n=8时，递归的层数是32层，这个效率其实是很低的。  
所以我们需要考虑如何用循环完成这个任务，我们只需要在每次进入循环并执行相加操作后，保存相加的结果作为下次使用，循环有一个优势在于，n与循环的次数是相等的。

**代码实现：**

#include "iostream"    
    using namespace std;
    long long Fibonacci(unsigned int n)
    {
        int result[2] = {
       0, 1};
        if(n < 2)
            return result[n];
    
        long long  fibNMinusOne = 1;
        long long  fibNMinusTwo = 0;
        long long  fibN = 0;
        for(unsigned int i = 2; i <= n; ++ i)
        {
            fibN = fibNMinusOne + fibNMinusTwo;
    
            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne = fibN;
        }
    
        return fibN;
    }
    int main()
    {
        long long sum = Fibonacci(8);
        cout<<sum<<endl;
        getchar();
        return 0;
    }

我们可以对代码效率做个测试，为了让效果明显，令n=40：

#include "iostream"    
    #include <time.h>
    using namespace std;
    // ====================方法1：递归====================
    long long Fibonacci_Solution1(unsigned int n)
    {
        if(n <= 0)
            return 0;
    
        if(n == 1)
            return 1;
    
        return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
    }
    
    // ====================方法2：循环====================
    long long Fibonacci_Solution2(unsigned n)
    {
        int result[2] = {
       0, 1};
        if(n < 2)
            return result[n];
    
        long long  fibNMinusOne = 1;
        long long  fibNMinusTwo = 0;
        long long  fibN = 0;
        for(unsigned int i = 2; i <= n; ++ i)
        {
            fibN = fibNMinusOne + fibNMinusTwo;
    
            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne = fibN;
        }
    
        return fibN;
    }
    int main()
    {
        clock_t start1,finish1,start2,finish2;
        double totaltime1,totaltime2;
        start1=clock();
        long long sum1 = Fibonacci_Solution1(40);
        finish1=clock();
        totaltime1=(double)(finish1-start1)/CLOCKS_PER_SEC;
        cout<<"结果："<<sum1<<endl<<"时间："<<totaltime1<<endl;
    
        start2=clock();
        long long sum2 = Fibonacci_Solution2(40);
        finish2=clock();
        totaltime2=(double)(finish2-start2)/CLOCKS_PER_SEC;
        cout<<"结果："<<sum2<<endl<<"时间："<<totaltime2<<endl;
    
        getchar();
        return 0;
    }

结果：102334155  
时间：5.06  
结果：102334155  
时间：0

最后，关于斐波那契数列有很多应用问题，比如：

**题目1：**  
用2\*1的小矩形横着放或竖着放去覆盖右侧的2\*8的区域，要求用8个小矩形，无重叠的覆盖，那么总共有多少种方法？  
![这里写图片描述][SouthEast 1]  
f(7)问题：  
![这里写图片描述][SouthEast 2]  
f(6)问题：  
![这里写图片描述][SouthEast 3]  
而f(1)=f(2)=1

**题目2：**  
一只青蛙一次可以跳1级或2级台阶，求跳上n级台阶有几种方法？

**题目3：**  
滴滴的一道智力题：有8层台阶，开始在第0层，每次可以爬一层或者两层，请问爬到8层一共有（ ）种方法？

[SouthEast]: /images/20220610/3a61d731767d4a4397436a962811ff95.png
[SouthEast 1]: /images/20220610/f72e3ac103a44fc78b49e48bf5fa986f.png
[SouthEast 2]: /images/20220610/d37def1e0fe148868a9f350ad579be82.png
[SouthEast 3]: /images/20220610/afe569d9f16642a18d8262d80bd9a0b2.png