问题标签 [towers-of-hanoi]

在我看到的大多数实现中，使用递归解决方案。但是，我不想要这个。我想用搜索算法在树中搜索，比如广度优先或深度优先。

谢谢你

我只是在Java中测试河内塔问题，我运行了以下代码：（为方便起见，我已删除）sysouts

我做了一个实验，我尝试了从 1 到 35 的磁盘大小（索引），我观察到一个非常奇怪的时序模式，这是程序的输出：

问题 1：算法有指数增长(2^n-1)，那么为什么我看不到从 1-20 的时间逐渐增长？但是然后突然从20-35跳跃？

问题2：还有一件更让我吃惊的事情是成对的时间相等。从 19 日开始，(19,20)、(21,22)、(23,24)、(25,26) 等......有可比的时间。我无法理解这一点，如果算法的增长率确实是指数级的，为什么两个索引给出几乎可比的时间，然后在下一个索引处突然跳跃？

注意：我重复了这个程序 2-3 次，得到了几乎可比的时间，所以你可以把它当作一个平均运行。

编辑
尝试System.nanoTime()并得到以下结果：

输出几乎与毫秒相似，但它确实使画面清晰......回答我的问题 1可能是，但问题 2仍然很有趣。并System.nanoTime()提出了另一个问题：

问题 3：为什么索引 1 比下一个索引 (2,3...) 等花费更多时间？

这不是家庭作业，我没有钱上学，所以我一边在高速公路上的收费站轮班工作，一边自学（长夜，顾客很少）。

我正在尝试用 Java 实现 Hanoi Towers 求解器的简单版本。我正在使用堆栈和递归函数，没有咨询外部资源，以便有机会思考自己。

int[][] pegs我从一个数组数组（我会将光盘放在目标位置数组中。当然，Stack<Integer>它是为我执行此操作的数据结构，我不必跟踪任何内容。我编写了这个版本，但对放弃感到消极懒惰；我对伸展我的大脑并了解如何使用数组来完成这一切很感兴趣。

是否可以使用来实现此代码int[][] pegs？如何？（一个提示就足够了，我只是停留在方法上，确定正确的路径后我可以自己做腿部工作）。

顺便说一句，我编写的代码是“可通过的”Java 还是我在滥用东西？（我仍然不确定是专注于 Java 还是 C++。我有两者的电子书）。

我正在阅读 RobetSedwick 的 C++ 书中的算法。在这里，作者正在解释河内塔使用分而治之的设计和重现。

以下代码是问题的递归解决方案。它指定在每个步骤中应该移动哪个磁盘，以及在哪个方向上（+ 表示向右移动一个钉子，当在最右边的钉子上时，循环到最左边的钉子；和 - 表示向左移动一个钉子，循环到最左边的钉子。当在最左边的钉子上时，最右边的钉子）。

我的问题当磁盘位于左挂钩（即挂钩 1）上时，作者在“循环到最左边的挂钩”上方的意思是什么我们如何循环到最左边的挂钩？

作者还提到递归是基于以下思想：要将N个磁盘向右移动一个钉子，我们首先将顶部N-1个磁盘向左移动一个钉子，然后将N个磁盘向右移动一个钉子，然后移动N-1个磁盘再向左钉一个（在磁盘 N 上）。

我对上面的左右术语感到困惑。任何人都可以解释一下。

我正在阅读Robert Sedgewick 的算法

以下是第 213 页的摘录，涉及数字二进制表示中尾随零的数量。

对于 Hanoi 塔问题，与 n 位数对应的含义是该任务的简单算法。我们可以通过以下两个步骤将桩向右移动一个钉子，直到完成：

1. 如果 n 为奇数，则将小圆盘向右移动（如果 n 为偶数，则向左）
2. 进行不涉及小磁盘的唯一合法移动。

也就是说，在我们移动小 dsik 之后，另外两个 peg 包含两个磁盘，一个比另一个小。唯一不涉及小磁盘的合法移动是将较小的磁盘移动到较大的磁盘上。其他所有移动都涉及较小的磁盘，原因与其他所有数字都是奇数并且规则上的所有其他标记都是最短的相同。

