第Java通過(guò)遞歸算法解決迷宮與漢諾塔及八皇后問(wèn)題目錄1.遞歸的重要規(guī)則2.遞歸的三個(gè)案例1.老鼠出迷宮2.漢諾塔3.八皇后

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

在執(zhí)行一個(gè)方法時(shí)，就創(chuàng)建一個(gè)新的受保護(hù)的獨(dú)立空間(?？臻g)。方法的局部變量時(shí)獨(dú)立的，不會(huì)相互影響。如果方法中使用的是應(yīng)用類型變量(比如數(shù)組，對(duì)象)，就會(huì)共享該引用類型的數(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)找路徑，返回值為布爾類型，

//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è)下-右-上-左

publicclassMiGong{

publicstaticvoidmain(String[]args){

//迷宮初始化

int[][]map=newint[8][7];

for(inti=0;ii++){

map[0][i]=1;

map[7][i]=1;

for(intj=0;jj++){

map[j][0]=1;

map[j][6]=1;

map[3][1]=1;

map[3][2]=1;

for(intk=0;kmap.length;k++){

for(intm=0;mmap[k].length;m++){

System.out.print(map[k][m]+"");

System.out.println();

tway=newt();

way.findWay(map,1,1);

System.out.println("=====找到路徑后的地圖=====");

for(intk=0;kmap.length;k++){

for(intm=0;mmap[k].length;m++){

System.out.print(map[k][m]+"");

System.out.println();

classt{

publicbooleanfindWay(int[][]map,intx,inty){

if(map[6][5]==2){//遞歸出口若終點(diǎn)處的值為2則表明能找到一條路

returntrue;

}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

returntrue;

elseif(findWay(map,x,y+1))//否則還繼續(xù)看右邊能不能走

returntrue;

elseif(findWay(map,x-1,y))//上

returntrue;

elseif(findWay(map,x,y-1))//左

returntrue;

else{

map[x][y]=3;

returnfalse;

}else//map[x][y]=1,2,3

returnfalse;

2.漢諾塔

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

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

(1)以C盤為中介，從A桿將1至n-1號(hào)盤移至B桿；

(2)將A桿中剩下的第n號(hào)盤移至C桿；

(3)以A桿為中介；從B桿將1至n-1號(hào)盤移至C桿。

importjava.util.Scanner;

publicclassHanoiTower{

publicstaticvoidmain(String[]args){

System.out.println("請(qǐng)輸入你要移動(dòng)的盤數(shù)：");

towerm=newtower();

Scannerinput=newScanner(System.in);

intnum=input.nextInt();

m.moveWay(num,'A','B','C');

classtower{

//num表示要移動(dòng)的盤的個(gè)數(shù)，a,b,c分別表示a塔，b塔，c塔

publicvoidmoveWay(intnum,chara,charb,charc){

if(num==1){//如果只有一個(gè)盤，直接將其從a移動(dòng)到c

System.out.println(a+"-"+c);

else{//如果有多個(gè)盤將最后一個(gè)盤以上的盤看成一個(gè)整體，借助c，移動(dòng)到b，然后將最后一個(gè)盤移到c

moveWay(num-1,a,c,b);

System.out.println(a+"-"+c);

//然后再將b的所有盤，借助a，移動(dòng)到c

moveWay(num-1,b,a,c);

3.八皇后

問(wèn)題表述為：在88格的國(guó)際象棋上擺放8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。

publicclassQueen8{

//第一個(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è)皇后放在第二行第四列

intmax=8;

int[]arry=newint[max];

staticintcount=0;

publicstaticvoidmain(String[]args){

Queen8queen8=newQueen8();

queen8.locate(0);

System.out.print("擺法一共有："+count+"種");

//依次放入皇后，并判斷是否沖突

publicvoidlocate(intn){

if(n==max){

display();

return;

for(inti=0;imax;i++){

//先把皇后n放到第一列

arry[n]=i;

if(judge(n)){//不沖突則繼續(xù)放置第n+1個(gè)皇后

locate(n+1);

//如果沖突則繼續(xù)往后一列放置

publicbooleanjudge(intn){

for(inti=0;ii++){

//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(