河内塔递归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你不能把较大的磁盘放在较小的磁盘上!

因此,选择第二个选项(策略)会导致您采用无效策略,这就是为什么您不能这样做的原因!