河内塔算法

Question

我对 Java 中的这个算法有疑问。例如，当您在主

hanoi(n, 'A', 'B', 'C')

中声明时，是否意味着

n

默认在

'A'

中？
例如，如果参数为 (

5

,

'A'

,

'B'

,

'C'

)，则

'A'

会是源并包含 5 个磁盘吗？
同样，如果参数是 (

4

,

'A'

,

'B'

,

'C'

)，

'A'

会是源并包含 4 个磁盘吗？
如果参数是

(int n, char source, char destination, char auxiliary)

，那么磁盘数量（

int n

）之后的第一个参数是否始终代表该阶段要移动的磁盘数量？
抱歉，如果我的问题不清楚...

public class TowerOfHanoi {

    public static void hanoi(int n, char source, char destination, char auxiliary) {
        if (n == 1) {
            System.out.println("Move disk 1 from tower " + source + " to tower " + destination);
            return;
        }
        hanoi(n - 1, source, auxiliary, destination);
        System.out.println("Move disk " + n + " from tower " + source + " to tower " + destination);
        hanoi(n - 1, auxiliary, destination, source);
    }

    public static void main(String[] args) {
        int n = 7; // Number of disks
        System.out.println("Solution for " + n + " disks:");
        hanoi(n, 'A', 'B', 'C'); // A is the source tower, C is the destination tower, B is the auxiliary tower
    }
}

我正在尝试理解这种基于河内塔的递归算法。

Answer 1

所以，如果我理解正确的话，您是在问该函数是否总是按该顺序获取输入。那么是的，你没看错！该函数始终按 n、源、目标和辅助的顺序接收输入，因为这就是它的定义方式。函数声明中参数的顺序决定了调用函数时必须提供参数的顺序。 例如，如果您要这样声明函数：

public static void hanoi(char destination, char source, char auxiliary, int n) { ... }

然后您需要按照目标、源、辅助、最后 n（源棒上的磁盘数量）的顺序传递参数。

Answer 2

是的，调用函数

hanoi

的目标和效果是将

n

磁盘从第一个给定堆 (A)（顶部）精确移动到最后一个给定堆（B）（顶部） .

这意味着在调用开始时，第一堆必须有 至少

n

磁盘。它可以拥有多于

n

的磁盘，但不能少于。如果它的数量较少，那么该函数最终将输出不可能进行的磁盘移动。

还有另一个假设。第一堆顶部的这些

n

圆盘必须是

n

最小 圆盘。

但是假设您从第一堆中的所有磁盘开始，这些都是在整个递归算法执行期间保证的不变量。