算法详解 - 神奇的兔子数列

算法知识点

递归、斐波那契数列

算法题目来源

异步社区

算法题目描述

假设第一个月有一对初生的兔子，第2个月进入成熟期，第三个月进行生育兔子，而一对成熟的 兔子每月会生1对兔子，兔子永不死去，那么从第一对初生的兔子开始，12个月后会有多少只兔子？

做题思路

不妨拿新出生的1对小兔子分析。 第1个月，小兔子①没有没有繁殖能力，所以还是1对 第2个月，小兔子①进入成熟期，所以还是1对 第3个月，兔子①生了一对兔子②，于是共有2对兔子 第4个月，兔子①生了一对兔子③，共有3对兔子 … 以此类推

在这里插入图片描述

这个数列有十分明显的特点：从第三个月开始， 当月的兔子数量 = 上月兔子数 + 当月新生兔子 当月新生兔子 = 上上个月的兔子 因此，前面相邻两项之和，便构成了后一项，换言之 当月兔子数 = 上月兔子数 + 上上月兔子数 斐波那契数列如下： 1，1，2，3，5，8，13，21，34，… 递归表达式如下：

在这里插入图片描述

模板代码

int Fib1(int n){
    if(n==1||n==2)   
    return 1;
    return Fib1(n-1)+Fib1(n-2);
}

做题过程中遇到的bug及解决方案

上面的代码是否正确？ 算法复杂度如何？ 算法是否能改进？

1、首先公式是推导出来的，算法正确性肯定没问题 2、那么复杂度呢 假设T(n) 表示计算Fib1(n)所需的基本操作次数，那么

n=1时，T(n)=1；
n=2时，T(n)=1；
n=3时，T(n)=3；//调用Fib1(2)和Fib1(1)并执行一次加法运算（Fib1(2)+Fib1(1)）

因此，当n>2时候，

T(n)=T(n-1)+T(n-2)+1；

递归表达式 和时间复杂度T(n)的关系如下：

在这里插入图片描述

由此可得，T(n)>=F(n) 那么如何计算F(n)呢？ 其中一种，就是画出F(n)的递归树，可以看出，时间复杂度是指数阶级的。

在这里插入图片描述

另一种是求斐波那契数列的通项公式：

在这里插入图片描述

算法改进： 斐波那契数列中的每一项（开头的两项除外）是前两项之和，如果记录前两项的值，则只需要一次加法运算就可以得到当前项的值，时间复杂度会不会降低一些呢？不妨用数组看看

int Fib2(int n){  
    int *F=new int[n+1];//定义一个长度为n+1的数组，空间尚未使用
    F[1]=1；
    F[2]=1;
    for(int i=3;i<=n;i++)
        F[i]=F[i-1]+F[i-2];
    return F[n];
}

很明显，时间复杂度为O(n)，因为使用了辅助数组，所以空间复杂度也是O(n)。算法复杂度大大降低。

还可以使用迭代法来取消空间复杂度。

int Fib3(int n){
    if(n==1||n==2)   
         return 1;
    int s1=1; //用s1和s2记录前面的两项
    int s2=1;
    for(int i=3;i<=n;i++){
         int tmp=s1+s2;
         s1=s2;
         s2=tmp;
    }
    return s2;
}

这样空间复杂度就降到了O(1)。那还不能再降低呢？实际上还可以降低到O(logn)，对数阶。

其他

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述