Java通过递归算法解决迷宫与汉诺塔及八皇后问题
时间：2022-10-21 09:43:30|栏目：JAVA代码|点击： 次
1.递归的重要规则
- 在执行一个方法时，就创建一个新的受保护的独立空间(栈空间)。
- 方法的局部变量时独立的，不会相互影响。
- 如果方法中使用的是应用类型变量(比如数组，对象)，就会共享该引用类型的数据。
- 递归必须向退出递归的条件逼近，否则就是无限递归。
- 当一个方法执行完毕，或者遇到return，就会返回，遵循谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
2.递归的三个案例
1.老鼠出迷宫
//一个7列8行的迷宫
//分析
//1.我们用一个二维数组来表示迷宫
//2.定义一个findWay方法来找路径，返回值为布尔类型，
//3.若找到路则返回true，否则返回false。
//4.我们用1来表示障碍物
//5.我们初始化老鼠当前坐标(1,1)
//6.用0表示能走，1表示不能走，2表示走过能走，3表示走过但走不通
//7.当map[6][5]=2时则说明找到了出迷宫的路，否则继续找路
//8.我们定义一个试探走的规则，我们假设 下->右->上->左
public class MiGong{
public static void main(String [] args){
//迷宫初始化
int [][] map = new int [8][7];
for(int i = 0; i < 7; i++){
map[0][i] = 1;
map[7][i] = 1;
}
for(int j = 0 ; j < 8; j++){
map[j][0] = 1;
map[j][6] = 1;
}
map[3][1]= 1;
map[3][2]= 1;
for (int k = 0; k < map.length; k++) {
for(int m = 0; m < map[k].length; m++){
System.out.print(map[k][m] + " ");
}
System.out.println();
}
t way = new t();
way.findWay(map, 1, 1);
System.out.println("=====找到路径后的地图=====");
for (int k = 0 ;k < map.length; k++) {
for(int m = 0;m < map[k].length; m++){
System.out.print(map[k][m] + " ");
}
System.out.println();
}
}
}
class t{
public boolean findWay(int [][] map ,int x , int y){
if(map[6][5]==2){//递归出口若终点处的值为2则表明能找到一条路
return true;
}else{
if(map[x][y]==0){//首先若当前位置为0，则表明可以走
map[x][y]=2;//我们假设选这条路可以走通，将当前位置赋为2
//然后按照我们的试探规则依次试探下->右->上->左
if(findWay(map, x+1, y))//递归调用findway函数如果下可以走则返回true
return true;
else if (findWay(map, x, y+1))//否则还继续看右边能不能走
return true;
else if(findWay(map, x-1, y))//上
return true;
else if(findWay(map, x, y-1))//左
return true;
else {
map[x][y]=3;
return false;
}
}else // map[x][y]=1,2,3
return false;
}
}
}
2.汉诺塔
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：
(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；
(2)将A杆中剩下的第n号盘移至C杆；
(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。
import java.util.Scanner;
public class HanoiTower{
public static void main(String []args ){
System.out.println("请输入你要移动的盘数：");
tower m = new tower();
Scanner input = new Scanner(System.in);
int num = input.nextInt();
m.moveWay(num,'A','B','C');
}
}
class tower{
//num表示要移动的盘的个数，a,b,c分别表示a塔，b塔，c塔
public void moveWay(int num,char a,char b,char c){
if(num == 1){//如果只有一个盘，直接将其从a移动到c
System.out.println(a + "->" + c);
}
else {//如果有多个盘将最后一个盘以上的盘看成一个整体，借助c，移动到b，然后将最后一个盘移到c
moveWay(num-1, a, c, b);
System.out.println(a + "->" + c);
//然后再将b的所有盘，借助a，移动到c
moveWay(num-1, b, a, c);
}
}
}
3.八皇后
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
public class Queen8{
//第一个皇后先放在第一行第一列
//第二个放在第二行第一列，然后判断是否发生冲突
//如果冲突，则继续放第二列，第三列，依次直到找到不发生冲突的位置
//第三个皇后，还是按照第二个一样依次找直到第八个皇后也能放在一个不发生冲突的地方，就算找到一个可行解。
//当得到一个可行解时，回退到上一个栈开始回溯，既可以得到第一个皇后放在第一列的所有可行解
//然后回头继续第一个皇后放在第二列，重复前面的操作
//用一个一维数组来表示皇后放置的位置
//列如arry[1]=3,表示第二个皇后放在第二行第四列
int max = 8;
int [] arry = new int [max];
static int count = 0;
public static void main(String[]args){
Queen8 queen8 = new Queen8();
queen8.locate(0);
System.out.print("摆法一共有："+ count +"种");
}
// 依次放入皇后，并判断是否冲突
public void locate(int n){
if(n == max){
display();
return;
}
for(int i = 0; i < max; i++){
//先把皇后n放到第一列
arry[n] = i;
if(judge(n)){//不冲突则继续放置第n+1个皇后
locate(n+1);
}
//如果冲突则继续往后一列放置
}
}
public boolean judge(int n){
for(int i = 0; i < n; i++){
//arry[i]==arry[n]表示在同一列
//Math.abs(i-n)==Matn.abs(arry[i]-arry[n])表示在同一斜线
if(arry[i] == arry[n] || Math.abs(i - n) == Math.abs(arry[i] - arry[n])){
return false;
}
}
return true;
}
public void display(){
count++;
for(int i = 0; i < arry.length; i++){
System.out.print(arry[i]+" ");
}
System.out.println();
}
}
