河内递归塔Java

Question

这是我使用递归解决河内塔的Java代码：

/**here is a stack of N disks on the first of three poles (call
them A, B and C) and your job is to move the disks from pole A to pole B without
ever putting a larger disk on top of a smaller disk.*/

public class Hanoi {

    public static void main(String[] args) {
        playHanoi (2,"A","B","C");
    }

    //move n disks from position "from" to "to" via "other"
    private static void playHanoi(int n, String from , String other, String to) {
        if (n == 0)
            return;
        if (n > 0)
        playHanoi(n-1, from, to, other);
        System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);
        playHanoi(n-1, other, from, to);
    }

}

我放置打印方法的地方重要吗？另外，我可以这样做吗：

    playHanoi(n-1, from, to, other);
    playHanoi(n-1, other, from, to);
    System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);

Answer 1

Tower of Hanoy以这种方式解决问题，无非是定义如何完成工作的策略。和你的代码：

    playHanoi(n-1, from, to, other);
    System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);
    playHanoi(n-1, other, from, to);

基本上将您的策略​​定义为喜欢以下情况，

1. 将 _ n-1个 磁盘从 _ “从” （源塔）移动到 _ “其他”_ （中间塔）。
2. 然后将第 _ n 个磁盘从 _ “从” （源塔）移动到 _ “到”_ （目标塔）。
3. 最后将 _ n-1个 磁盘从 _ “其他” （中间塔）移动到 _ “到”_ （目标塔）。

你prinf基本上是使用 _ 2_ 档时。

现在，如果您编写这样的代码：

    playHanoi(n-1, from, to, other);
    playHanoi(n-1, other, from, to);
    System.out.printf("Move one disk from pole %s to pole %s \n ", from, to);

然后，您基本上在做：

1. 将 _ n-1个 磁盘从 _ “从” （源塔）移动到 _ “其他”_ （中间塔）。

2. 然后将 _ n-1个 磁盘从 _ “其他” （中间塔）移动到 _ “到”_ （目标塔）。

3. 最后，将第 _ n 个磁盘从 _ “从” （源塔）移动到 _ “到”_ （目标塔）。

在这种策略中，在做后 _ 2 次步骤（移动所有 n-1个 从磁盘 _ “其他” ，以 _ “至” ）， _3
第三步变为无效（移动 _ ñ 从第磁盘 _ “从” 到 _ “至”_ ）！因为Tower of Hanoy您不能将较大的磁盘放在较小的磁盘上！

因此，选择第二种选择（策略）会导致您采用无效策略，这就是为什么您不能这样做！