专业团队
2020-08-14
395
原创

数据结构与算法---递归(迷宫、八皇后等问题)


1.常见的递归问题

何时需要递归：

  1. 数学问题：八皇后、汉诺塔、阶乘、迷宫、球和篮子问题等等。
  2. 各种算法：快速排序、归并排序、
  3. 将用栈解决的问题--->递归(代码比较简洁)

2.递归需要遵守的重要规则

  1. 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)。
  2. 方法的局部变量是独立的，不会互相影响。
  3. 如果方法中使用的是引用类型的变量(比如：数组)，就会共享该引用类型的数据。
  4. 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackPverflowError报错！
  5. 当一个方法执行完毕，或者遇到return就会返回。遵守谁调用，就将结果返回给谁。同时当方法执行完毕或者返回时，该方法也就执行完毕。

3.递归的简单应用与理解

avatar

public class Recursion_Test {
	public static void main(String[] args) {
		test(4);
	}

	//打印问题
	public static void test(int n){
		System.out.println("函数开头n=" + n);
		if(n > 2){
			test(n - 1);
		}
		System.out.println("函数结尾n=" + n);
	}
}

【输出】：

函数开头n=4
函数开头n=3
函数开头n=2
函数结尾n=2
函数结尾n=3
函数结尾n=4

public static void main(String[] args) {
		System.out.println("1的阶乘：" + factorial(1));
		System.out.println("2的阶乘：" + factorial(2));
		System.out.println("3的阶乘：" + factorial(3));
	}

	//阶乘问题
	public static int factorial(int n){
		if(n == 1){
			return 1;
		}else{
			return factorial(n - 1) * n;
		}
	}
}

【输出】：

1的阶乘：1
2的阶乘：2
3的阶乘：6

4.迷宫问题

利用数组来模拟小型迷宫，分别用不同的数字代表不同意思，然后利用递归让其自动从初始位置走到终点位置。

4.1 创建地图
//------------------------地图创建-------------------------
int[][] map = new int[10][10];
// 第一行、最后一行：全部置为1
for (int i = 0; i < 10; i++) {
	map[0][i] = 1;
	map[9][i] = 1;
}
// 最左侧、最右侧列：全部置为1
for (int i = 0; i < 10; i++) {
	map[i][0] = 1;
	map[i][9] = 1;
}
// 设置挡板
map[3][1] = 1; map[3][2] = 1; map[3][3] = 1;
map[1][5] = 1; map[2][5] = 1; map[3][5] = 1;
map[6][3] = 1; map[6][4] = 1; map[6][5] = 1;
4.2 查看初始地图情况
// 输出地图的情况
System.out.println("输出初始地图情况：");
for (int i = 0; i < 10; i++) {
	for (int j = 0; j < 10; j++) {
		System.out.print(map[i][j] + " ");
	}
	System.out.println();
}

输出初始地图情况：
1 1 1 1 1 1 1 1 1 1 
1 0 0 0 0 1 0 0 0 1 
1 0 0 0 0 1 0 0 0 1 
1 1 1 1 0 1 0 0 0 1 
1 0 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 0 1 
1 0 0 1 1 1 0 0 0 1 
1 0 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 0 1 
1 1 1 1 1 1 1 1 1 1

avatar

4.3 编写函数：寻找正确的路径
//【函数】：使用递归回溯来给小球找路
//1：i,j表示小球的初始位置
//2：数字2表示小球走的路径； 
//3：数字3表示该点已经走过，但是走不通
//【策略】：下->右->上->左，如果该点走不通，再回溯
public static boolean setWay(int[][] map, int i, int j){
	if(map[8][8] == 2){//通路已经找到
		return true;
	}else{
		if(map[i][j] == 0){//当前这个点还没有走过
			//按照策略
			map[i][j] = 2;//假定该点可以走通
			if(setWay(map, i+1 ,j)){//向下走
				return true;
			}else if(setWay(map, i ,j+1)){//向右走
				return true;
			}else if(setWay(map, i-1 ,j)){//向上
				return true;
			}else if(setWay(map, i ,j-1)){//向左走
				return true;
			}else{
				//说明该点是走不通的，是死路
				map[i][j] = 3;
				return false;
			}
		}else{//如果map[1][j] != 0，可能是1 2 3
			return false;
		}
	}
}

