一道关于兔子繁衍的编程题:
有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
自己考虑了挺久,思路出现了问题,甚至连其中的规律都没有搞清楚.查看网上的一些算法之后,发现一个之前没有使用的思想:递归.目前对于递归的理解仅限于初级中的初级.
关于这道编程题,应该以这样的思路来进行考虑:
每个月的兔子的来源是哪些?答:上个月的兔子的个数(不管是否具备繁殖能力) + 2个月前的兔子的个数 在第1和2个月的时候,只有最开始的一对兔子.
这样想一想的话,就是用上个月的兔子个数 + 上上个月的兔子个数 ,就可以得到本月的兔子的个数.结果恰好是很著名的斐波那契数列.
public static int method(int month){
if(month == 1 || month == 2){
return 1;
}else{
int num = method(month -1) + method(month -2);
return num;
}
}
思想就是结果= 上次程序的结果 + 上上次的程序的结果
后在网上查看有关递归的资料,看到另外两个用递归思想解决的问题:爬楼梯问题和汉诺塔问题
爬楼梯问题
假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶，求总共的爬楼梯方案数。
分析:
台阶数(走法) 方法数
1 1 1
2 11 2 2
3 111 12 21 3
4 1111 112 121 211 225
因此可知,这个问题和之前的兔子繁衍问题是一个道理.
public static int f(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
return f(n - 1) + f(n - 2);
}
}
汉诺塔问题:
从左到右 A B C 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱,大盘子只能在小盘子下面.
这些问题我想起来比较吃力,但网上解析很多,几乎涵盖了我的所有的考虑了,因此,我在这里只说以下较为简单快捷的一种理解方式.
A,B,C三个针,假设有n个盘子,只需要分成三步,①将(n-1)个盘子从A移动到B,②将最大的盘子从A放到C,③将(n-1)个盘子从B移动到C
f(n) = (f(n-1)*2) + 1;
public static int method(int n){
if(n == 1){
return 0;
}else if(n == 2){
return 1;
}else{
return method(n-1)*2 + 1;
}
}
再举个例子,使用递归的思想来打印9*9乘法表
正常若不使用迭代的话,可以这样来实现代码,使用两层嵌套的for循环
public static void method_1(){
for(int i = 1;i <= 9;i++){
for(int j = 1;j <= i;j++){
System.out.print(i + "*" + j + "=" + i*j + " ");
}
System.out.println();
}
}
若使用递归的话,问题就变成了:打印上一次的结果并打印新的一行
public static void method_2(int i){
if (i == 1) {
System.out.println("1*1=1 ");
} else {
method_2(i - 1);
for (int j = 1; j <= i; j++) {
System.out.print(j + "*" + i + "=" + j * i + " ");
}
System.out.println();
}
}
关于递归的应用,大体上来说,就是需要发现并找到程序中的递归的情况,将问题简化.