Java는 재귀 알고리즘을 통해 미로, 하노이 탑 및 여덟 여왕 문제를 어떻게 해결합니까?

1. 재귀의 중요한 규칙

• 메서드를 실행하면 새로운 보호되는 독립 공간(스택 공간)이 생성됩니다.

• 메서드의 지역 변수는 독립적이며 서로 영향을 미치지 않습니다.

• 메서드에 응용프로그램 유형 변수(예: 배열, 객체)가 사용되는 경우 참조 유형의 데이터가 공유됩니다.

• 재귀는 반드시 재귀를 종료하기 위한 조건에 접근해야 합니다. 그렇지 않으면 무한 재귀가 됩니다.

• 메서드가 실행을 완료하거나 반환을 만나면 결과가 호출자에게 반환됩니다. 동시에 메서드가 실행을 완료하거나 반환하면 메서드도 실행을 완료합니다.

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. 하노이의 탑

전설에 따르면 하노이 게임이라는 탑이 있었습니다. 이 게임은 세 개의 막대(A, B, C 번호)가 있는 구리판 장치에서 진행됩니다. 막대 A에는 n개의 금 디스크가 아래에서 위로, 큰 것에서 작은 순서로 배치됩니다. 게임의 목표는 A극에 있는 금 원반을 모두 C극으로 옮겨 원래 순서대로 쌓아 두는 것입니다. 작동 규칙: 한 번에 하나의 판만 이동할 수 있으며 이동 중에 큰 판은 항상 바닥에 있고 작은 판은 세 개의 막대 위에 있습니다. 작동 중에 판은 어느 곳에나 배치될 수 있습니다. 막대 A, B, C 중 하나입니다.

분석: 이러한 문제의 경우 판이 움직이는 모든 단계를 누구든지 직접 기록하는 것은 불가능하지만 다음과 같은 방법을 사용하여 해결할 수 있습니다. 이동하는 판의 수가 n개라고 가정합니다. 이 n개의 판을 A극에서 C극으로 이동하려면 다음 세 단계를 수행할 수 있습니다.

(1) 판 C를 매개로 판 1을 n-1로 이동합니다. A극에서 B극으로

(2) A극의 나머지 n번째 판을 C극으로 이동합니다.

(3) A극을 매개로 1~n-1판을 B극으로 이동합니다. 극 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. Eight Queens

문제는 다음과 같이 표현됩니다. 8x8 정사각형 체스에 8개의 퀸을 배치하여 서로 공격할 수 없도록 합니다. 즉, 두 퀸이 같은 행, 같은 열에 있을 수 없습니다. 또는 같은 경사면을 온라인에서 몇 가지 방법으로 넣을 수 있는지 물어보십시오.

rreee

위 내용은 Java는 재귀 알고리즘을 통해 미로, 하노이 탑 및 여덟 여왕 문제를 어떻게 해결합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!