【说明】:策略可以根据自己的情况来调整，或者利用其他算法进行优化。

4.4 实现功能
// ------------------使用递归回溯 给小球找路-------------------
setWay(map, 1, 1);
// -----------------------输出新的地图------------------------
System.out.println("小球走过的输出地图情况：");
for (int i = 0; i < 10; i++) {
	for (int j = 0; j < 10; j++) {
		System.out.print(map[i][j] + " ");
	}
	System.out.println();
}

小球走过的输出地图情况：
1 1 1 1 1 1 1 1 1 1 
1 2 0 0 0 1 0 0 0 1 
1 2 2 2 2 1 0 0 0 1 
1 1 1 1 2 1 0 0 0 1 
1 0 0 0 2 0 0 0 0 1 
1 0 0 0 2 2 2 0 0 1 
1 0 0 1 1 1 2 0 0 1 
1 0 0 0 0 0 2 0 0 1 
1 0 0 0 0 0 2 2 2 1 
1 1 1 1 1 1 1 1 1 1

avatar

5.八皇后问题

回溯算法的经典案例：在国际象棋8*8的棋盘上摆放8个皇后，使其不能互相攻击(不能放在同一行、同一斜线)。

5.1 八皇后算法的基本思路
  1. 第一个皇后先放在第一行第一列。
  2. 第二个皇后放在第二行第一列，然后判断是否OK？如果不OK，则改放在第二列判断、第三列判断...找到合适位置。
  3. 第三个皇后放在第三行第一列，然后判断是否OK？如果不OK，则改放在第二列判断、第三列判断...找到合适位置。
  4. ........
  5. 直到第八个皇后放在一个不冲突的位置时，即得到了一个正确解。
  6. 当得到一个正确解时，在栈回退到上一个栈，就会开始回溯(即：将第一个皇后放在第一行第一列这种情况下的所有解得到)
  7. 然后，回头将第一个皇后放到改放到第二列，循环前面的操作......
5.2 初始化变量
// 定义一个数组：用来存储每个皇后所放的位置
int[] array = new int[8];
// 定义一个变量：统计解法的个数
static int count = 0;
5.3 编写函数：判断皇后位置是否符合要求
// 查看我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
private boolean judge(int n) {
	for (int i = 0; i < n; i++) {
		// 1.array[i] == array[n]: 判断第n个皇后是否和前面的n-1个皇后在同一列
		// 2.Math.abs(n - i) == Math.abs(array[n] - array[i])：判断第n个皇后是否和第i个皇后在同一斜线
		if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
			return false;
		}
	}
	return true;
}
5.4 编写函数：放置皇后的位置
// 放置第n个皇后
private void check(int n) {
	if (n == 8) {
		print();
		return;
	}
	// 依次放入皇后，并判断是否冲突
	for (int i = 0; i < 8; i++) {
		// 先把当前这个皇后n，放到第i列
		array[n] = i;
		if (judge(n)) {// 不冲突
			// 紧接着放第n+1个皇后，即开始递归
			check(n + 1);
		}
		// 如果冲突i++，就继续执行array[n] = i;即将第n个皇后，放置在本行的 后移的一个位置
	}
}
5.5 编写函数：打印结果
//写一个方法，可以将皇后摆放的位置打印出来
private void print() {
	count++;
	for (int i = 0; i < array.length; i++) {
		System.out.print(array[i] + " ");
	}
	System.out.println();
}
5.6 实现
public static void main(String[] args) {
	Queue8 queue8 = new Queue8();
	queue8.check(0);
	System.out.printf("一共有%d解法", count);
}

【输出】：

