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

Question

我正在尝试解决 "towers of hanoi" 问题，该问题通过辅助堆栈将从最小到最大组织的磁盘堆栈从起始堆栈移动到目标堆栈，而无需放置更大的磁盘磁盘在较小的磁盘之上。

我得到了算法：

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）的算法

如果只有一张碟子要移动，就移动它然后停止*。
将 n - 1 个棋子从 S 移动到 A，D 移动
将第 n 个圆盘从 S 移动到 D
将n-1张棋子从A移动到D，S为

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

你提到 "I seem repeat the base case for every move." 如果你查看你的代码，并与我上面的陈述进行比较。你会看到你在我的第 3 步和第 4 步之间调用了 Move(1, start, destination, aux);。这就是为什么你要重复你的基本情况，因为你明确地调用，重复你的基本情况，但这没有任何意义。

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

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

为了响应给定的示例，在 post 的开头。它产生的输出与您的版本略有不同。

你的指定（或尝试）在每一步应该移动哪个大小的光盘，该示例仅指定将光盘从哪个堆栈移动到哪个堆栈，而不管其大小。

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

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

Recursive approach to solving the Towers of Hanoi puzzle

java

algorithm

recursion

towers-of-hanoi