第一章 栈和队列(用栈来求解汉诺塔问题)

题目:

汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有n层的时候,打印最优移动过程和最优移动总步数。

输入描述:

输入一个数n,表示塔层数

输出描述:

按样例格式输出最优移动过程和最优移动总步数

输入
2

输出
Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.

package base;

import java.util.Stack;

public class Hannuota {

    public static void main(String[] args) {
        method(6);
    }

    public static void method(int num) {
        Stack<Integer> leftStack = new Stack<Integer>();
        Stack<Integer> midStack = new Stack<Integer>();
        Stack<Integer> rightStack = new Stack<Integer>();
        for (int i = num; i > 0; i--) {
            leftStack.push(i);
        }
        int count = 0;
        MoveAction[] actions = {MoveAction.NO};
        while (rightStack.size() != num) {
            count += moveMethod(actions, MoveAction.MTOL, MoveAction.LTOM, leftStack, midStack, "left", "mid");
            count += moveMethod(actions, MoveAction.LTOM, MoveAction.MTOL, midStack, leftStack, "mid", "left");
            count += moveMethod(actions, MoveAction.MTOR, MoveAction.RTOM, rightStack, midStack, "right", "mid");
            count += moveMethod(actions, MoveAction.RTOM, MoveAction.MTOR, midStack, rightStack, "mid", "right");
        }
        System.out.println(String.format("move %s times", count));
    }

    public static int moveMethod(MoveAction[] actions, MoveAction preNoAction, MoveAction nowAction, Stack<Integer> fromStack, Stack<Integer> toStack
            , String from, String to) {
        if (!actions[0].equals(preNoAction) && !fromStack.isEmpty()) {
            if (toStack.isEmpty() || fromStack.peek() < toStack.peek()) {
                Integer value = fromStack.pop();
                toStack.push(value);
                actions[0] = nowAction;
                System.out.println(String.format("move %s from %s to %s", value, from, to));
                return 1;
            }
        }
        return 0;
    }
}

enum MoveAction {
    NO, LTOM, MTOR, RTOM, MTOL;
}

上一篇:技术分享 | 为什么学习rrt_exploration实现自主建图容易掉坑?


下一篇:Java 老鼠走迷宫 汉诺塔