algorithm - 河内改造塔

我们都知道，解决经典的汉诺塔问题所需的最少步数是 2n-1。现在，让我们假设一些光盘具有相同的大小。在这种情况下，解决问题的最少移动次数是多少？

例如，让我们假设有三张光盘。在经典问题中，所需的最小移动次数为 7。现在，让我们假设圆盘 2 和圆盘 3 的大小相同。在这种情况下，所需的最少移动次数为:

将光盘 1 从 a 移动到 b。

将光盘 2 从 a 移动到 c。

将光盘 3 从 a 移动到 c。

将光盘 1 从 b 移动到 c。

这是4个 Action 。现在，给定棋盘的总数 n 和具有相同大小的棋盘组，找到解决问题的最小移动次数。这是 friend 的挑战，因此欢迎提供解决方案的指针。谢谢。

最佳答案

让我们考虑一个大小为 n 的塔。顶部磁盘必须移动 2n-1 次，第二个磁盘 2n-2 次，依此类推，直到底部磁盘只需移动一次，总共移动 2n-1 次。移动每个磁盘只需要一圈。

   1      moved 8 times
  111     moved 4 times
 11111    moved 2 times
1111111   moved 1 time   => 8 + 4 + 2 + 1  ==  15

现在，如果 x 个磁盘具有相同的大小，则它们必须位于连续的层中，并且您总是将它们移向同一个目标堆栈，因此您也可以将它们折叠到一个磁盘上，需要移动 x 轮。如果您愿意，您可以将这些多磁盘视为“重”或“厚”的 x 倍。

   1
  111                       1      moved 8 times
  111       collapse       222     moved 4 times, taking 2 turns each
 11111    ----------->    11111    moved 2 times
1111111                  3333333   moved 1 time, taking 3 turns
1111111                            => 8 + 4*2 + 2 + 1*3  ==  21
1111111

现在把这些总结一下，你就有了答案。

下面是一些 Python 代码，使用上面的例子:假设你已经有一个“折叠”磁盘的列表，disks[i] 是 i 层中折叠磁盘的重量，你可以这样做:

disks = [1, 2, 1, 3]           # weight of collapsed disks, top to bottom
print sum(d * 2**i for i, d in enumerate(reversed(disks)))

相反，如果您有一个磁盘大小列表，例如左侧，则可以使用此算法:

disks = [1, 3, 3, 5, 7, 7, 7]  # size of disks, top to bottom
last, t, s = disks[-1], 1, 0
for d in reversed(disks):
    if d < last: t, last = t*2, d
    s = s + t
print s

在这两种情况下，输出都是 21 ，即所需的圈数。

关于algorithm - 河内改造塔，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24909612/

2N

algorithm - 河内改造塔