Comment résoudre les problèmes du labyrinthe, de la Tour de Hanoï et des Huit Reines en utilisant un algorithme récursif en Java

1. Règles importantes de récursion

• Lors de l'exécution d'une méthode, un nouvel espace indépendant protégé (espace de pile) est créé.

• Les variables locales de la méthode sont indépendantes et ne s'influenceront pas les unes les autres.

• Si une variable de type application (comme un tableau, un objet) est utilisée dans la méthode, les données du type référence seront partagées.

• La récursivité doit se rapprocher des conditions de sortie de la récursivité, sinon ce sera une récursivité infinie.

• Lorsqu'une méthode termine son exécution ou rencontre un retour, elle reviendra. Le résultat sera renvoyé à celui qui l'appelle. En même temps, lorsque la méthode terminera son exécution ou reviendra, la méthode terminera également son exécution.

2. Trois cas de récursion

1. Souris sortie du labyrinthe

Tour de Hanoï

Selon la légende, dans les anciens temples indiens, il y avait une tour appelée Tour de jeu de Hanoï. Le jeu se déroule sur un dispositif en plaque de cuivre à trois tiges (numérotées A, B, C). Sur la tige A, n disques d'or sont placés dans l'ordre de bas en haut et du plus grand au plus petit. Le but du jeu est de déplacer tous les disques d'or du pôle A vers le pôle C et de les empiler dans l'ordre d'origine. Règles de fonctionnement : Une seule plaque peut être déplacée à la fois, et pendant le mouvement, la grande plaque est toujours en bas et la petite plaque est en haut des trois tiges. Pendant l'opération, la plaque peut être placée sur n'importe laquelle. des tiges A, B et C.

Analyse : Pour un tel problème, il est impossible pour quiconque d'écrire directement chaque étape du déplacement de la plaque, mais nous pouvons utiliser la méthode suivante pour le résoudre. Supposons que le nombre de plaques mobiles soit n. Afin de déplacer ces n plaques du pôle A au pôle C, vous pouvez effectuer les trois étapes suivantes :

(1) En utilisant la plaque C comme intermédiaire, déplacez les plaques 1 vers n-1. du pôle A au pôle B ;

(2) Déplacez la n-ième plaque restante du pôle A vers le pôle C

(3) En utilisant le pôle A comme intermédiaire, déplacez les plaques 1 à n-1 du pôle B ; pôle C Tige.

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

3. Huit reines

Le problème est exprimé comme suit : placez 8 reines sur un jeu d'échecs de 8 x 8 cases afin qu'elles ne puissent pas s'attaquer, c'est-à-dire que deux reines ne puissent pas être dans la même rangée, dans la même colonne. ou la même pente en ligne, demandez combien de façons de le mettre.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!