java - 尝试使用我自己的程序来理解 Hanoi 算法

Question

我有以下汉诺塔的工作程序，我们将从 A--B 塔移动磁盘，C 是额外的塔。我定义函数的初始状态如下:moveDisks(n, 'A', 'B', 'C');

每次移动时我都会使用以下算法进行打印:

public static void moveDisks(
        int n,
        char fromTower,
        char toTower,
        char auxTower)
    {
        if (n == 1) // Stopping condition
            System.out.println(
                "Move disk " + n + " from " + fromTower + " to " + toTower);
        else
        {
            moveDisks(n - 1, fromTower, auxTower, toTower);
            System.out.println(
                "Move disk " + n + " from " + fromTower + " to " + toTower);
            moveDisks(n - 1, auxTower, toTower, fromTower);
        }
    }
}

正如您从我的程序中的递归调用中看到的，我有三种可能的调用:

    A--B--C //fromTower, toTower,auxTower
    A--C--B //fromTower, auxTower, toTower
    C--B--A //auxTower, toTower, fromTower

但是，我收到了以下 3 的打印输出磁盘:

The moves are:
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

我知道我的程序是正确的，但我并没有真正了解它是如何做的 B--C和C--A调用，因为我从未做过这样的函数/方法。如果您能使用我的 A--B--C 展示此递归方法如何在三个磁盘方面工作，我将不胜感激, fromTower, toTower,auxTower型号。

Answer 1

我自己终于弄清楚了这一点。我可以看到它惊人地遵循二叉树结构，在递归中首先调用最左边的子节点(在本例中，子节点是打印语句)。

我理解的错误是，我假设所有递归调用的 A--B--C 为 from-to-aux，尽管from-to-aux 变量始终在变化。因此，当我从 n=3 和 A= from,B=to, C= aux 开始时code>，我收到以下调用: moveDisks(2, 'A', 'C', 'B') 和 moveDisks(2, 'C', 'B', 'A ')。现在，每个递归调用都将独立启动自己的调用，但第一个调用现在 A=from、C=to 和 B=aux ，第二个调用 >C=from、B=to 和 A=aux。因此，对于第一个，我得到 moveDisks(1,'A','B','C') 和 moveDisks(1,'B','C','A') 调用，第二个我得到 moveDisks(1,'C','A','B') 和 moveDisks(1,'A','B','C') 调用。递归继续，直到到达停止点。

---

注意:这太神奇了!我正在学习递归，但最终也学习了二叉树!