algorithm - 修改后的汉诺塔

Question

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

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

1. 将圆盘 1 从 a 移动到 b。
2. 将圆盘 2 从 a 移到 c。
3. 将圆盘 3 从 a 移动到 c。
4. 将圆盘 1 从 b 移动到 c。

这是 4 个 Action 。现在，给定棋子总数 n 和大小相同的棋子组，找出解决该问题的最少步数。这是一个 friend 的挑战，所以欢迎指点解决方案。谢谢。

Answer 1

让我们考虑一个大小为 n 的塔.顶部磁盘必须移动 2^n-1 次，第二个磁盘 2^n-2 次，依此类推，直到底部磁盘只需移动一次, 总共 2ⁿ-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 , 所需的圈数。