算法-斐波那契数列

题目: 写一个函数,输入为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个小矩形,无重叠的覆盖,那么总共有多少种方法?

f(7)问题:

f(6)问题:

而f(1)=f(2)=1

题目2: 一只青蛙一次可以跳1级或2级台阶,求跳上n级台阶有几种方法?

题目3: 滴滴的一道智力题:有8层台阶,开始在第0层,每次可以爬一层或者两层,请问爬到8层一共有( )种方法?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区