Java通過(guò)遞歸算法解決迷宮與漢諾塔及八皇后問(wèn)題
1.遞歸的重要規(guī)則
- 在執(zhí)行一個(gè)方法時(shí),就創(chuàng)建一個(gè)新的受保護(hù)的獨(dú)立空間(??臻g)。
- 方法的局部變量時(shí)獨(dú)立的,不會(huì)相互影響。
- 如果方法中使用的是應(yīng)用類(lèi)型變量(比如數(shù)組,對(duì)象),就會(huì)共享該引用類(lèi)型的數(shù)據(jù)。
- 遞歸必須向退出遞歸的條件逼近,否則就是無(wú)限遞歸。
- 當(dāng)一個(gè)方法執(zhí)行完畢,或者遇到return,就會(huì)返回,遵循誰(shuí)調(diào)用,就將結(jié)果返回給誰(shuí),同時(shí)當(dāng)方法執(zhí)行完畢或者返回時(shí),該方法也就執(zhí)行完畢。
2.遞歸的三個(gè)案例
1.老鼠出迷宮
//一個(gè)7列8行的迷宮 //分析 //1.我們用一個(gè)二維數(shù)組來(lái)表示迷宮 //2.定義一個(gè)findWay方法來(lái)找路徑,返回值為布爾類(lèi)型, //3.若找到路則返回true,否則返回false。 //4.我們用1來(lái)表示障礙物 //5.我們初始化老鼠當(dāng)前坐標(biāo)(1,1) //6.用0表示能走,1表示不能走,2表示走過(guò)能走,3表示走過(guò)但走不通 //7.當(dāng)map[6][5]=2時(shí)則說(shuō)明找到了出迷宮的路,否則繼續(xù)找路 //8.我們定義一個(gè)試探走的規(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.漢諾塔
相傳在古印度圣廟中,有一種被稱(chēng)為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上,有三根桿(編號(hào)A、B、C),在A桿自下而上、由大到小按順序放置n個(gè)金盤(pán)。游戲的目標(biāo):把A桿上的金盤(pán)全部移到C桿上,并仍保持原有順序疊好。操作規(guī)則:每次只能移動(dòng)一個(gè)盤(pán)子,并且在移動(dòng)過(guò)程中三根桿上都始終保持大盤(pán)在下,小盤(pán)在上,操作過(guò)程中盤(pán)子可以置于A、B、C任一桿上。
分析:對(duì)于這樣一個(gè)問(wèn)題,任何人都不可能直接寫(xiě)出移動(dòng)盤(pán)子的每一步,但我們可以利用下面的方法來(lái)解決。設(shè)移動(dòng)盤(pán)子數(shù)為n,為了將這n個(gè)盤(pán)子從A桿移動(dòng)到C桿,可以做以下三步:
(1)以C盤(pán)為中介,從A桿將1至n-1號(hào)盤(pán)移至B桿;
(2)將A桿中剩下的第n號(hào)盤(pán)移至C桿;
(3)以A桿為中介;從B桿將1至n-1號(hào)盤(pán)移至C桿。
import java.util.Scanner; public class HanoiTower{ public static void main(String []args ){ System.out.println("請(qǐng)輸入你要移動(dòng)的盤(pán)數(shù):"); tower m = new tower(); Scanner input = new Scanner(System.in); int num = input.nextInt(); m.moveWay(num,'A','B','C'); } } class tower{ //num表示要移動(dòng)的盤(pán)的個(gè)數(shù),a,b,c分別表示a塔,b塔,c塔 public void moveWay(int num,char a,char b,char c){ if(num == 1){//如果只有一個(gè)盤(pán),直接將其從a移動(dòng)到c System.out.println(a + "->" + c); } else {//如果有多個(gè)盤(pán)將最后一個(gè)盤(pán)以上的盤(pán)看成一個(gè)整體,借助c,移動(dòng)到b,然后將最后一個(gè)盤(pán)移到c moveWay(num-1, a, c, b); System.out.println(a + "->" + c); //然后再將b的所有盤(pán),借助a,移動(dòng)到c moveWay(num-1, b, a, c); } } }
3.八皇后
問(wèn)題表述為:在8×8格的國(guó)際象棋上擺放8個(gè)皇后,使其不能互相攻擊,即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上,問(wèn)有多少種擺法。
public class Queen8{ //第一個(gè)皇后先放在第一行第一列 //第二個(gè)放在第二行第一列,然后判斷是否發(fā)生沖突 //如果沖突,則繼續(xù)放第二列,第三列,依次直到找到不發(fā)生沖突的位置 //第三個(gè)皇后,還是按照第二個(gè)一樣依次找直到第八個(gè)皇后也能放在一個(gè)不發(fā)生沖突的地方,就算找到一個(gè)可行解。 //當(dāng)?shù)玫揭粋€(gè)可行解時(shí),回退到上一個(gè)棧開(kāi)始回溯,既可以得到第一個(gè)皇后放在第一列的所有可行解 //然后回頭繼續(xù)第一個(gè)皇后放在第二列,重復(fù)前面的操作 //用一個(gè)一維數(shù)組來(lái)表示皇后放置的位置 //列如arry[1]=3,表示第二個(gè)皇后放在第二行第四列 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個(gè)皇后 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ò)遞歸算法解決迷宮與漢諾塔及八皇后問(wèn)題的文章就介紹到這了,更多相關(guān)Java遞歸算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java Redis分布式鎖的正確實(shí)現(xiàn)方式詳解
這篇文章主要介紹了Java Redis分布式鎖的正確實(shí)現(xiàn)方式詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09Java中線程上下文類(lèi)加載器超詳細(xì)講解使用
這篇文章主要介紹了Java中線程上下文類(lèi)加載器,類(lèi)加載器負(fù)責(zé)讀取Java字節(jié)代碼,并轉(zhuǎn)換成java.lang.Class類(lèi)的一個(gè)實(shí)例的代碼模塊。本文主要和大家聊聊JVM類(lèi)加載器ClassLoader的使用,需要的可以了解一下2022-12-12Spring ApplicationListener監(jiān)聽(tīng)器用法詳解
這篇文章主要介紹了Spring ApplicationListener監(jiān)聽(tīng)器用法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11Springboot自動(dòng)掃描包路徑來(lái)龍去脈示例詳解
這篇文章主要介紹了Springboot自動(dòng)掃描包路徑來(lái)龍去脈示例詳解,本文通過(guò)示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-12-12Spring Security單項(xiàng)目權(quán)限設(shè)計(jì)過(guò)程解析
這篇文章主要介紹了Spring Security單項(xiàng)目權(quán)限設(shè)計(jì)過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11IntelliJ IDEA之配置JDK的4種方式(小結(jié))
這篇文章主要介紹了IntelliJ IDEA之配置JDK的4種方式(小結(jié)),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10