题目:
汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有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;
}