Rosalind: 兔子与递归

  1. 云栖社区>
  2. 博客>
  3. 正文

Rosalind: 兔子与递归

徐洲更 2018-09-30 21:22:00 浏览1020
展开阅读全文

问题描述

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

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

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

img_5a6646d6e85ba9f11231dacf94526e0c.png
兔子繁衍图

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

F_n = F_{n-1} + F_{n-2}

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

结题思路

新的斐波那契数列如下:

F_n = F_{n-1} + K \times F_{n-2}

第一版递归代码如下:

#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个月有多少兔子的时候,基本上是秒答。

网友评论

登录后评论
0/500
评论
徐洲更
+ 关注