java - 汉诺塔 - 简单算法

Question

关闭。这个问题需要details or clarity .它目前不接受答案。












想改进这个问题？通过 editing this post 添加详细信息并澄清问题.

7年前关闭。




Improve this question




求解汉诺塔的简单递归代码:

public static void hanoi(char A, char B, char C, int n) {
  if(n>0) {
    hanoi(A,C,B,n-1);
    System.ouit.println("moving from " + A + " to " + B);
    hanoi(C,B,A,n-1);
 }
}

我和我的同学今天正在检查这段代码，虽然我们知道它是如何工作的，但我们无法理解算法，这意味着我们永远不会想到这样的解决方案。

我记得一位老师曾经说过，我们不在乎它是如何解决的，我们只是假设它是。他指的是函数调用自身的部分。

我知道我们基本上分两步解决汉诺塔。首先将所有环移动到 C(这是老师的代码，在这种情况下，我们想将所有环移动到 B 而不是 C)，然后将最大的环移动到 B，然后将所有剩余的环从 C 移动到 B。我明白在第一次调用中，我们从 A 移动到 C，在第二次调用中从 C 移动到 B。
我在纸上写了代码如何执行并得到正确的打印，但我仍然不明白。我明白，但我不明白，如果你明白我的意思。

ps:我检查了很多我发现的视频和链接，没有一个给我任何有值(value)的答案，你会如何突然想到这样的算法。这是不同的，例如斐波那契数列，这是合乎逻辑的。但是这个 ...

编辑:我什至很难解释我不明白的东西，我以前在编程方面从来没有遇到过问题。我知道这段代码是如何工作的，我可以把整个过程写在纸上。我知道如何解决汉诺塔。但是如果你给我一个任务来写一个汉诺塔的算法，我永远不会想到这个。我正在查看这段代码，我在说，这段代码到底是如何给出正确的打印输出的？我对这种信仰的飞跃有疑问，但不知何故，这就是递归的工作方式。基本上对于前两个环，我可以毫不费力地理解这个算法是有效的。但从那时起，移动戒指就不同了，因为你已经有两个戒指放在钉子上，你必须先移动它们，然后才能移动更多的戒指，然后把那些旧戒指放回去。嗯，到现在为止我在编程上从来没有遇到过问题，这真的很困扰我，因为这只是一个开始，它应该是如此简单和合乎逻辑，以至于我们的老师甚至都懒得解释它是如何工作的，他只是给了我们代码并移动了在。

Answer 1

想想对 hanoi 的调用功能为“使用主轴 C 作为备用，将整堆 n 磁盘从主轴 A 移动到主轴 B”。如果您愿意假设它可以完成，请将其概念化为函数调用。几分钟后应该很清楚，这可以通过移动桩来完成以上底部磁盘，具有 n-1磁盘，从主轴 A 到备用主轴 C，将底部磁盘移动到其目标主轴 B，然后将备用磁盘上的堆从 C 移动到 B。由于假设移动堆是函数调用，因此堆移动是通过底部磁盘移动之前和之后的递归调用来完成。剩下的唯一问题是识别何时没有更多工作要做。这是由您的n 完成的。计数器，它表示要移动的堆中磁盘的数量。当它为零时，不需要任何操作。

汉诺塔是“信仰的递归飞跃”的一个很好的例子，在这个例子中，您假设通过函数调用解决方案是可能的，然后只需将该函数应用于一个或多个子问题 + 一个微不足道的案例。