面向对象编程(基础部分)
递归(Recursion)
★递归执行机制
递归打印：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class Test{
public static void main(String[] args){
T t1 = new T();
int n = 4;
t1.recursion(4);
/*输出为：
n = 2
n = 3
n = 4*/
}
}
class T {
public void recursion(int n) {
if (n > 2) {
recursion(n - 1);
}
System.out.println("n = " + n);
}
}
阶乘：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class Test {
public static void main(String[] args) {
T t1 = new T();
int n = 5;
int res = t1.factorial(n);
System.out.println(n + " 的阶乘为：" + res);
}
}
class T {
public int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
}
递归的重要规则：
- 每执行一个方法时，就创建一个新的受保护的独立空间（栈空间）；
- 方法的局部变量是独立的，不会相互影响；
- 如果方法中使用的是引用类型变量（例如数组），就会共享该引用类型的数据；
- 递归必须向退出递归的条件逼近，否则就是无限递归，出现
StackOverflowError； - 当一个方法执行完毕，或者遇到
return时，就会返回，返回到调用该方法的地方，然后对应于该方法的栈空间就会被释放。
递归斐波那契数列
请使用递归的方式求出斐波那契数1,1,2,3,5,8,13 … 给你一个序号n，求出它所对应的值是多少。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class Test {
public static void main(String[] args) {
T t1 = new T();
int n = 10;
int res = t1.fibonacci(n);
System.out.println("序号 " + n + " 所对应的斐波那契数为：" + res);
}
}
class T {
public int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
猴子吃桃子问题
有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个。以后每天猴子都吃其中的一半，然后再多吃一个。当到第 10 天时，想再吃时 (即还没吃) 发现只有 1 个桃子了。问题：最初共多少个桃子？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32public class Test {
public static void main(String[] args) {
T t1 = new T();
int day = 1;
int peaches = t1.calPeaches(day);
if(peaches != -1){
System.out.println("第 " + day + " 天有" + " " + peaches + " 个桃子。");
}
}
}
class T {
/*
第 10 天 -> 吃之前有 1 个桃子
第 9 天 -> 吃之前有 (day10 + 1) * 2 个桃子
第 8 天 -> 吃之前有 (day9 + 1) * 2 个桃子
第 7 天 -> 吃之前有 (day8 + 1) * 2 个桃子
...
第 1 天 -> 吃之前有 (day2 + 1) * 2 个桃子 -> 最开始的桃子数
规律即为：前一天吃之前的桃子 = (后一天吃之前的桃子 + 1) * 2
*/
public int calPeaches(int day) {
if(day == 10){
return 1;
} else if ( day >=1 && day <= 9 ) {
return (calPeaches(day + 1) + 1) * 2;
}else{
System.out.println("输入不合法");
return -1;
}
}
}如果是到第 n 天时，想再吃时 (即还没吃) 发现只有 1 个桃子了，则可以进行进一步的改进：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public class Test {
public static void main(String[] args) {
T t1 = new T();
int day = 1;
int n = 10;
int peaches = t1.calPeaches(day, n);
if (peaches != -1) {
System.out.println("总共有 " + n + " 天，第 " + day + " 天有" + " " + peaches + " 个桃子。");
}
}
}
class T {
public int calPeaches(int day, int n) {
if (day == n) {
return 1;
} else if (day >= 1 && day <= n - 1) {
return (calPeaches(day + 1, n) + 1) * 2;
} else {
System.out.println("输入不合法");
return -1;
}
}
}
★老鼠出迷宫(回溯算法)
典型的用递归解决走迷宫问题（回溯算法）。
从一条路往前走，能进则进，不能进则退回来，换一条路再试。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80import java.util.Scanner;
public class Test {
public static void main(String[] args) {
/*
1. 创建一个迷宫，用二维数组表示：int[][] map;
2. 规定 map 数组的元素值：0 表示可以走，1 表示障碍物，2 表示可以走且能走通，3 表示走过但走不通;
3. 走的策略为：右 下 左 上;
4. 如果最终能让 map[row-2][col-2] == 2，说明能走出迷宫；否则不能走出迷宫。
*/
Scanner myScanner = new Scanner(System.in);
int row, col;
do {
System.out.println("请设置迷宫的行数（至少为3）和列数（至少为3）");
row = myScanner.nextInt();
col = myScanner.nextInt();
} while (row < 3 || col < 3);
//创建迷宫
int[][] map = new int[row][col];
//设置迷宫的边界
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
map[i][j] = 1;
}
}
}
//设置障碍物(只需让障碍物处的 map 值为 1 即可)
map[2][4] = 1;
map[3][4] = 1;
map[3][5] = 1;
//map[row - 2][col - 2] = 1; //将终点设置了障碍物，将导致无法走出迷宫
//输出迷宫样子
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
T t1 = new T();
if (t1.findWay(map, 1, 1, row - 2, col - 2)) {
System.out.println("可以走出该迷宫");
} else {
System.out.println("不能走出该迷宫");
}
//输出迷宫样子
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
}
class T {
public boolean findWay(int[][] map, int curRow, int curCol, int finRow, int finCol) {
if (map[finRow][finCol] == 2) {//已经成功走出迷宫
return true;
} else {
if (map[curRow][curCol] == 0) { //这一步可以走但还未走
map[curRow][curCol] = 2; //假设这一步是在可以走通的路上
if (findWay(map, curRow, curCol + 1, finRow, finCol)) { //向右走
return true;
} else if (findWay(map, curRow + 1, curCol, finRow, finCol)) { //向下走
return true;
} else if (findWay(map, curRow, curCol - 1, finRow, finCol)) { //向左走
return true;
} else if (findWay(map, curRow - 1, curCol, finRow, finCol)) { //向上走
return true;
} else {//走过但走不通，开始回溯
map[curRow][curCol] = 3;
return false;
}
} else { //map[curRow][curCol] != 0 就说明这一步是不能走的
return false;
}
}
}
}
汉诺塔
1 | public class Test { |