5

这是我使用递归解决河内塔的 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);
4

2 回答 2

11

以这种方式解决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 个磁盘从“from”（源塔）移动到“other”（中间塔）。
  2. 然后将第n个圆盘从“from”（源塔）移动到“to”（目标塔）。
  3. 最后将n-1 个磁盘从“其他”（中间塔）移动到“到”（目标塔）。

你prinf基本上做了第二步。

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

    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 个磁盘从“from”（源塔）移动到“other”（中间塔）。

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

  3. 最后将第n个圆盘从“from”（源塔）移动到“to”（目标塔）。

    在此策略中，在执行第2步（将所有 n-1 个磁盘从"other"移动到"to"）之后，第 3步变得无效（将第n个磁盘从"from"移动到"to"）！因为Tower of Hanoy您不能将较大的磁盘放在较小的磁盘上！

所以选择第二个选项（策略）会导致你的策略无效，这就是你不能这样做的原因！

于 2013-05-11T04:08:13.053 回答
1

这确实很重要。递归调用之后的任何内容都将在递归展开之后执行（以及之前的任何内容，之前），因此您可能会发现您的输出顺序无意义。

请记住，函数调用之后的语句在函数返回之前不会执行。

于 2013-05-11T03:46:56.817 回答