Bagaimana untuk menyelesaikan masalah maze, Tower of Hanoi dan Eight Queens menggunakan algoritma rekursif di Jawa

1. Peraturan penting rekursi

• Apabila kaedah dilaksanakan, ruang bebas yang dilindungi (ruang tindanan) dicipta. Pembolehubah tempatan kaedah

• adalah bebas dan tidak akan menjejaskan satu sama lain.

• Jika pembolehubah jenis aplikasi (seperti tatasusunan, objek) digunakan dalam kaedah, data jenis rujukan akan dikongsi.

• Rekursi mesti mendekati syarat untuk keluar dari rekursi, jika tidak, ia akan menjadi rekursi tak terhingga.

• Apabila kaedah menyelesaikan pelaksanaan atau menemui pengembalian, hasilnya akan dikembalikan kepada sesiapa yang memanggilnya Pada masa yang sama, apabila kaedah menyelesaikan pelaksanaan atau mengembalikan, kaedah itu juga akan kembali.

2. Tiga kes pengulangan

1 tetikus keluar dari labirin

//一个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. . Menara Hanoi

Mengikut legenda, di kuil India kuno, terdapat permainan yang dipanggil Menara Hanoi (Hanoi). Permainan ini adalah pada peranti plat kuprum dengan tiga batang (bernombor A, B, C Pada rod A, n cakera emas diletakkan mengikut urutan dari bawah ke atas dan dari besar ke kecil). Matlamat permainan ini adalah untuk memindahkan semua cakera emas pada tiang A ke tiang C dan memastikannya disusun mengikut susunan asal. Peraturan pengendalian: Hanya satu plat boleh digerakkan pada satu masa, dan semasa pergerakan, plat besar sentiasa berada di bahagian bawah dan plat kecil berada di bahagian atas tiga batang semasa operasi, plat boleh diletakkan pada mana-mana daripada rod A, B, dan C.

Analisis: Untuk masalah sebegini, adalah mustahil bagi sesiapa untuk menulis secara langsung setiap langkah menggerakkan plat, tetapi kita boleh menggunakan kaedah berikut untuk menyelesaikannya. Katakan bilangan plat yang bergerak ialah n Untuk memindahkan n plat ini dari kutub A ke kutub C, tiga langkah berikut boleh dilakukan:

(1) Menggunakan plat C sebagai perantara, gerakkan 1 ke. n- dari kutub A Pindahkan plat No. 1 ke kutub B;

(2) Pindahkan plat ke-n yang tinggal di kutub A ke kutub C; ; dari tiang B Rod menggerakkan cakera 1 ke n-1 ke rod C.

3. Lapan Ratu

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

Masalahnya dinyatakan seperti berikut: Letakkan 8 ratu pada catur 8×8 persegi supaya mereka tidak boleh menyerang antara satu sama lain, iaitu mana-mana dua queens Mereka tidak boleh berada dalam baris, lajur atau pepenjuru yang sama. Berapa banyak cara yang ada untuk meletakkannya?

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah maze, Tower of Hanoi dan Eight Queens menggunakan algoritma rekursif di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!