上面的文字并没有进入我的脑海，即使在阅读了来自谷歌信息的各种参考资料之后。

请帮我举一个简单的例子，例如磁盘 N = 3。Disk3 最大，Disk1 最小，它们需要从 PegA 移动到 PegB。

我正在实施河内塔问题以了解更多关于递归的信息。我能够使用 3 peg 案例来实现它，但是，当我想使用更多 pegs（以产生更少的移动）时，我理解 Frame-Stewart 解决方案，我必须打破我拥有的磁盘数量并堆叠到一个peg上当我将磁盘从源钉转移到带有所有中间钉的目标钉时，切勿触摸该钉。但是，我不明白如何将 move(disks, 1, i, {2...K}) 之类的东西写成函数。当我从一开始都不知道它们时，如何在函数原型中写出所有钉子的名称？我在下面给出了我为 3 磁盘解决方案所做的工作，但我需要有关更一般情况的帮助。

我不明白我需要对我的“移动”功能做出什么样的改变来解决一个 6 钉的情况。谢谢

我能够提出一种算法（逻辑）来解决河内塔问题的 k-peg 解决方案，但是当我实现我的代码时，我遇到了分段错误。

这个想法很简单，我保留了一个免费的钉子（或塔）向量，并在我移动磁盘时更新它。所以对于 6 个 pegs 和 n 个磁盘的情况，我有一个源、一个目标和 4 个空闲 pegs。这个想法是将 (n - p) where p ~ n/2 从源移动到 free_peg[3] （第四个自由钉）。现在我的向量中只有 3 个空闲钉，我使用这 3 个空闲钉将 (n - p - 1) 个磁盘移动到 free_peg[2]，然后将最后一个磁盘从源移动到目标。所以现在我有 2 个免费挂钩和 1 个来源 = 3 个免费挂钩。接下来，我需要使用 3 个空闲的 peg（包括现在空闲的源）将 (n - p - 1) 个磁盘从 peg[2] 移动到目的地。最后，使用 4 个空闲 peg 将 p 个磁盘从 free_peg[3] 移动到目的地。但是，当我在我的代码中实现它时，我遇到了分段错误，有人可以帮我解决这个问题吗？

下面的代码使用预定义的函数 moveLOD、swapLOI 和 swapLID 解决了 hanoi 返回移动列表的问题。

MoveLOD：将 1 个圆盘从第一个位置移动到三联体第三个位置的第三个销。此外，包含有关移动信息的字符串正在字符串列表中堆积。

我正在尝试为 CS 家庭作业找出这个问题（我将其标记为家庭作业，我只需要朝着正确的方向迈出一步）。编辑：显然“家庭作业”标签已过时，不再使用。无论如何，我必须在 Prolog 中编写一个规则定义，确定给定的移动列表可以解决塔。我知道说明不好，我的教授很不清楚，但我所拥有的就是必须满足以下条件：

我一点也不知道上述任何内容应该暗示我做什么，所以任何指导都将不胜感激！它不会让我这样标记它，但是，就像我说的，这是一个家庭作业问题（尽管考虑到缺乏解释，这似乎是一个非常困难的问题），所以我不一定想要一个我想要的答案准确了解正在发生的事情。

非常感谢大家！！

我正在通过使用堆栈和链表来解决塔游戏，并通过使用递归将块从一个塔移动到另一个塔。

我在我的问题中遇到了一个导致 java.lang.NullPointerException 的问题。我猜为什么会发生这种情况是我尝试从堆栈中弹出值，即使没有条目。在我设置绑定控制后，我仍然收到该错误。

错误指向 deleteFirst() 方法的行，但即使在我检查列表是否为空之后，我也不明白为什么会发生这种情况。

我在这里的任务只是传递塔或 LinkedStack 对象，然后以塔游戏的方式移动它们的内容。

错误：

我在这里做错了什么？我无法完成这项工作。正如它应该。