算法-斐波那契数列

chaibubble

发布于 2018-01-02 11:40:26

1.1K0

发布于 2018-01-02 11:40:26

文章被收录于专栏：深度学习与计算机视觉

题目： 写一个函数，输入为n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列定义如下：

解题思路： 斐波那契问题是个非常经典的递归问题，比如我们想要求得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个小矩形，无重叠的覆盖，那么总共有多少种方法？