4

如您所知，有一些解决河内塔的方法，但它们要求所有磁盘一开始都在一个塔中。

现在我想知道有没有办法解决它，磁盘已经在开始时随机分布在塔之间。

4

5 回答 5

8

是的，它仍然可以解决（假设在较小的磁盘之上没有大磁盘）。例如：

        1
  4     2
  6     5     3
  -------------

找到包含 1 的最大连续堆栈。这里是 {1,2}。将该堆栈移动到下一个最大的磁盘上，忽略任何其他磁盘。您可以在此步骤中使用标准的汉诺塔算法。

              1
  4           2
  6     5     3
  -------------

重复上述步骤。下一个包含 1 的连续堆栈现在是 {1,2,3}。移动到 4

  1
  2
  3           
  4           
  6     5  
  -------------

同样的——将 {1,2,3,4} 移到 5 上。

        1
        2
        3     
        4     
  6     5    
  -------------

现在将 {1,2,3,4,5} 移到 6 上，就完成了。如果您需要将整个堆栈移动到特定的挂钩，请再次使用标准解决方案。

于 2012-01-18T13:46:32.397 回答
0

你的问题毁了我的生产力！

我只是花了我宝贵的时间试图回答它，结果如下：

首先，您必须计算每个磁盘想要去的位置，从最大到最小。有3个简单的规则要遵循：

  1. 最大的磁盘要向右移动。
  2. 如果稍大的磁盘移动，则磁盘想要“让开”（如果N+1想要从LEFT到MIDDLE，那么N想要到RIGHT）。
  3. 如果稍大的磁盘不移动，则磁盘想要前往相同的位置（如果N+1停留在RIGHT，则N想要前往RIGHT）。

然后将不想停留在其挂钩上的最小磁盘移动到其所需位置。（编辑：或者，您可以移动遇到的第一个想要执行合法移动的磁盘，但这意味着您的代码具有合法移动的概念）

迭代直到解决。

例子

让我们以贾斯汀为例。

初始塔

| | |
| | |
| | |
| 1 |
4 2 |
6 5 3
  • 6想要从LEFT到RIGHT（规则 1）。
  • 5想要从CENTER到CENTER（规则 2）。
  • 4想要从LEFT到CENTER（规则 3）。
  • 3想要从RIGHT到RIGHT（规则 2）。
  • 2想要从CENTER到RIGHT（规则 3）。
  • 1想要从CENTER到LEFT（规则 2）。

第一步必须将磁盘 1 放在左侧钉子上（不想留在原地的最小磁盘）。

下一个

接下来的动作将如下所示：

| | |
| | |
| | |
1 | |
4 2 |
6 5 3

| | |
| | |
| | |
1 | |
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
2 4 |
6 5 3

etc.

// TODO : commenting

我实施了这些规则，它们适用于任何初始塔（包括常规的左塔）。而且，他们总是选择最短的路径。

耶！解决河内塔的非递归方法！

于 2018-01-30T15:36:39.747 回答
0

我也不是专家，但考虑到这个问题，考虑到 AB 和 C 三个堆栈，并且作为前提，6 个磁盘必须在堆栈 C 中完成，就像河内最传统的塔一样，用 43 个动作解决了这个问题。我不知道这是否是最佳解决方案，但这里有一个非常有趣的 网站

于 2016-07-21T13:09:16.540 回答
0

当从较大的圆盘开始在较小的圆盘上时，获得解决方案没有任何限制（例如，圆盘可能以相反的顺序排列，最小的在底部，然后解决方案是微不足道的）。它确实让这个问题变得更有趣了，但这个谜题在某些时候确实开始看起来像一堆更大的圆盘和更小的圆盘。要移动一个常规的从小到大的堆来完成重新排序，通常有 2 个移动。如果要移动的圆盘数量是奇数，则首先将顶部（即最小）圆盘移动到所需位置，然后将下一个最小的圆盘移动到另一个钉子，然后将最小的圆盘放在上面，然后将下一个圆盘放在第一个是等等。如果要移动的圆盘数量是偶数，则应将最小的圆盘移动到不是所需位置的挂钩。当光盘的大小顺序随机时，可能会有一些捷径或一些复杂情况，但谜题仍然可以解决。我应该补充一点，随机开始游戏的目的只是让圆盘在任何挂钩上以正确的大小顺序排列，但很明显，可以应用常规递归算法将这样的堆栈移动到任何挂钩上。

于 2020-05-22T14:37:39.687 回答
0

任何法律安排的解决方案都遵循相同的模式。解决方案只有两种步骤：

  • 将给定的磁盘移动到 peg
  • 将给定的磁盘和比它小的所有东西移动到一个钉子上

要将磁盘移动到 peg，磁盘已经在 peg 上并且您已完成，或者磁盘不在 peg 上，并且只有一种方法可以完成此步骤：

  • 将所有较小的磁盘移动到剩余的第三个挂钩
  • 将给定磁盘从其当前 peg 转移到目标 peg

要将给定的磁盘和所有较小的磁盘移动到特定的挂钩，实现此目标的唯一方法是按顺序执行以下两个步骤

  • 将给定的磁盘移动到目标挂钩
  • 将所有较小的磁盘移动到目标挂钩
于 2016-07-21T15:25:52.880 回答