java - 如何用汉诺塔调用递归

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)？

以及何时重启 block 代码？谢谢。

Answer 1

汉诺塔的工作方式是-:

1. 首先，您必须使用 3 将 n - 1 个磁盘从第 1 个移动到第 2 个 Hook 。
2. 将最后第 n 个圆盘移动到第 3 个 Hook 。
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
         }
   }
}