兔兔那么可爱怎么会去世?
Rosalind编程问题之计算斐波那契数列变式,江湖人称神兔也死问题。
有关不死神兔问题可以参考这一篇文章:Rosalind Java| 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个月剩余的兔子数。难点在于递归方程并非单纯的一个,而是要根据兔子寿命变化。
下面我们直接看代码:
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;
}
}