首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法-斐波那契数列

算法-斐波那契数列

作者头像
chaibubble
发布2018-01-02 11:40:26
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个小矩形,无重叠的覆盖,那么总共有多少种方法?

这里写图片描述
这里写图片描述

f(7)问题:

这里写图片描述
这里写图片描述

f(6)问题:

这里写图片描述
这里写图片描述

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

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

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-08-19 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档