拓展题-生兔子的四种解法，欢迎交流！ - 黑马程序员技术交流社区

/*
题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，
假如兔子都不死，问每个月的兔子对数为多少？
程序分析：兔子的规律为数列1,1,2,3,5,8,13,21....
*/
/*
下面是我想到的几种解法，其实都是一个原理，只是在代码上的体现不同
如果大家有更加好的解法欢迎讨论~
*/
//第一种(递归)：
class Rabbits1 {
public static void main(String[] args) {
int month = 10;
System.out.println("第" + month + "个月的兔子数是: " + getNumOfRabbits(month));
}
//根据月份计算兔子数量
public static int getNumOfRabbits(int month) {
if (month == 1 || month == 2) { //如果是前两个月份的话兔子数是固定的，无需进行计算，返回1即可
return 1;
}
//如果月份超过2的话兔子数就需要知道前两个月份才能算出来
//因此函数返回的值总是前两个月兔子数的和
return getNumOfRabbits(month - 2) + getNumOfRabbits(month - 1);
}
}
/*
上面一种递归的方法可能不太好理解，并且目前基础java班并没有将递归
下面采用数组的办法做
*/
//第二种(使用数组)：
class Rabbits2 {
public static void main(String[] args) {
int month = 10;
System.out.println("第" + month + "个月的兔子数是: " + getNumOfRabbits(month));
}
public static int getNumOfRabbits(int month) {
//要计算第n个月的兔子数，就需要一个长度为n的数组
int[] numOfRabbits = new int[month];
//第一个月和第二个月的兔子数是固定的
numOfRabbits[0] = 1;
numOfRabbits[1] = 1;
//高能开始
//现在开始计算第三个月到第 month 个月的兔子数
//因为数组索引是从0开始的，所以m的初始值是 3 - 1
for (int m = 2; m < month; ++m) {
//第m个月的兔子数等于 m-1 个月加上 m-2 个月的兔子数
numOfRabbits[m] = numOfRabbits[m - 2] + numOfRabbits[m - 1];
}
//打印第 1 个月到第 month 个月的兔子数
System.out.println("每个月的兔子数:");
for (int i = 0; i < numOfRabbits.length; ++i) {
System.out.print(numOfRabbits[i] + "\t");
}
//数组的最后一项就是第month个月的兔子数
return numOfRabbits[numOfRabbits.length - 1];
}
}
//既然能用数组，并且计算的数据需要的变量来回都是那三个，是不是可以只用三个变量进行计算呢？
//第三种(小内存版):
class Rabbits3 {
public static void main(String[] args) {
int month = 10;
System.out.println("第" + month + "个月的兔子数是: " + getNumOfRabbits(month));
}
public static int getNumOfRabbits(int month) {
if (month == 1 || month == 2) { //前两个月不用算，直接返回 1 好了
return 1;
}
//高能开始
//定义三个变量，分别用于存储进行计算的三个月份的兔子数
int aaa = 1; //上上个月兔子的数量
int aa = 1; //上个月兔子的数量
int a = 0; //当前月兔子的数量
//由于前两个月兔子数量是不用计算的，因此要计算第 month 个月兔子数只需要计算 month - 2 次即可
//这就是说
month -= 2;
while (month > 0) {
a = aaa + aa; //当前月兔子数 = 上个月兔子数 + 上上个月兔子数
aaa = aa; //将上个月兔子数交由上上个月那个变量，因为下次计算的时候已经不再需要那个值
aa = a; //将本月兔子数交由上个月变量保存
//这样经过一轮计算，我们得到了本月兔子数并且还有上个月的兔子数
month--;
}
return a; //返回当月兔子数
}
}
/*
似乎每次在循环中运算之后我们只需要保存当月的和上个月的兔子数就
能够在下次循环中计算出下个月的兔子数，因此这个版本仅仅只是减少
了一个变量，但在内存使用上并不占优势
*/
//第四种(最少变量):
class Rabbits4 {
public static void main(String[] args) {
int month = 10;
System.out.println("第" + month + "个月的兔子数是: " + getNumOfRabbits(month));
}
public static int getNumOfRabbits(int month) {
if (month == 1 || month == 2) { //前两个月不用算，直接返回 1 好了
return 1;
}
int aaa = 1; //上上个月兔子的数量
int aa = 1; //上个月兔子的数量
month -= 2;
while (month > 0) {
//参考一条语句交换两个变量的值的那种写法，就不解释了
aa = aaa + aa * 2 - (aaa = aa);
month--;
}
return aa; //返回兔子数
}
}

复制代码