【題目】
創(chuàng)新互聯(lián)公司主營(yíng)亭湖網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,手機(jī)APP定制開(kāi)發(fā),亭湖h5小程序定制開(kāi)發(fā)搭建,亭湖網(wǎng)站營(yíng)銷推廣歡迎亭湖等地區(qū)企業(yè)咨詢
漢諾塔問(wèn)題比較經(jīng)典，這里修改一下游戲規(guī)則：現(xiàn)在限制不能從最左側(cè)的塔直接移動(dòng)到最右側(cè)，也不能從最右側(cè)直接移動(dòng)到最左側(cè)，而是必須經(jīng)過(guò)中間。求當(dāng)塔有N層的時(shí)候，打印最優(yōu)移動(dòng)過(guò)程和最優(yōu)移動(dòng)總步數(shù)。
【解答】
上一篇用的是遞歸的方法解決這個(gè)問(wèn)題，這里我們用棧來(lái)模擬漢諾塔的三個(gè)塔，也就是不用遞歸的方法
原理是這樣的：修改后的漢諾塔問(wèn)題不能讓任何塔從左直接移動(dòng)到右，也不能從右直接移動(dòng)到左，而是要經(jīng)過(guò)中間，也就是說(shuō)，實(shí)際上能做的動(dòng)作，只有四個(gè)：左->中，中->左，中->右，右->中
用棧來(lái)模擬漢諾塔的移動(dòng)，其實(shí)就是某一個(gè)棧彈出棧頂元素，壓入到另一個(gè)棧中，作為另一個(gè)棧的棧頂，理解了這個(gè)就好說(shuō)了，對(duì)于這個(gè)問(wèn)題，有兩個(gè)原則：
一：小壓大原則，也就是，要壓入的元素值不能大于要壓入的棧的棧頂?shù)脑刂?，這也是漢諾塔的基本規(guī)則
二：相鄰不可逆原則，也就是，我上一步的操作如果是左->中，那么下一步的操作一定不是中->左，否則就相當(dāng)于是移過(guò)去又移回來(lái)
有了這兩個(gè)原則，就可以推導(dǎo)出兩個(gè)非常有用的結(jié)論：
1、游戲的第一個(gè)動(dòng)作一定是L->M
2、在走出最小步數(shù)過(guò)程中的任何時(shí)刻，四個(gè)動(dòng)作中只有一個(gè)動(dòng)作不違反小壓大和相鄰不可逆原則，另外三個(gè)動(dòng)作一定都會(huì)違反
【代碼實(shí)現(xiàn)】
重慶分公司
重慶分公司
import java.util.Stack;
class Demo{
public enum Action{
No,LToM,MToL,MToR,RToM
}
//num是盤子的數(shù)量，left，mid，right分別代表左中右三個(gè)柱子
public static int hanoi(int num,String left,String mid,String right){
//lS,mS,rS代表左中右三個(gè)棧（模擬柱子）
Stack lS = new Stack();
Stack mS = new Stack();
Stack rS = new Stack();
lS.push(Integer.MAX_VALUE);
mS.push(Integer.MAX_VALUE);
rS.push(Integer.MAX_VALUE);
for(int i=num;i>0;i--){
lS.push(i);
}
Action[] record = { Action.No };
int step = 0;
while(rS.size() != num+1){
step += fStackToStack(record,Action.MToL,Action.LToM,lS,mS,left,mid);
step += fStackToStack(record,Action.LToM,Action.MToL,mS,lS,mid,left);
step += fStackToStack(record,Action.MToR,Action.RToM,rS,mS,right,mid);
step += fStackToStack(record,Action.RToM,Action.MToR,mS,rS,mid,right);
}
return step;
}
//preNoAct是與現(xiàn)在所要進(jìn)行的動(dòng)作相反的動(dòng)作，nowAct是現(xiàn)在所要進(jìn)行的動(dòng)作
public static int fStackToStack(Action[] record,Action preNoAct,Action nowAct,Stack fStack,Stack tStack,String from,String to){
if(record[0] != preNoAct && fStack.peek() < tStack.peek()){
tStack.push(fStack.pop());
System.out.println("Move " + tStack.peek() + " " + from + "->" + to);
record[0] = nowAct;
return 1;
}
return 0;
}
public static void main(String[] args){
int i = hanoi(3,"left","mid","right");
System.out.println("一共走了" + i + "步");
}
} 總結(jié)
以上就是本文關(guān)于Java編程用棧來(lái)求解漢諾塔問(wèn)題的代碼實(shí)例（非遞歸）的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以參閱：Java 蒙特卡洛算法求圓周率近似值實(shí)例詳解、Java遺傳算法之沖出迷宮、Java實(shí)現(xiàn)四則混合運(yùn)算代碼示例等，有什么問(wèn)題可以隨時(shí)留言，歡迎大家交流討論。
