数据结构与算法
递归Recursion、迷宫回溯、八皇后问题、排列组合
对于递归大家应该都不陌生了，我们直接看递归的应用。
迷宫回溯
给定一个二维数组，用1表示墙壁，0表示道路，当使用者指定入口和出口时，程序可以从入口走出迷宫。
如这个二维数组：
text
1 1 1 1 1
1 1 0 0 1
0 0 0 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
因为要求比较低，所以实现起来比较简单：
java实现
java
package Recursion;
import java.io.*;
public class Maze {
//用二维数组表示迷宫地图，约定1为墙壁，0为通路，2为足迹，3为重复走过的点
int[][] mazeMap;
//出口坐标
int goalI;
int goalJ;
//以文件方式构造地图数组,这样好设计地图
public Maze(File mapFile) throws IOException {
loadMapFile(mapFile);
}
//读取地图文件中的二维数组
public void loadMapFile(File mapFile) throws IOException {
/*
* 拿到文件中二维数组的行数列数
* */
Reader reader = new FileReader(mapFile);
BufferedReader bufferedReader = new BufferedReader(reader);
//查看数组行数
int rowI = 0;
//数组列数
int rowJ = 0;
//文件每行数据
String line;
while ((line = bufferedReader.readLine()) != null) {
//得到数组行数
rowI++;
//每行以两个空格分割
String[] splits = line.split(" {2}");
//得到列数
rowJ = splits.length;
}
System.out.println("该地图的二维数组行数：" + rowI);
System.out.println("该地图的二维数组列数：" + rowJ);
//初始化对应行列的数组
mazeMap = new int[rowI][rowJ];
System.out.println("地图数组初始化完成");
/*
* 载入文件中的数组数据
* */
//关闭流
bufferedReader.close();
//新建流
reader = new FileReader(mapFile);
bufferedReader = new BufferedReader(reader);
//开始读取每行数据
//数组第i行
int i = 0;
while (i < rowI) {
//读取每行数据
line = bufferedReader.readLine();
//以两个空格分割
String[] splits = line.split(" {2}");
//处理当前行的数据
for (int j = 0; j < splits.length; j++) {
//[打印]每行数据，不换行
System.out.print(splits[j] + "\t");
//把当前值转为int，然后赋给二维数组
mazeMap[i][j] = Integer.parseInt(splits[j]);
}
//行数自增
i++;
//[打印]每行打印后换行
System.out.println();
}
System.out.println("地图数组数据载入完成！");
}
//读取稀疏数组文件
/*
* 暂时不需要，地图文件大的话可以转成稀疏数组存放
* */
//打印数组
public void show(){
//打印数组
for (int[] valuex : mazeMap) {
for (int valuey : valuex) {
System.out.print(valuey + "\t");
}
System.out.println();
}
}
//自动寻找迷宫路线，指定一个入口的坐标(x,y)，再指定一个出口的坐标(goalI,goalJ)
public void autoFind(int x, int y, int goalI, int goalJ) {
if (mazeMap == null) {
System.out.println("地图无数据，请先初始化");
} else {
//判断输入值是否越界，是否有效
if (x >= mazeMap[0].length || y >= mazeMap.length || mazeMap[y][x] == 1) {
System.out.println("该位置不在地图内，或者该位置不能做为入口");
} else {
//指定出口坐标
this.goalI = goalI;
this.goalJ = goalJ;
//开始寻路
System.out.println("开始寻路");
startFind(x, y);
//打印数组
show();
}
}
}
//递归寻路
public boolean startFind(int x, int y) {
//若到达出口
if (x == goalI && y == goalJ) {
System.out.println("找到出口");
return true;
}
//若能走通
if (mazeMap[y][x] == 0) {
mazeMap[y][x] = 2;
System.out.println("找到一个点");
show();
//接着向上走
if (startFind(x, y - 1)) {
return true;
//向右走
} else if (startFind(x + 1, y)) {
return true;
//向下走
} else if (startFind(x, y + 1)) {
return true;
//向左走
} else if (startFind(x - 1, y)) {
return true;
} else {
//都走不通
System.out.println(" ");
return false;
}
}else if (mazeMap[y][x] == 2){
System.out.println("回溯");
mazeMap[y][x] = 3;
show();
return false;
}else {
System.out.println("碰到墙");
return false;
}
}
}
class mapTest {
public static void main(String[] args) throws IOException {
//源文件
File mapFile = new File("D:\\aria2\\mazeMap.data");
Maze maze = new Maze(mapFile);
//起始坐标(0,2)，终点坐标(1,5)
maze.autoFind(0, 2, 1, 5);
}
}
输出结果
shell
该地图的二维数组行数：6
该地图的二维数组列数：5
地图数组初始化完成
1 1 1 1 1
1 1 0 0 1
0 0 0 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
地图数组数据载入完成！
开始寻路
找到一个点
1 1 1 1 1
1 1 0 0 1
2 0 0 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
碰到墙
找到一个点
1 1 1 1 1
1 1 0 0 1
2 2 0 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
碰到墙
找到一个点
1 1 1 1 1
1 1 0 0 1
2 2 2 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
找到一个点
1 1 1 1 1
1 1 2 0 1
2 2 2 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
碰到墙
找到一个点
1 1 1 1 1
1 1 2 2 1
2 2 2 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
碰到墙
碰到墙
碰到墙
回溯
1 1 1 1 1
1 1 3 2 1
2 2 2 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
回溯
1 1 1 1 1
1 1 3 2 1
2 2 3 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
碰到墙
碰到墙
找到一个点
1 1 1 1 1
1 1 3 2 1
2 2 3 1 1
1 0 2 0 1
1 0 1 1 1
1 0 1 1 1
碰到墙
找到一个点
1 1 1 1 1
1 1 3 2 1
2 2 3 1 1
1 0 2 2 1
1 0 1 1 1
1 0 1 1 1
碰到墙
碰到墙
碰到墙
回溯
1 1 1 1 1
1 1 3 2 1
2 2 3 1 1
1 0 3 2 1
1 0 1 1 1
1 0 1 1 1
碰到墙
找到一个点
1 1 1 1 1
1 1 3 2 1
2 2 3 1 1
1 2 3 2 1
1 0 1 1 1
1 0 1 1 1
回溯
1 1 1 1 1
1 1 3 2 1
2 3 3 1 1
1 2 3 2 1
1 0 1 1 1
1 0 1 1 1
碰到墙
找到一个点
1 1 1 1 1
1 1 3 2 1
2 3 3 1 1
1 2 3 2 1
1 2 1 1 1
1 0 1 1 1
回溯
1 1 1 1 1
1 1 3 2 1
2 3 3 1 1
1 3 3 2 1
1 2 1 1 1
1 0 1 1 1
碰到墙
找到出口
1 1 1 1 1
1 1 3 2 1
2 3 3 1 1
1 3 3 2 1
1 2 1 1 1
1 0 1 1 1
Process finished with exit code 0
八皇后Eight queens
百度百科：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
针对这个问题，我们可以把棋盘简化成一个普通数组， 把棋盘行数对应为数组下标即可，而不必使用二维数组来表示棋盘，如：
java
array[8]={0, 6, 3, 5, 7, 1, 4, 2}
//分别对应棋子从第1行到第8行的位置
//每行的值在0~7之间
-
判断是否在同一列
- 只需判断与之前已有的值是否相同，设当前行号为
n，之前行号为pastN，若在同一列，则有：
javaarray[n] == array[pastN] - 只需判断与之前已有的值是否相同，设当前行号为
-
判断是否在同一斜线
- 只需判断
行号之间的差值，与对应行棋子所在位置的差值，是否相同，需要用绝对值来判断：
java//Math.abs(a)返回a的绝对值 Math.abs( array[n] - array[pastN] )==Math.abs( n - pastN) - 只需判断
-
判断是否在同一行
- 显然一维数组不可能有同一行，所以无需判断
java实现
先看一个比较简单的java实现，以后我们再对它进行优化：
java
package Recursion;
import java.util.Arrays;
public class EightQueens {
//初始化一个数组
private int[] array = new int[8];
//对有效结果进行计数
private int count = 0;
//使用n表示棋盘的第n+1行，初始为0，表示棋盘第1行，即array[n]
/**
* 往棋盘中放入皇后（给数组赋值）
* @param n 表示当前行号，范围从0到7
*/
public void addQueen(int n) {
//当n==8时，说明一个8*8的棋盘每行都放了，此时是要放第9个了
if (n == 8) {
count++;
System.out.println("第" + count + "次的棋子已经放完："+showArrayString());
return;
}
//在当前行放棋子，从0号位放到7号位
for (int i = 0; i < array.length; i++) {
//放入棋子
array[n] = i;
//每放一个，判断棋子的位置与放过的棋子是否冲突
//若不冲突
if (check(n)) {
//用递归，换到下一行做重复的事情
addQueen(n + 1);
}
//没进入递归，就说明该棋子位置冲突，不用做什么，继续for循环改变棋子位置即可
}
}
//判断是否冲突的方法
public boolean check(int n) {
//遍历棋盘的每一行
for (int pastN = 0; pastN < n; pastN++) {
//若与当前行的棋子在同列或同一斜线
if (isSameColumn(n, pastN) || isSameSlant(n, pastN)) {
return false;
}
}
//循环完毕后能执行到这里，说明不与以前的棋子在同列同斜线
return true;
}
/**
* 判断是否在同一列
*
* @param n 表示当前行
* @param pastN 表示n之前的任意行
*/
public boolean isSameColumn(int n, int pastN) {
return array[n] == array[pastN];
}
//判断是否在同一行
/*这个无需判断，因为肯定不在同一行*/
//判断是否在同一斜线，使用绝对值
public boolean isSameSlant(int n, int pastN) {
return Math.abs(array[n] - array[pastN]) == Math.abs(n - pastN);
}
//返回数组的字符串
public String showArrayString() {
return Arrays.toString(array);
}
//展示数组
public void show(){
System.out.println(showArrayString());
}
}
class eightQueenTest {
public static void main(String[] args) {
EightQueens eightQueens = new EightQueens();
eightQueens.addQueen(0);
}
}
输出结果
shell
第1次的棋子已经放完：[0, 4, 7, 5, 2, 6, 1, 3]
第2次的棋子已经放完：[0, 5, 7, 2, 6, 3, 1, 4]
第3次的棋子已经放完：[0, 6, 3, 5, 7, 1, 4, 2]
第4次的棋子已经放完：[0, 6, 4, 7, 1, 3, 5, 2]
第5次的棋子已经放完：[1, 3, 5, 7, 2, 0, 6, 4]
第6次的棋子已经放完：[1, 4, 6, 0, 2, 7, 5, 3]
第7次的棋子已经放完：[1, 4, 6, 3, 0, 7, 5, 2]
第8次的棋子已经放完：[1, 5, 0, 6, 3, 7, 2, 4]
第9次的棋子已经放完：[1, 5, 7, 2, 0, 3, 6, 4]
第10次的棋子已经放完：[1, 6, 2, 5, 7, 4, 0, 3]
第11次的棋子已经放完：[1, 6, 4, 7, 0, 3, 5, 2]
第12次的棋子已经放完：[1, 7, 5, 0, 2, 4, 6, 3]
第13次的棋子已经放完：[2, 0, 6, 4, 7, 1, 3, 5]
第14次的棋子已经放完：[2, 4, 1, 7, 0, 6, 3, 5]
第15次的棋子已经放完：[2, 4, 1, 7, 5, 3, 6, 0]
第16次的棋子已经放完：[2, 4, 6, 0, 3, 1, 7, 5]
第17次的棋子已经放完：[2, 4, 7, 3, 0, 6, 1, 5]
第18次的棋子已经放完：[2, 5, 1, 4, 7, 0, 6, 3]
第19次的棋子已经放完：[2, 5, 1, 6, 0, 3, 7, 4]
第20次的棋子已经放完：[2, 5, 1, 6, 4, 0, 7, 3]
第21次的棋子已经放完：[2, 5, 3, 0, 7, 4, 6, 1]
第22次的棋子已经放完：[2, 5, 3, 1, 7, 4, 6, 0]
第23次的棋子已经放完：[2, 5, 7, 0, 3, 6, 4, 1]
第24次的棋子已经放完：[2, 5, 7, 0, 4, 6, 1, 3]
第25次的棋子已经放完：[2, 5, 7, 1, 3, 0, 6, 4]
第26次的棋子已经放完：[2, 6, 1, 7, 4, 0, 3, 5]
第27次的棋子已经放完：[2, 6, 1, 7, 5, 3, 0, 4]
第28次的棋子已经放完：[2, 7, 3, 6, 0, 5, 1, 4]
第29次的棋子已经放完：[3, 0, 4, 7, 1, 6, 2, 5]
第30次的棋子已经放完：[3, 0, 4, 7, 5, 2, 6, 1]
第31次的棋子已经放完：[3, 1, 4, 7, 5, 0, 2, 6]
第32次的棋子已经放完：[3, 1, 6, 2, 5, 7, 0, 4]
第33次的棋子已经放完：[3, 1, 6, 2, 5, 7, 4, 0]
第34次的棋子已经放完：[3, 1, 6, 4, 0, 7, 5, 2]
第35次的棋子已经放完：[3, 1, 7, 4, 6, 0, 2, 5]
第36次的棋子已经放完：[3, 1, 7, 5, 0, 2, 4, 6]
第37次的棋子已经放完：[3, 5, 0, 4, 1, 7, 2, 6]
第38次的棋子已经放完：[3, 5, 7, 1, 6, 0, 2, 4]
第39次的棋子已经放完：[3, 5, 7, 2, 0, 6, 4, 1]
第40次的棋子已经放完：[3, 6, 0, 7, 4, 1, 5, 2]
第41次的棋子已经放完：[3, 6, 2, 7, 1, 4, 0, 5]
第42次的棋子已经放完：[3, 6, 4, 1, 5, 0, 2, 7]
第43次的棋子已经放完：[3, 6, 4, 2, 0, 5, 7, 1]
第44次的棋子已经放完：[3, 7, 0, 2, 5, 1, 6, 4]
第45次的棋子已经放完：[3, 7, 0, 4, 6, 1, 5, 2]
第46次的棋子已经放完：[3, 7, 4, 2, 0, 6, 1, 5]
第47次的棋子已经放完：[4, 0, 3, 5, 7, 1, 6, 2]
第48次的棋子已经放完：[4, 0, 7, 3, 1, 6, 2, 5]
第49次的棋子已经放完：[4, 0, 7, 5, 2, 6, 1, 3]
第50次的棋子已经放完：[4, 1, 3, 5, 7, 2, 0, 6]
第51次的棋子已经放完：[4, 1, 3, 6, 2, 7, 5, 0]
第52次的棋子已经放完：[4, 1, 5, 0, 6, 3, 7, 2]
第53次的棋子已经放完：[4, 1, 7, 0, 3, 6, 2, 5]
第54次的棋子已经放完：[4, 2, 0, 5, 7, 1, 3, 6]
第55次的棋子已经放完：[4, 2, 0, 6, 1, 7, 5, 3]
第56次的棋子已经放完：[4, 2, 7, 3, 6, 0, 5, 1]
第57次的棋子已经放完：[4, 6, 0, 2, 7, 5, 3, 1]
第58次的棋子已经放完：[4, 6, 0, 3, 1, 7, 5, 2]
第59次的棋子已经放完：[4, 6, 1, 3, 7, 0, 2, 5]
第60次的棋子已经放完：[4, 6, 1, 5, 2, 0, 3, 7]
第61次的棋子已经放完：[4, 6, 1, 5, 2, 0, 7, 3]
第62次的棋子已经放完：[4, 6, 3, 0, 2, 7, 5, 1]
第63次的棋子已经放完：[4, 7, 3, 0, 2, 5, 1, 6]
第64次的棋子已经放完：[4, 7, 3, 0, 6, 1, 5, 2]
第65次的棋子已经放完：[5, 0, 4, 1, 7, 2, 6, 3]
第66次的棋子已经放完：[5, 1, 6, 0, 2, 4, 7, 3]
第67次的棋子已经放完：[5, 1, 6, 0, 3, 7, 4, 2]
第68次的棋子已经放完：[5, 2, 0, 6, 4, 7, 1, 3]
第69次的棋子已经放完：[5, 2, 0, 7, 3, 1, 6, 4]
第70次的棋子已经放完：[5, 2, 0, 7, 4, 1, 3, 6]
第71次的棋子已经放完：[5, 2, 4, 6, 0, 3, 1, 7]
第72次的棋子已经放完：[5, 2, 4, 7, 0, 3, 1, 6]
第73次的棋子已经放完：[5, 2, 6, 1, 3, 7, 0, 4]
第74次的棋子已经放完：[5, 2, 6, 1, 7, 4, 0, 3]
第75次的棋子已经放完：[5, 2, 6, 3, 0, 7, 1, 4]
第76次的棋子已经放完：[5, 3, 0, 4, 7, 1, 6, 2]
第77次的棋子已经放完：[5, 3, 1, 7, 4, 6, 0, 2]
第78次的棋子已经放完：[5, 3, 6, 0, 2, 4, 1, 7]
第79次的棋子已经放完：[5, 3, 6, 0, 7, 1, 4, 2]
第80次的棋子已经放完：[5, 7, 1, 3, 0, 6, 4, 2]
第81次的棋子已经放完：[6, 0, 2, 7, 5, 3, 1, 4]
第82次的棋子已经放完：[6, 1, 3, 0, 7, 4, 2, 5]
第83次的棋子已经放完：[6, 1, 5, 2, 0, 3, 7, 4]
第84次的棋子已经放完：[6, 2, 0, 5, 7, 4, 1, 3]
第85次的棋子已经放完：[6, 2, 7, 1, 4, 0, 5, 3]
第86次的棋子已经放完：[6, 3, 1, 4, 7, 0, 2, 5]
第87次的棋子已经放完：[6, 3, 1, 7, 5, 0, 2, 4]
第88次的棋子已经放完：[6, 4, 2, 0, 5, 7, 1, 3]
第89次的棋子已经放完：[7, 1, 3, 0, 6, 4, 2, 5]
第90次的棋子已经放完：[7, 1, 4, 2, 0, 6, 3, 5]
第91次的棋子已经放完：[7, 2, 0, 5, 1, 4, 6, 3]
第92次的棋子已经放完：[7, 3, 0, 2, 5, 1, 6, 4]
Process finished with exit code 0
所以我们可以看到，共有92种放法。
排列组合
不多说，如
java
package Recursion;
//排列组合
public class SortTest {
public static void main(String[] args) {
char[] array = {'A', 'B', 'C'};
arrange(array, 0, array.length);
}
public static void arrange(char[] array, int start, int len) {
if (start == len - 1) {
for (int i = 0; i < array.length; i++)
System.out.print(array[i]);
System.out.println();
return;
}
for (int i = start; i < len; i++) {
char temp = array[start];
array[start] = array[i];
array[i] = temp;
arrange(array, start + 1, len);
temp = array[start];
array[start] = array[i];
array[i] = temp;
}
}
}