当前位置: 首页 > 工具软件 > Rabbits > 使用案例 >

Rosalind Java| Mortal Fibonacci Rabbits

高博涉
2023-12-01

兔兔那么可爱怎么会去世?
Rosalind编程问题之计算斐波那契数列变式,江湖人称神兔也死问题。
有关不死神兔问题可以参考这一篇文章:Rosalind Java| Rabbits and Recurrence Relations

Rabbits and Recurrence Relations

Problem
Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed the recurrence relation Fn=Fn−1+Fn−2 and assumed that each pair of rabbits reaches maturity in one month and produces a single pair of offspring (one male, one female) each subsequent month.

Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit tree in which rabbits live for three months (meaning that they reproduce only twice before dying).

Given: Positive integers n≤100 and m≤20.

Return: The total number of pairs of rabbits that will remain after the n-th month if all rabbits live for m months.


解析一下本道题:在不死神兔的基础上,设定兔子寿命为月数m,此时输出第n个月剩余的兔子数。难点在于递归方程并非单纯的一个,而是要根据兔子寿命变化。

  • 在m个月以内遵循monthn = month(n-1) + month(n-2)
  • 在第m+1个月时遵循monthn = month(n-1) + month(n-2) - 1
  • 在m+1个月之后遵循monthn = month(n-1) + month(n-2) - month(n-m-1)

下面我们直接看代码:

import java.util.Scanner;

public class Mortal_Fibonacci_Rabbits {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入月份数n:");
        int n = sc.nextInt();

        Scanner sr = new Scanner(System.in);
        System.out.println("请输入兔子存活月数m:");
        int m = sr.nextInt();

//        System.out.println("第" + n + "个月后剩余的兔子数为:" + rabbit(n, m));
        System.out.println("第" + n + "个月后剩余的兔子数为:" + rabbitnew(n, m));

    }

    //用循环方法解决斐波那契数列问题
    public static long rabbit(int n, int m) {
        //1.建立一个含有n+1个数字的数组,以便于数组引索i与月份数n对齐。
        long[] arr =new long[n+1];

        //2.判断存活月数m:
        //  如果只活一个月,则全是0
        //  如果只活两个月,则全是1
        if (m == 1){
            return 0;
        }else if (m ==2){
            return 1;
        }

        //3.按照兔子生长规律进行递归
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i < n+1; i++) {
            if (i<=m){
                //1)在m个月以内遵循monthn = month(n-1)+month(n-2)
                arr[i] = arr[i-1]+arr[i-2];
            }else if (i==m+1){
                //2)在m+1个月时遵循monthn = month(n-1)+month(n-2)-1
                arr[i] = arr[i-1]+arr[i-2]-1;
            }else {
                //3)在m+1个月之后遵循monthn = month(n-1)+month(n-2)-month(n-m-1)
                arr[i] = arr[i-1]+arr[i-2]-arr[i-m-1];
            }
        }
        return arr[n];
    }
}

理清逻辑之后,撰写代码并不算复杂。也能够顺利解决Rosalind问题。

但也要注意细节。Rosalind为了难为你,一般给出的n和m都比较大,但如果给出的月份n较小,那么本代码一定会报错。 由于本方法采用了建立静态数组,但在初始就设定了arr[0], arr[1], arr[2]三个值。这也意味着此方法输入的n+1值一定要大于等于3。否则一定会出现引索越界的情况。

因此,要分类讨论n的输入情况。
修正后的代码如下,在此暂时忽略main函数:

public static long rabbitnew(int n, int m) {
        if (n>=2){
            //1.建立一个含有n+1个数字的数组,以便于数组引索i与月份数n对齐。
            long[] arr =new long[n+1];

            //2.判断存活月数m:
            //  如果只活一个月,则全是0
            //  如果只活两个月,则全是1
            if (m == 1){
                return 0;
            }else if (m ==2){
                return 1;
            }

            //3.按照兔子生长规律进行递归
            arr[0] = 0;
            arr[1] = 1;
            arr[2] = 1;
            for (int i = 3; i < n+1; i++) {
                if (i<=m){
                    //1)在m个月以内遵循monthn = month(n-1)+month(n-2)
                    arr[i] = arr[i-1]+arr[i-2];
                }else if (i==m+1){
                    //2)在m+1个月时遵循monthn = month(n-1)+month(n-2)-1
                    arr[i] = arr[i-1]+arr[i-2]-1;
                }else {
                    //3)在m+1个月之后遵循monthn = month(n-1)+month(n-2)-month(n-m)
                    arr[i] = arr[i-1]+arr[i-2]-arr[i-m-1];
                }
            }
            return arr[n];
        }else {
            //如果输入月数为1,则直接返回数值。否则静态数组建立失败。
            return 1;
        }
    }
 类似资料:

相关阅读

相关文章

相关问答