algorithm - 这是如何运作的？河内奇怪的塔解决方案

Question

当我发现 this 时，我在互联网上迷路了汉诺塔的不寻常的迭代解决方案:

for (int x = 1; x < (1 << nDisks); x++)
{
     FromPole = (x & x-1) % 3;
     ToPole = ((x | x-1) + 1) % 3;
     moveDisk(FromPole, ToPole);
}

This post其中一个答案中也有类似的Delphi代码。

然而，对于我的一生，我似乎无法找到一个很好的解释来解释为什么会这样。

谁能帮我理解一下？

Answer 1

Hanoi 塔的递归解决方案是这样的，如果你想将 N 个圆盘从钉 A 移动到 C，你首先将 N-1 从 A 移动到 B，然后将底部的一个移动到 C，然后你移动从 B 到 C 又是 N-1 个磁盘。本质上，

hanoi(from, to, spare, N):
  hanoi(from, spare, to, N-1)
  moveDisk(from, to)
  hanoi(spare, to, from, N-1)

显然 hanoi( _ , _ , _ , 1) 走一步，而 hanoi ( _ , _ , _ , k) 走的步数与 2 * hanoi( _ , _ , _ , k-1) + 1 一样多. 所以解长度按顺序 1, 3, 7, 15, ... 这与 (1 << k) - 1 的顺序相同，这解释了你发布的算法中循环的长度。

如果您查看解决方案本身，对于 N = 1，您会得到

FROM   TO
          ; hanoi(0, 2, 1, 1)
   0    2    movedisk

对于 N = 2 你得到

FROM   TO
          ; hanoi(0, 2, 1, 2)
          ;  hanoi(0, 1, 2, 1)
   0    1 ;   movedisk
   0    2 ;  movedisk
          ;  hanoi(1, 2, 0, 1)
   1    2 ;   movedisk

对于 N = 3 你得到

FROM   TO
          ; hanoi(0, 2, 1, 3)
          ;  hanoi(0, 1, 2, 2)
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk
   0    1 ;   movedisk
          ;   hanoi(2, 1, 0, 1)
   2    1 ;    movedisk
   0    2 ;  movedisk ***
          ;  hanoi(1, 2, 0, 2)
          ;   hanoi(1, 0, 2, 1)
   1    0 ;    movedisk
   1    2 ;   movedisk
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk

由于解决方案的递归性质，FROM 和 TO 列遵循递归逻辑:如果您采用列的中间条目，则上面和下面的部分是彼此的副本，但数字排列。这是算法本身的一个明显结果，它不对 Hook 数字执行任何算术，而只是排列它们。在 N=4 的情况下，中间行位于 x=4(上面标有三颗星)。

现在表达式 (X & (X-1)) 取消设置 X 的最小设置位，因此它映射到例如数字从 1 到 7 如下所示:

   1 ->  0
   2 ->  0
   3 ->  2
   4 -> 0 (***)
   5 ->  4 % 3 = 1
   6 ->  4 % 3 = 1
   7 ->  6 % 3 = 0

诀窍在于，由于中间行始终是 2 的精确幂，因此恰好设置了一位，所以当您添加中间行值(在本例中为 4)时，中间行之后的部分等于它之前的部分) 到行(即 4=0+4、6=2+6)。这实现了“复制”属性，中间行的添加实现了排列部分。表达式 (X | (X-1)) + 1 设置右边有 1 的最低零位，并清除这些零位，因此它具有与预期类似的属性:

   1 ->  2
   2 ->  4 % 3 = 1
   3 ->  4 % 3 = 1
   4 -> 8 (***) % 3 = 2
   5 ->  6 % 3 = 0
   6 ->  8 % 3 = 2
   7 ->  8 % 3 = 2

至于为什么这些序列实际上产生了正确的 Hook 编号，让我们考虑 FROM 列。递归解从 hanoi(0, 2, 1, N) 开始，所以在中间行 (2 ** (N-1)) 你必须有 movedisk(0, 2)。现在根据递归规则，在 (2 ** (N-2)) 你需要有 movedisk(0, 1) 和在 (2 ** (N-1)) + 2 ** (N-2) movedisk ( 1, 2).这为从钉子创建了“0,0,1”模式，在上表中以不同的排列可见(检查第 2、4 和 6 行的 0,0,1 和第 1、2、3 行的 0,0 ,2，以及 1,1,0 的第 5、6、7 行，都是同一模式的所有排列版本)。

现在，在所有具有此属性的函数中，它们围绕 2 的幂创建自身的副本但带有偏移量，作者选择了那些产生模 3 正确排列的函数。这不是一项非常困难的任务，因为三个整数 0..2 只有 6 种可能的排列，并且排列在算法中按逻辑顺序进行。 (X|(X-1))+1 不一定与河内问题密切相关，或者不需要；它具有复制属性并且恰好以正确的顺序产生正确的排列就足够了。