如何用汉诺塔调用递归

Question

我正在尝试解决汉诺塔问题；我写了这段代码：

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, from, other);
         move(disks - 1, other, to);
         }
   }
}

但是结果是错误的。我书中的解决方案是

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         move(disks - 1, from, other);
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, other, to);
         }
   }
}

这是为什么？我无法理解这些表达式的顺序：

先吧运行System.out.println()
然后它运行 move(disks - 1, from, other)
现在又是运行System.out.println()还是运行move(disks - 1, other, to)？

以及何时重启块代码？谢谢

Answer 1

正确的解法思路是：

首先，您必须递归地将最上面的 n-1 个棋子从挂钩 "from" 移动到挂钩 "other"。
然后您可以将底部圆盘从钉 "from" 移动到钉 "to" - 这就是 println 语句。
然后你必须将 n-1 个圆盘（在步骤 1 中移动）从钉 "other" 递归地移动到钉 "to"。

另一方面，您在错误的解决方案中试图做的是在移动底部圆盘之前移动堆叠在其上方的所有圆盘，这不是有效的移动。

Answer 2

河内塔的工作方式 -:

首先，您必须使用 3 将 n - 1 个磁盘从第 1 个移动到第 2 个挂钩。
将最后第 n 个磁盘移动到第 3 个挂钩。
使用第一个将 n-1 个圆盘从第二个柱子移动到第三个柱子上。

书中的解法是正确的。你的解法是错误的，因为你一开始就移动了最后一个盘子，这是违反汉诺塔规则的。希望你能明白。

经过一些修改后代码更加优雅和易于理解，它适用于任意 n。（由于它的指数复杂性，至少对于 n 的小值）

public class TowersOfHanoi {
   public static void main(String[] args) {
      int first = 1, second = 2, third = 3;
      int disk = 5; // or take user input
      move(disk, first, third);
   }

   public static void move(int disks, int first, int second, int third) {
      if (disks > 0) {
              move(disks - 1, first, third, second); // source = first, dest = second
              System.out.println("Move disk from peg " + first+ " to " + third);
              move(disks - 1, second, first, third);  // source = second, dest = third
         }
   }
}

Answer 3

所以我们有 n 个圆盘和 3 个柱子，我们想将放置在第一个柱子（源柱子）上的圆盘移动到第三个柱子（目标柱子）；本例中递归的概念是：

将所有圆盘递归地从 1 移动到 n-1 以上最大的（称为 n）从第一个钉到第二个（备用钉），因为我们想为最大的磁盘制作 space 并能够将其放在第三个挂钩上。这是第句move(disks - 1, from, other);
将所有圆盘移到最大圆盘上方后，我们将其移至第三个钉：如维基百科says这是简单的步骤，它是第二个句
System.out.println("Move disk from peg " + from + " to " + to);
最后，将所有 n-1 个圆盘从第二个柱子递归地移动到第三个柱子 ，以便在第三个柱子中重建塔 ，它的最后句move(disks - 1, other, to);

这个算法对偶数和奇数 n 圆盘都有效，因为它是一个通用的求解过程，显然步骤会根据圆盘的初始数量而改变。

如何用汉诺塔调用递归

How to call recursion with Tower of Hanoi

java

recursion

towers-of-hanoi