Rosalind: 兔子与递归

问题描述

序列 指的是一组对象的集合，其中允许重复。序列分为有限序列和无限序列两种类型，我们通常用 表示序列中的第n个对象。

递归其实就是当前的序列依赖于之前的序列。最典型的案例就是兔子繁衍问题，假设一开始第一个月有1对兔子（A），到了第二个月这对兔子(A)性成熟，到了第三个月这对兔子（A）生出了一对兔子（B）。到了第四个月兔子（A）又生了一对兔子（D），之前刚的兔子（B）性成熟。到了第五个月，兔子（A）又生了兔子E，兔子（B）生出了兔子(F)，而兔子（D）性成熟。

当然一图胜过千言万语，也就是下面这个情况

兔子繁衍图

这也就是斐波那契数列，公式为

现在，如果每个具有繁衍能力的兔子能够生出k对兔子，那么n个月后一共有多少对兔子？

结题思路

新的斐波那契数列如下：

第一版递归代码如下:

#include <stdio.h>
#include <stdlib.h>

long int FIB(long int n, long int k)
{
    if (n == 1 || n == 2){
        return 1;
    } else{
        return FIB(n-1,k) + k * FIB(n-2, k);
    }

}

int main(int argc, char *argv[])
{
    if (argc != 3){
        printf("USAGE: ./FIB n k \n");
        return 1;
    }
    long int n = atoi(argv[1]);
    long int k = atoi(argv[2]);
    printf("month is %ld, %ld rabbit pairs per \n", n, k);
    long total = FIB(n,k);
    printf("The total number of rabbit is %ld \n", total);
    return 0;

}

注意，这个数字增长的很快，所以用了long int。

上面的方法在month很大的时候时候，这些迭代算法的由于会反复求解一些重复的子问题，导致求解速度就会非常慢，比如求解第100个月会有多少个兔子，会需要很久很久。而且很容易导致栈溢出，解决方案就是**动态规划**dynamic programming

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

代码如下:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if (argc != 2){
        printf("USAGE: ./FIBv2 n k \n");
    }

    long int n = atoi(argv[1]);
    long int k = atoi(argv[2]);

    long int month[n-1];
    int i = 0;
    for (i = 0 ; i < n; i++){
        if ( i == 0 || i == 1){
            month[i] = 1;
        } else{
            month[i] = month[i-1] + k * month[i-2];
        }
    }

    printf("After %ld month, there are %ld rabbits\n", n, month[n-1]); 
   

    return 0;
}

这个代码在求解第100个月有多少兔子的时候，基本上是秒答。