package stackAndQueue;import java.util.Stack;/*** 用棧來求解漢諾塔問題：HanoiStack【3】* * 【問題描述】：將漢諾塔游戲（小壓大）規則修改，不能從左（右）側的塔直接移到右（左）側，而是必須經過中間塔。* * 求當塔有N層時，打印最優移動過程和最優移動步數。如N=2，記上層塔為1，下層為2.則打印：1：left->mid;1* * 由于必須經過中間，實際動作只有4個：左L->中M，中->左，中->右R，右->中。* * 原則：①小壓大；②相鄰不可逆（上一步是L->M,下一步絕不能是M->L）* * 非遞歸方法核心結論：1.第一步一定是L-M；2.為了走出最少步數，四個動作只可能有一個不違反上述兩項原則。* * 核心結論2證明：假設前一步是L->M（其他3種情況略）* * a.根據原則①，L->M不可能發生；b.根據原則②，M->L不可能；c.根據原則①，M->R或R->M僅一個達標。* * So，每走一步只需考察四個步驟中哪個步驟達標，依次執行即可。* * @author xiaofan*/ public class HanoiStack {private enum Action {None, LToM, MToL, MToR, RToM};static Action preAct = Action.None; // 上一步操作，最初什么移動操作都沒有final static int num = 4; // 漢諾塔層數public static void main(String[] args) {int steps = transfer(num);System.out.println("It will move " + steps + " steps.");}private static int transfer(int n) {Stack<Integer> lS = new Stack<>(); // java7菱形用法，允許構造器后面省略范型。Stack<Integer> mS = new Stack<>();Stack<Integer> rS = new Stack<>();lS.push(Integer.MAX_VALUE);// 棧底有個最大值，方便后續可以直接peek比較mS.push(Integer.MAX_VALUE);rS.push(Integer.MAX_VALUE);for (int i = n; i > 0; i--) {lS.push(i);// 初始化待移動棧}int step = 0;while (rS.size() < n + 1) {// n+1,因為rS.push(Integer.MAX_VALUE);等于n+1說明全部移動完成step += move(Action.MToL, Action.LToM, lS, mS);// 第一步一定是LToMstep += move(Action.LToM, Action.MToL, mS, lS);// 只可能有這4種操作step += move(Action.MToR, Action.RToM, rS, mS);step += move(Action.RToM, Action.MToR, mS, rS);}return step;}/*** 實施移動操作.* * @param cantAct* 不能這樣移動* @param nowAct* 即將執行的操作* @param fromStack* 起始棧* @param toStack* 目標棧* @return step(成功與否)*/private static int move(Action cantAct, Action nowAct, Stack<Integer> fromStack, Stack<Integer> toStack) {if (preAct != cantAct && toStack.peek() > fromStack.peek()) {toStack.push(fromStack.pop()); // 執行移動操作System.out.println(toStack.peek() + ":" + nowAct);preAct = nowAct; // 更新“上一步動作”return 1;}return 0;} }

代碼地址：https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue

總結

以上是生活随笔為你收集整理的用栈来求解汉诺塔变形问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。