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

Trying to understand Hanoi algorithm using my own program

我有以下河内塔的工作程序,我们将从 A--B 塔移动磁盘,C 是额外的 tower.I 定义函数的初始状态如下: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--CC--A 调用的,因为我从未进行过这样的 function/method。如果你能的话,我将不胜感激使用我的 A--B--CfromTower, toTower,auxTower 模型显示此递归方法如何在三个磁盘方面工作。

您仅从初始调用的角度考虑对 moveDisks 的可能调用:

moveDisks(.., 'A', 'B', 'C')

会打电话

moveDisks(.., 'A', 'C', 'B')
moveDisks(.., 'C', 'B', 'A')

但这些调用将继续递归,因此下一轮调用将是

moveDisks(.., 'A', 'B', 'C')
moveDisks(.., 'B', 'C', 'A')  --> moving B to C

moveDisks(.., 'C', 'A', 'B')
moveDisks(.., 'A', 'B', 'C')

...

我自己在last.I弄明白了,可以看到它惊人地遵循二叉树结构,首先调用最左边的child(在这种情况下,child是一个打印语句)在递归中。

我的理解错误是,我假设 A--B--C 为所有递归调用的 from-to-aux,尽管 from-to-aux 变量一直在变化 throughout.So当我从 n=3A= from,B=to, C= aux 开始时,我收到以下调用:moveDisks(2, 'A', 'C', 'B')moveDisks(2, 'C', 'B', 'A')。现在,这些递归调用中的每一个都将独立地开始它们自己的调用,但对于第一个现在一个 A=from, C=to, and B=aux 和第二个 C=from, B=to and A=aux。所以对于第一个我得到 moveDisks(1,'A','B','C')moveDisks(1,'B','C','A') 调用,第二个我得到 moveDisks(1,'C','A','B')moveDisks(1,'A','B','C') calls.Recurssion 继续,直到到达停止点。


注意:太神奇了!我学的是递归,结果也学了二叉树!