0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
1 4 6 0 2 7 5 3 
1 4 6 3 0 7 5 2 
1 5 0 6 3 7 2 4 
1 5 7 2 0 3 6 4 
1 6 2 5 7 4 0 3 
1 6 4 7 0 3 5 2 
1 7 5 0 2 4 6 3 
2 0 6 4 7 1 3 5 
2 4 1 7 0 6 3 5 
...省略一部分...
5 3 6 0 7 1 4 2 
5 7 1 3 0 6 4 2 
6 0 2 7 5 3 1 4 
6 1 3 0 7 4 2 5 
6 1 5 2 0 3 7 4 
6 2 0 5 7 4 1 3 
6 2 7 1 4 0 5 3 
6 3 1 4 7 0 2 5 
6 3 1 7 5 0 2 4 
6 4 2 0 5 7 1 3 
7 1 3 0 6 4 2 5 
7 1 4 2 0 6 3 5 
7 2 0 5 1 4 6 3 
7 3 0 2 5 1 6 4 
一共有92解法

6.两个案例代码的重构

6.1 迷宫
public class MiGong {
	public static void main(String[] args) {
		// ------------------------地图创建-------------------------
		int[][] map = new int[10][10];
		// 第一行、最后一行：全部置为1
		for (int i = 0; i < 10; i++) {
			map[0][i] = 1;
			map[9][i] = 1;
		}
		// 最左侧、最右侧列：全部置为1
		for (int i = 0; i < 10; i++) {
			map[i][0] = 1;
			map[i][9] = 1;
		}
		// 设置挡板
		map[3][1] = 1; map[3][2] = 1; map[3][3] = 1;
		map[1][5] = 1; map[2][5] = 1; map[3][5] = 1;
		map[6][3] = 1; map[6][4] = 1; map[6][5] = 1;
		// 输出地图的情况
		System.out.println("输出地图情况");
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		// ------------------使用递归回溯 给小球找路-------------------
		setWay(map, 1, 1);
		// ------------------------输出新的地图-------------------------
		System.out.println("小球走过的输出地图情况");
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
	// ----------------------------编写函数----------------------------
	//【函数】：使用递归回溯来给小球找路
	//1：i,j表示小球的初始位置
	//2：数字2表示小球走的路径； 
	//3：数字3表示该点已经走过，但是走不通
	//【策略】：下->右->上->左，如果该店走不通，再回溯
	public static boolean setWay(int[][] map, int i, int j){
		if(map[8][8] == 2){//通路已经找到
			return true;
		}else{
			if(map[i][j] == 0){//当前这个点还没有走过
				//按照策略
				map[i][j] = 2;//假定该点可以走通
				if(setWay(map, i+1 ,j)){//向下走
					return true;
				}else if(setWay(map, i ,j+1)){//向右走
					return true;
				}else if(setWay(map, i-1 ,j)){//向上
					return true;
				}else if(setWay(map, i ,j-1)){//向左走
					return true;
				}else{
					//说明该点是走不通的，是死路
					map[i][j] = 3;
					return false;
				}
			}else{//如果map[1][j] != 0，可能是1 2 3
				return false;
			}
		}
	}
}
6.2 八皇后
public class Queue8 {
	
	int[] array = new int[8];
	static int count = 0;
	
	public static void main(String[] args) {
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.printf("一共有%d解法", count);
	}
	
	// 查看我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
	private boolean judge(int n) {
		for (int i = 0; i < n; i++) {
			// 1.array[i] == array[n]: 判断第n个皇后是否和前面的n-1个皇后在同一列
			// 2.Math.abs(n - i) == Math.abs(array[n] - array[i])：判断第n个皇后是否和第i个皇后在同一斜线
			if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
				return false;
			}
		}
		return true;
	}
	
	// 放置第n个皇后
	private void check(int n) {
		if (n == 8) {
			print();
			return;
		}
		// 依次放入皇后，并判断是否冲突
		for (int i = 0; i < 8; i++) {
			// 先把当前这个皇后n，放到第i列
			array[n] = i;
			if (judge(n)) {// 不冲突
				// 紧接着放第n+1个皇后，即开始递归
				check(n + 1);
			}
			// 如果冲突i++，就继续执行array[n] = i;即将第n个皇后，放置在本行的 后移的一个位置
		}
	}
	
	//写一个方法，可以将皇后摆放的位置打印出来
	private void print() {
		count++;
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
}
Java
数据结构与算法
  • 作者：李延松(联系作者)
  • 发表时间：2020-08-14 15:43
  • 版本声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 公众号转载:请在文末添加作者公众号二维码

评论

留言