java - 需要解释我的汉诺塔递归代码如何工作

Question

我刚刚开始学习递归，我想我对其工作原理有基本的了解。我有一个汉诺塔问题的代码，我已经盯着它看了一个小时，试图弄清楚它到底在做什么。 “moveDisks”方法让我感到困惑。我希望有人能帮助解释该方法中发生了什么。不是我写的。

为了尝试理解，我运行了代码并输入 2 作为磁盘数量。以下是打印出来的内容:

举措是:将磁盘 1 从 A 移动到 C，将磁盘 2 从 A 移动到 B，将磁盘 1 从 C 移动到 B

所以，如果我理解正确的话，2 将我们带到“else” block ，这意味着 2-1 将从 A 移动到 C。然后它再次减去 1 以进行另一次移动？我不明白接下来会发生什么，也不明白为什么需要交替塔。

import java.util.Scanner; 

public class TowersOfHanoi {
  /** Main method */
  public static void main(String[] args) {
    // Create a Scanner
    Scanner input = new Scanner(System.in);
    System.out.print("Enter number of disks: ");
    int n = input.nextInt();

    // Find the solution recursively
    System.out.println("The moves are:");
    moveDisks(n, 'A', 'B', 'C');
  }

  /** The method for finding the solution to move n disks
      from fromTower to toTower with auxTower */

  public static void moveDisks(int n, char fromTower,
      char toTower, char auxTower) {
    if (n == 1) // Stopping condition
      System.out.println("Move disk " + n + " from " +
        fromTower + " to " + toTower);
    else {
      moveDisks(n - 1, fromTower, auxTower, toTower);
      System.out.println("Move disk " + n + " from " +
        fromTower + " to " + toTower);
      moveDisks(n - 1, auxTower, toTower, fromTower);
    }
  }
}

Answer 1

递归是信仰的飞跃。重点是，您不需要尝试控制每一个小细节。您只需假设您已经编写了函数，并且它可以正常工作。然后你就用它。就这样。

所以，这是相反的归纳法。

无论是塔楼，你都认为它已经可供你使用。所以，搬家n磁盘从 A 到 B，您移动 (n-1)现在最大的磁盘仍然在 A，并且排列整齐 (n-1) C处的磁盘。B处是空的。只需将最后一个磁盘从 A 移动到 B，然后移动 (n-1)磁盘从 C 到 B。您已完成。

搬家没问题n-1磁盘即使磁盘 n躺在周围，因为所有 n-1磁盘小于 n ，所以磁盘 n可以安全地忽略。对于任何 m 也是如此, 0 < m < n .

搬家0磁盘更容易，而且也不违反任何法律。

<小时/>

对于您的具体问题，

And then it subtracts 1 again to do another move?

不，n还是一样，所以(n-1)两种情况都是一样的。

你交替使用塔楼，最终降落在正确的塔楼上。