不使用缓冲堆栈的汉诺塔

Question

汉诺塔问题：

你有 3 个塔和 N 个圆盘可以滑到任何塔上的不同尺寸。

谜题从排序的磁盘开始按大小从上到下的升序排列（即，每个磁盘位于一个偶数的顶部大一点）。您有以下限制条件：

(1)一次只能移动一个磁盘。

(2) 一个圆盘从一个塔的顶部滑到下一根杆上。

(3) 一个磁盘只能放在一个更大的磁盘之上。编写一个程序，使用 Stacks 将磁盘从第一个塔移动到最后一个。

问题： 为什么我们需要 second/buffer/intermediate 堆栈？

我已经在不使用缓冲堆栈的情况下解决了这个问题。我使用了方法（递归）创建的隐式堆栈。

见代码：

public void play(Stack<Integer> aSourceStack,Stack<Integer> aTargetStack){

    if(aSourceStack.isEmpty()){
        return;
    }

    Integer temp = aSourceStack.pop();

    play(aSourceStack,aTargetStack);

    aTargetStack.push(temp);
}

我也违反了第二个约束：(2) 一个圆盘从一个塔的顶部滑到下一个杆上。

这是否意味着我不能将盘子存储在临时变量中？它只能进入堆栈？

如果是，那么我想我已经有了答案，我可以结束这个问题了。

请确认。

Answer 1

让我帮你搜索一下 ...这是一个classic puzzle.

您应该为每个塔使用 Stack class 的一个实例来实施解决方案。共有三座塔，因此您有三个 Stack 实例。是的，当您从一个塔顶弹出一个圆盘时，您必须立即将它推到下一个塔上。一个合适的陈述可能是

aTargetStack.push(aSourceStack.pop())

你写的代码没有解决问题；它依次将每个圆盘抛向空中，然后按所需顺序将它们推到目标堆栈上：N 个圆盘以 N 次移动。正确、理想的解决方案需要 2^N-1 步。

不使用缓冲堆栈的汉诺塔

Tower of Hanoi WITHOUT using a buffer stack

recursion

stack

towers-of-hanoi