java - 解决汉诺塔难题的递归方法

Question

我正在尝试解决“汉诺塔”问题，该问题通过辅助堆栈将从最小到最大组织的磁盘堆栈从起始堆栈移动到目标堆栈，而无需在上面放置更大的磁盘一个较小的磁盘的顶部。

我得到了算法:

If numberDisks ==  1:
   Display “Move the top disk from  S to D”.
Else
  Move(numberDisks -1, ‘S’, ‘A’, ‘D’);
  Move(1, ‘S’, ‘D’, ‘A’);
  Move(numberDisks -1, ‘A’, ‘D’, ‘S’);

然而，这似乎不同于大多数其他 examples这似乎在不使用 Move(1, ‘S’, ‘D’, ‘A’) 的情况下工作；在递归函数中。

就我的代码而言，我似乎对每一步都重复了基本情况，我不确定如何构建我的打印语句以提供正确的输出，应该如下所示:

Move disk 1 from S to D
Move disk 2 from S to A
Move disk 1 from D to A
Move disk 3 from S to D
Move disk 1 from A to S
Move disk 2 from A to D
Move disk 1 from S to D

尝试移动 3 个磁盘时。

// Recursively solve Towers of Hanoi puzzle

public static void main(String[] args) {
    if (handleArguments(args)) {
        System.out.println("numDisks is ok");
        int numDisks = Integer.parseInt(args[0]);

        Move(numDisks,'s', 'a', 'd' );
    }
}

// recursive case
public static void Move(int disks, char start, char aux, char destination) {

    // base case
    if (disks == 1) {
        System.out.println("Move disk 1 from S to D");

        // if number of disks is 2 or greater
    } else if(disks > 1) {
        Move(disks - 1, start, aux, destination);
        System.out.println("move disk " + disks + " from " + start + " to " + destination);
        Move(1, start, destination, aux);
        Move(disks - 1, aux, destination, start);
    }
}

Answer 1

第一件事:理解移动n个圆盘(从S到D，带A)的算法

1. 如果只有一个圆盘要移动，就移动它然后停止*。
2. 用 D 将 n - 1 个圆盘从 S 移动到 A。
3. 将第 n 个圆盘从 S 移动到 D
4. 用 S 将 n - 1 个圆盘从 A 移动到 D。

*同样:如果有0个盘子，就停止。 (有些人会争辩说这是更好的终止条件，因为在您的代码中，它会阻止 print 语句当有一个特殊情况时，它将由您涵盖步骤 3 的 print 语句自然地处理。当，例如，您决定更改此方法以返回步骤列表而不是打印它，此更改只需在一个地方应用)

您提到“我似乎对每一步都重复基本情况”。如果您查看您的代码，并与我上面的陈述进行比较。你会看到你在我的第 3 步和第 4 步之间调用了 Move(1, start, destination, aux);。这就是为什么你要重复你的基本情况，因为你明确地调用，重复你的基本情况情况下，但这没有任何意义。

我看到的另一个主要问题:System.out.println("Move disk 1 from S to D"); 将始终按此顺序打印“S”和“D”，当您经常需要指定不同的移动时，确保使用此语句的参数。

我觉得没有别的了，试试看吧。

为了回应您在帖子开头给出的示例。它产生的输出与您的版本略有不同。

您指定(或尝试)在每个步骤中应移动哪个大小的圆盘，该示例仅指定将圆盘从哪个堆栈移动到哪​​个堆栈，而不管其大小。

中间以 1 作为参数的递归调用打印移动指令以移动堆栈中的最后一个圆盘(我的第 3 步)。