问题标签 [towers-of-hanoi]

可能重复：
这是如何工作的？奇怪的河内塔解决方案

在浏览 Google 时，我发现了河内塔的这个有趣的解决方案，它甚至不使用堆栈作为数据结构。

谁能简要解释一下，它实际上在做什么？

这种解决方案真的可以接受吗？

代码

更新：硬编码的数字 3 在这里做什么？

目前我正在阅读 Douglas Crockford 的书，河内塔楼功能有点超出我的想象。即使将内容记录到控制台，我也无法真正理解发生了什么。这是我添加的功能：

这导致以下结果：

3
Src Dst
2
Src Aux
1
Src Dst
0
Src Aux
将光盘 1 从 Src 移动到 Dst
0
Aux Dst
将光盘 2 从 Src 移动到 Aux
1
Dst Aux
0
Dst Src
将光盘 1 从 Dst 移动到 Aux
0
Src Aux
将光盘 3 从 Src 移动到 Dst
2
Aux Dst
1
Aux Src
0
Aux Dst
将光盘 1 从 Aux 移动到 Src
0
Dst Src
将光盘 2 从 Aux 移动到 Dst
1
Src Dst
0
Src Aux
将光盘 1 从 Src 移动到 Dst
0
辅助目的地

我很早就迷路了。在结果的第 6 行，它如何从 Src Aux 回到 Src Dst？

当函数仅使用“disc - 1”调用自身时，一旦达到 0，磁盘数量如何再次增加？

how do i solve for running time in the towers of Hanoi problem. I get a recurrence realation like t(n) = 2t(n-1) + 1. After drawing the recursion tree i get at every step values like 1+2+4+8... the height of the tree will be lg(n). how do i calculate the sum of the series? when do i stop?

如果我对河内塔问题进行单元测试，最好的情况是什么？我可以测试该方法的参数和一般预期输出，但是否可以测试其他任何东西？

所以我可以测试：输出是正确的（算法有效），参数是正确的假设（即不为空），还有其他吗？

谢谢

我刚开始尝试学习编程，所以我正在当地的社区大学上课，我们必须制作河内塔的程序我一直在看书去图书馆并去辅导到目前为止这就是我来跟上。有人可以指出我正确的方向或给我一些帮助。

我的任务是添加一堆打印语句来显示河内塔的完整输出，以查看和了解它在幕后所做的事情，而不仅仅是给你最终结果。

这是我的输出。我唯一缺少的是indentation。我需要有一个用于第一级递归的选项卡，2 个用于第二级递归的选项卡等等......这就是我的意思：

电流输出：

期望的输出：

我需要某种计数器来“计算”我进入该功能的次数吗？但是，这甚至可以通过递归实现吗？也许我在分析什么时候有一个更简单的解决方案来解决这个问题？

规则

河内塔是一个谜，如果你不是很熟悉它，这里是它的工作原理：

游戏场由 3 根杆和x个圆盘组成，下一个比上一个大。这些圆盘可以放在杆上，规则如下：

• 一次只能移动一个磁盘，并且必须在另一个杆的顶部移动
• 必须从杆的顶部取出磁盘
• 磁盘可以移动到某个地方，只有当目标杆上最上面的磁盘大于要移动的磁盘时

最后 - 比赛场地是这样开始的：

• 一根带有x 个圆盘的棒，排序后最大的在底部，最小的在顶部
• 一根空棒
• 一根空棒

游戏的目标是将原始的“堆叠”磁盘移动到另一根杆上，即 - 将所有磁盘放在另一根杆上，因此（再次）最大的在底部，最小的在顶部

执行

您的目标是使用您选择的编程语言编写一个程序，该程序接受输入（如下所述）并输出解决位置所需的步骤。

与往常一样，尽量缩短它。

输入

示例输入：

输入是一个字符串，由 3 部分组成，用逗号分隔。这些零件是 3 根杆中每根杆上的磁盘列表。它们也是分开的，这次用连字符（ - ），每个子部分都是一个数字，数字越大，磁盘越大。

所以 - 对于上述输入，这将是一个视觉表示：

输出

正如您在上面的表示中看到的 - 输入的最左侧部分是一号杆，中间是二号杆，最后一个是三号杆。

您的程序的输出应如下所示：

一个数字列表，用逗号分隔，定义了应该取出磁盘的杆，以及应该放置磁盘的杆。只有 3 个杆，所以只有 6 种可能的组合（因为必须将磁盘移动到另一个杆，而不是同一个杆）：

笔记

输入不必描述处于“原始”状态的字段 - 它可以是中间解决的。

您的程序不能产生空输出。如果输入处于原始状态，只需将磁盘放在不同的杆上。

输入可以有一个空棒，如下所示：

如果输入不是这种格式，您的程序可能会产生未定义的行为。因此，如果输入无效（例如较小的磁盘上的较大磁盘，丢失磁盘，无法解决），它可以。输入将始终有效。

确保解决方案尽可能快（尽可能少转弯）-也就是说，不要浪费“12,21,12”的转弯......

测试

所以，我为你准备了这个小闪存，你可以用它来测试你的程序是否产生了一个好的解决方案，而无需写下它或任何东西。

这里是：Hanoi AlgoTest（等待它加载然后刷新——死链接：|）

要使用它，请将程序的输入粘贴到INPUT字段，并将程序产生的输出粘贴到PROCESS字段。它将以您也可以更改的速度运行模拟，并以视觉表示形式打印出底部的任何错误。

希望能帮助到你。

我通读了一些关于河内塔问题的讨论。我理解使用以下代码的递归解决方案：

我真正需要做的是在每一步输出某种类型的塔的“插图”。我很难做到这一点。我们的讲师建议使用堆栈来跟踪哪个磁盘在哪个塔上，但是我在输出这个时遇到了麻烦，因为在堆栈中查找和输出值需要弹出顶部条目并删除它们。如果我理解正确，他们会迷路。

无论哪种方式，它都让我找到了一些这样开始的解决方案：

我很清楚这是错误的。我不确定用磁盘号填充源的好地方在哪里。而且我每次都传递相同大小的源堆栈。如果有人能给我一些方向或任何东西，那就太酷了。谢谢你。

假设有 2*n 个磁盘，如果奇数是“A”柱上的磁盘，而偶数磁盘是“B”柱上的磁盘，如何解决河内问题？如果需要更多信息，请告诉我。

谢谢

我为河内塔问题开发了一个解决方案：

它工作正常。现在我想限制幻灯片的数量并在达到某个限制时抛出异常。我用计数器尝试过，但它不起作用：

永远不会抛出异常。有任何想法吗？

更新：结果是 6 张幻灯片，但应该是 5 张 http://ideone.com/lm084