Java は再帰アルゴリズムを通じて迷路、ハノイの塔、8 人の女王の問題をどのように解決するのでしょうか?-＆＃＆チュートリアル-php.cn

Java は再帰アルゴリズムを通じて迷路、ハノイの塔、8 人の女王の問題をどのように解決するのでしょうか?

WBOY

リリース： 2023-04-25 13:52:06

転載

1437 人が閲覧しました

1. 再帰の重要なルール

メソッドを実行すると、新しい保護された独立空間 (スタック空間) が作成されます。
メソッドのローカル変数は独立しており、相互に影響しません。
メソッド内でアプリケーション型の変数(配列、オブジェクトなど)を使用する場合、参照型のデータが共有されます。
再帰は、再帰を終了する条件に近づく必要があります。そうでない場合は、無限再帰になります。
メソッドが実行を完了するかリターンに遭遇すると、メソッドは戻ります。結果は呼び出した人に返されます。同時に、メソッドが実行を完了するかリターンするとき、メソッドも戻り、実行が完了します。

2. 再帰の 3 つのケース

1. 迷路から抜け出すマウス

Java は再帰アルゴリズムを通じて迷路、ハノイの塔、8 人の女王の問題をどのように解決するのでしょうか?

//一个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.Hannoタワー

古代インドの寺院ではハノイタワーというゲームがあったと言われています。ゲームは 3 本の棒 (A、B、C の番号が付けられています) を備えた銅板の装置上で行われ、棒 A には、n 個の金のディスクが下から上、大きいものから小さいものの順に配置されます。ゲームの目標は、ポール A にあるすべてのゴールドディスクをポール C に移動し、元の順序で積み上げたままにすることです。操作ルール：一度に移動できるプレートは 1 つだけで、移動中は常に 3 本のロッドの一番下に大きなプレート、上部に小さなプレートが配置されます。ロッドA、B、Cの

Java は再帰アルゴリズムを通じて迷路、ハノイの塔、8 人の女王の問題をどのように解決するのでしょうか?

分析: このような問題については、プレートを移動するすべてのステップを直接書き出すことは誰にも不可能ですが、次の方法を使用して解決できます。移動するプレートの数が n であるとします。これらの n 個のプレートを極 A から極 C に移動するには、次の 3 つの手順を実行できます:

(1) プレート C を媒介として、1 を極 C に移動します。 n- ポール A からプレート No. 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,&#39;A&#39;,&#39;B&#39;,&#39;C&#39;);
	}
} 
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);
		}
	}
}

ログイン後にコピー