河内的改良塔 [英] Modified Tower of Hanoi

问题描述

我们都知道，解决河内经典塔楼问题所需的最少动作数是2 ⁿ -1.现在，让我们假设某些光盘的大小相同.在这种情况下，解决问题的最少动作数是多少.

We all know that the minimum number of moves required to solve the classical towers of hanoi problem is 2ⁿ-1. Now, let us assume that some of the discs have same size. What would be the minimum number of moves to solve the problem in that case.

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

Example, let us assume that there are three discs. In the classical problem, the minimum number of moves required would be 7. Now, let us assume that the size of disc 2 and disc 3 is same. In that case, the minimum number of moves required would be:

1. 将光盘1从a移到b.
2. 将光盘2从a移到c.
3. 将光盘3从a移到c.
4. 将光盘1从b移到c.

这是4个动作.现在，给定光盘总数n和大小相同的光盘组，找到最小移动量即可解决该问题.这是朋友的挑战，因此欢迎您提出解决方案.谢谢.

which is 4 moves. Now, given the total number of discs n and the sets of discs which have same size, find the minimum number of moves to solve the problem. This is a challenge by a friend, so pointers towards solution are welcome. Thanks.

推荐答案

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

Let's consider a tower of size n. The top disk has to be moved 2^n-1 times, the second disk 2^n-2 times, and so on, until the bottom disk has to be moved just once, for a total of 2ⁿ-1 moves. Moving each disk takes exactly one turn.

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

现在，如果 x 磁盘具有相同的大小，则它们必须位于连续的层中，并且您将始终将它们移至相同的目标堆栈，因此您也可以将它们折叠成一个磁盘，需要移动 x .如果愿意，您可以将这些多磁盘视为重"或厚"的 x 倍.

Now if x disks have the same size, those have to be in consecutive layers, and you would always move them towards the same target stack, so you could just as well collapse those to just one disk, requiring x turns to be moved. You could consider those multi-disks to be x times as 'heavy', or 'thick', if you like.

   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

现在，只需对它们进行总结，即可得到答案.

Now just sum those up and you have your answer.

使用上面的示例，这里有一些Python代码:假设您已经有了折叠"磁盘的列表，其中disks[i]是第i层中折叠磁盘的重量，您可以执行此操作:

Here's some Python code, using the above example: Assuming you already have a list of the 'collapsed' disks, with disks[i] being the weight of the collapsed disk in the ith layer, you can just do this:

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

相反，如果您有磁盘大小的列表(如左侧)，则可以使用以下算法:

If instead you have a list of the sizes of the disks, like on the left side, you could use this algorithm:

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，即所需的匝数.

Output, in both cases, is 21, the required number of turns.

这篇关于河内的改良塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！