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();
 }
}

以上是Java怎麼透過遞歸演算法解決迷宮與漢諾塔及八皇后問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！