java - 汉诺塔递归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 个磁盘从"from"(源塔)移动到“其他”(中间塔)。
2. 然后将第 n 个磁盘从"from"(源塔)移动到“到”(目的地塔)。
3. 最后将n-1 个磁盘从"other"(中间塔)移动到< strong>“到”(目的地塔)。

您的 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 个磁盘从"from"(源塔)移动到“其他”(中间塔)。

2. 然后将 n-1 个磁盘从"other"(中间塔)移动到< em>“到”(目的地塔)。

3. 最后将第 n 个磁盘从"from"(源塔)移动到“到”(目的地塔)。

   In this strategy, after doing the 2 nd step (moving all n-1 disks from "other" to "to"), 3 rd step becomes invalid(moving n th disk from "from" to "to")! Because in Tower of Hanoy you cant put a larger disk on a smaller one!

所以选择第二个选项(策略)会导致你的策略无效，这就是为什么你不能这样做!