溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
【題目】
漢諾塔問題比較經典，這里修改一下游戲規則：現在限制不能從最左側的塔直接移動到最右側，也不能從最右側直接移動到最左側，而是必須經過中間。求當塔有N層的時候，打印最優移動過程和最優移動總步數。
【解答】
上一篇用的是遞歸的方法解決這個問題，這里我們用棧來模擬漢諾塔的三個塔，也就是不用遞歸的方法
原理是這樣的：修改后的漢諾塔問題不能讓任何塔從左直接移動到右，也不能從右直接移動到左，而是要經過中間，也就是說，實際上能做的動作，只有四個：左->中，中->左，中->右，右->中
用棧來模擬漢諾塔的移動，其實就是某一個棧彈出棧頂元素，壓入到另一個棧中，作為另一個棧的棧頂，理解了這個就好說了，對于這個問題，有兩個原則：
一：小壓大原則，也就是，要壓入的元素值不能大于要壓入的棧的棧頂的元素值，這也是漢諾塔的基本規則
二：相鄰不可逆原則，也就是，我上一步的操作如果是左->中，那么下一步的操作一定不是中->左，否則就相當于是移過去又移回來
有了這兩個原則，就可以推導出兩個非常有用的結論：
1、游戲的第一個動作一定是L->M
2、在走出最小步數過程中的任何時刻，四個動作中只有一個動作不違反小壓大和相鄰不可逆原則，另外三個動作一定都會違反
【代碼實現】
import java.util.Stack;
class Demo{
public enum Action{
No,LToM,MToL,MToR,RToM
}
//num是盤子的數量，left，mid，right分別代表左中右三個柱子
public static int hanoi(int num,String left,String mid,String right){
//lS,mS,rS代表左中右三個棧（模擬柱子）
Stack<Integer> lS = new Stack<Integer>();
Stack<Integer> mS = new Stack<Integer>();
Stack<Integer> rS = new Stack<Integer>();
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是與現在所要進行的動作相反的動作，nowAct是現在所要進行的動作
public static int fStackToStack(Action[] record,Action preNoAct,Action nowAct,Stack<Integer> fStack,Stack<Integer> 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 + "步");
}
}
總結
以上就是本文關于Java編程用棧來求解漢諾塔問題的代碼實例（非遞歸）的全部內容，希望對大家有所幫助。感興趣的朋友可以參閱：Java 蒙特卡洛算法求圓周率近似值實例詳解、Java遺傳算法之沖出迷宮、Java實現四則混合運算代碼示例等，有什么問題可以隨時留言，歡迎大家交流討論。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
