Wie löst Java die Labyrinth-, Tower of Hanoi- und Eight Queens-Probleme durch rekursive Algorithmen?

1. Wichtige Regeln der Rekursion

• Beim Ausführen einer Methode wird ein neuer geschützter unabhängiger Raum (Stapelraum) erstellt.

• Die lokalen Variablen der Methode sind unabhängig und beeinflussen sich nicht gegenseitig.

• Wenn eine Anwendungstypvariable (z. B. ein Array, ein Objekt) in der Methode verwendet wird, werden die Daten des Referenztyps gemeinsam genutzt.

• Die Rekursion muss sich den Bedingungen zum Beenden der Rekursion nähern, andernfalls handelt es sich um eine unendliche Rekursion.

• Wenn eine Methode die Ausführung abschließt oder auf eine Rückgabe trifft, wird sie zurückgegeben. Das Ergebnis wird an denjenigen zurückgegeben, der sie aufruft. Gleichzeitig schließt die Methode auch die Ausführung ab.

2. Drei Fälle von Rekursion

//一个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;
  }
 }
}

Der Legende nach gab es in alten indischen Tempeln einen Turm namens Hanoi. Das Spiel findet auf einem Kupferplattengerät mit drei Stäben (Nummerierung A, B, C) statt. Auf Stab A werden n Goldscheiben in der Reihenfolge von unten nach oben und von groß nach klein gelegt. Ziel des Spiels ist es, alle Goldscheiben von Pol A auf Pol C zu verschieben und sie in der ursprünglichen Reihenfolge gestapelt zu halten. Betriebsregeln: Es kann jeweils nur eine Platte bewegt werden, und während der Bewegung befindet sich die große Platte immer unten und die kleine Platte oben auf den drei Stangen. Während des Vorgangs kann die Platte auf jede beliebige gelegt werden der Stäbe A, B und C.

Analyse: Bei einem solchen Problem ist es für niemanden möglich, jeden Schritt beim Bewegen der Platte direkt aufzuschreiben, aber wir können es mit der folgenden Methode lösen. Angenommen, die Anzahl der beweglichen Platten beträgt n. Um diese n Platten von Pol A nach Pol C zu bewegen, können Sie die folgenden drei Schritte ausführen:

(1) Verwenden Sie Platte C als Vermittler und verschieben Sie die Platten 1 nach n-1 von Pol A zu Pol B;

(2) Verschieben Sie die verbleibende n-te Scheibe in Pol A zu Pol C;

(3) Verschieben Sie die 1. bis n-te Scheibe von Pol B zu Pol C Stab.

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. Acht Damen

Das Problem wird wie folgt ausgedrückt: Platzieren Sie 8 Damen auf einem 8x8-Felder-Schachbrett, sodass sie sich nicht gegenseitig angreifen können, das heißt, zwei beliebige Damen dürfen nicht in derselben Reihe oder derselben Spalte stehen oder die gleiche Steigung Online, fragen Sie, wie viele Möglichkeiten es gibt.

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

Das obige ist der detaillierte Inhalt vonWie löst Java die Labyrinth-, Tower of Hanoi- und Eight Queens-Probleme durch rekursive Algorithmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!