欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java通過遞歸算法解決迷宮與漢諾塔及八皇后問題

 更新時間:2022年05月10日 14:44:33   作者:小學(xué)生?。? 
方法就是用來完成解決某件事情或?qū)崿F(xiàn)某個功能的辦法;程序調(diào)用自身的編程技巧稱為遞歸,本文主要講的是通過遞歸來實(shí)現(xiàn)三個經(jīng)典的問題,解決迷宮,漢諾塔,八皇后問題,感興趣的朋友可以參考一下

1.遞歸的重要規(guī)則

  • 在執(zhí)行一個方法時,就創(chuàng)建一個新的受保護(hù)的獨(dú)立空間(??臻g)。
  • 方法的局部變量時獨(dú)立的,不會相互影響。
  • 如果方法中使用的是應(yīng)用類型變量(比如數(shù)組,對象),就會共享該引用類型的數(shù)據(jù)。
  • 遞歸必須向退出遞歸的條件逼近,否則就是無限遞歸。
  • 當(dāng)一個方法執(zhí)行完畢,或者遇到return,就會返回,遵循誰調(diào)用,就將結(jié)果返回給誰,同時當(dāng)方法執(zhí)行完畢或者返回時,該方法也就執(zhí)行完畢。

2.遞歸的三個案例

1.老鼠出迷宮

//一個7列8行的迷宮
//分析
//1.我們用一個二維數(shù)組來表示迷宮
//2.定義一個findWay方法來找路徑,返回值為布爾類型,
//3.若找到路則返回true,否則返回false。
//4.我們用1來表示障礙物
//5.我們初始化老鼠當(dāng)前坐標(biāo)(1,1)
//6.用0表示能走,1表示不能走,2表示走過能走,3表示走過但走不通
//7.當(dāng)map[6][5]=2時則說明找到了出迷宮的路,否則繼續(xù)找路
//8.我們定義一個試探走的規(guī)則,我們假設(shè) 下->右->上->左
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){//遞歸出口若終點(diǎn)處的值為2則表明能找到一條路
      return true;
     }else{
      if(map[x][y]==0){//首先若當(dāng)前位置為0,則表明可以走
         map[x][y]=2;//我們假設(shè)選這條路可以走通,將當(dāng)前位置賦為2
         //然后按照我們的試探規(guī)則依次試探下->右->上->左
         if(findWay(map, x+1, y))//遞歸調(diào)用findway函數(shù)如果下可以走則返回true
            return  true;
         else if (findWay(map, x, y+1))//否則還繼續(xù)看右邊能不能走
              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.漢諾塔

相傳在古印度圣廟中,有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上,有三根桿(編號A、B、C),在A桿自下而上、由大到小按順序放置n個金盤。游戲的目標(biāo):把A桿上的金盤全部移到C桿上,并仍保持原有順序疊好。操作規(guī)則:每次只能移動一個盤子,并且在移動過程中三根桿上都始終保持大盤在下,小盤在上,操作過程中盤子可以置于A、B、C任一桿上。

分析:對于這樣一個問題,任何人都不可能直接寫出移動盤子的每一步,但我們可以利用下面的方法來解決。設(shè)移動盤子數(shù)為n,為了將這n個盤子從A桿移動到C桿,可以做以下三步:

(1)以C盤為中介,從A桿將1至n-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("請輸入你要移動的盤數(shù):");	
    tower m = new tower();
Scanner input = new Scanner(System.in);
    int num = input.nextInt();
    m.moveWay(num,'A','B','C');
	}
} 
class tower{
	//num表示要移動的盤的個數(shù),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.八皇后

問題表述為:在8×8格的國際象棋上擺放8個皇后,使其不能互相攻擊,即任意兩個皇后都不能處于同一行、同一列或同一斜線上,問有多少種擺法。

public class Queen8{
//第一個皇后先放在第一行第一列
//第二個放在第二行第一列,然后判斷是否發(fā)生沖突
//如果沖突,則繼續(xù)放第二列,第三列,依次直到找到不發(fā)生沖突的位置
//第三個皇后,還是按照第二個一樣依次找直到第八個皇后也能放在一個不發(fā)生沖突的地方,就算找到一個可行解。
//當(dāng)?shù)玫揭粋€可行解時,回退到上一個棧開始回溯,既可以得到第一個皇后放在第一列的所有可行解
//然后回頭繼續(xù)第一個皇后放在第二列,重復(fù)前面的操作
//用一個一維數(shù)組來表示皇后放置的位置
//列如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)){//不沖突則繼續(xù)放置第n+1個皇后
     	locate(n+1);
     }
     //如果沖突則繼續(xù)往后一列放置
	}
}
 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();
 }
}

到此這篇關(guān)于Java通過遞歸算法解決迷宮與漢諾塔及八皇后問題的文章就介紹到這了,更多相關(guān)Java遞歸算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java Redis分布式鎖的正確實(shí)現(xiàn)方式詳解

    Java Redis分布式鎖的正確實(shí)現(xiàn)方式詳解

    這篇文章主要介紹了Java Redis分布式鎖的正確實(shí)現(xiàn)方式詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-09-09
  • Java中線程上下文類加載器超詳細(xì)講解使用

    Java中線程上下文類加載器超詳細(xì)講解使用

    這篇文章主要介紹了Java中線程上下文類加載器,類加載器負(fù)責(zé)讀取Java字節(jié)代碼,并轉(zhuǎn)換成java.lang.Class類的一個實(shí)例的代碼模塊。本文主要和大家聊聊JVM類加載器ClassLoader的使用,需要的可以了解一下
    2022-12-12
  • Spring ApplicationListener監(jiān)聽器用法詳解

    Spring ApplicationListener監(jiān)聽器用法詳解

    這篇文章主要介紹了Spring ApplicationListener監(jiān)聽器用法詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-11-11
  • Spring?Bean創(chuàng)建的另一條捷徑

    Spring?Bean創(chuàng)建的另一條捷徑

    這篇文章主要為大家介紹了Spring?Bean創(chuàng)建的另一條方法捷徑詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-08-08
  • 使用svn管理Maven項(xiàng)目的方法步驟

    使用svn管理Maven項(xiàng)目的方法步驟

    這篇文章主要介紹了使用svn管理Maven項(xiàng)目的方法步驟,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-08-08
  • Hibernate命名策略詳解

    Hibernate命名策略詳解

    本文主要介紹了Hibernate命名策略。具有很好的參考價(jià)值,下面跟著小編一起來看下吧
    2017-01-01
  • Springboot自動掃描包路徑來龍去脈示例詳解

    Springboot自動掃描包路徑來龍去脈示例詳解

    這篇文章主要介紹了Springboot自動掃描包路徑來龍去脈示例詳解,本文通過示例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-12-12
  • Spring Security單項(xiàng)目權(quán)限設(shè)計(jì)過程解析

    Spring Security單項(xiàng)目權(quán)限設(shè)計(jì)過程解析

    這篇文章主要介紹了Spring Security單項(xiàng)目權(quán)限設(shè)計(jì)過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-11-11
  • Scala小程序詳解及實(shí)例代碼

    Scala小程序詳解及實(shí)例代碼

    這篇文章主要介紹了Scala 第一個Scala小程序詳解的相關(guān)資料,需要的朋友可以參考下
    2017-01-01
  • IntelliJ IDEA之配置JDK的4種方式(小結(jié))

    IntelliJ IDEA之配置JDK的4種方式(小結(jié))

    這篇文章主要介紹了IntelliJ IDEA之配置JDK的4種方式(小結(jié)),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-10-10

最新評論