建筑模拟3正版下载,河北百度seo软件,中堂镇仿做网站,上海装修公司排名榜单出炉题目描述#xff1a;
兔子生崽问题。假设一对小兔的成熟期是一个月#xff0c;即一个月可长成成兔#xff0c;每对成兔每个月可以生一对小兔#xff0c;一对新生的小兔从第二个月起就开始生兔子#xff0c;试问从一对兔子开始繁殖#xff0c;一年以后可有多少对兔子
兔子生崽问题。假设一对小兔的成熟期是一个月即一个月可长成成兔每对成兔每个月可以生一对小兔一对新生的小兔从第二个月起就开始生兔子试问从一对兔子开始繁殖一年以后可有多少对兔子
这道题目一眼看过去就是典型的递归问题代码如下
public class RabbitReproduction {public static void main(String[] args) {int months 12;System.out.println(After months months, there will be rabbitPairs(months) pairs of rabbits.);}public static int rabbitPairs(int n) {if (n 1 || n 2) {return 1;}return rabbitPairs(n - 1) rabbitPairs(n - 2);}
}
递归方法rabbitPairs 使用递归来计算每个月的兔子对数。这个问题类似于斐波那契数列 第一个月和第二个月有 1 对兔子。 从第三个月开始每个月的兔子对数等于前两个月的兔子对数之和。 但是这道题目虽然简单但是递归方法可能会导致性能问题。
public class RabbitReproduction {public static void main(String[] args) {int months 12;System.out.println(After months months, there will be rabbitPairs(months) pairs of rabbits.);}public static int rabbitPairs(int n) {if (n 1 || n 2) {return 1;}int[] dp new int[n 1];dp[1] 1;dp[2] 1;for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
数组 dp用于存储每个月的兔子对数。初始条件dp[1] 和 dp[2] 都设为 1因为第一个月和第二个月只有一对兔子。状态转移方程dp[i] dp[i - 1] dp[i - 2]。这表示每个月的兔子对数等于前一个月和前两个月兔子对数之和。循环从第三个月开始逐月计算直至第 n 个月
这种方法主要是避免了递归带来的性能问题效率更高。
