这是如何工作的？

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

河内塔的递归解决方案可以工作，因此如果您想将N个磁盘从挂钩A移动到C，您首先将N-1从A移动到B，然后将底部移动到C，然后您移动再次N-1从乙磁盘C.在本质上，

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

显然河内（_，_，_，1）需要一个移动和河内（_，_，_，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列遵循递归逻辑：如果您采用中间条目在列上，上面和下面的部分是每个其他部分的副本，但排列的是数字。这是算法本身的一个显而易见的结果，它不对挂钩数字执行任何算术运算，而只是对它们进行置换。在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 

诀窍是，因为中间行始终在两个精确的功率，因此只能有一个位集，中间行之后的部分才等于部分当您将中间行值（在这种情况下为4）添加到行（即4 = 0 + 4,6 = 2 + 6）时。这实现了“复制”属性，中间行的添加实现了排列部分。表达式（X |（X-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 

至于为什么这些序列实际上会生成正确的挂钩编号，让我们考虑一下FROM列。递归解决方案以河内（0,2,1，N）开始，所以在中间行（2 **（N-1）），您必须有移动（0,2）。现在通过递归规则，在（2 **（N-2））你需要有移动（0,1）和在（2 **（N-1））+ 2 **（N-2）移动1,2）。这为上面的表中不同排列的pegs创建了“0,0,1”模式（针对0,0,1检查行2,4和6，针对0,0检查行1,2,3） ，2和1,1,6行的5,6,7行，同一模式的所有置换版本）。

现在，所有具有这个属性的函数，他们创造了他们自己的权力两个权力，但与偏移量，作者选择那些产生模3正确的排列。这不是一个过分困难的任务，因为三个整数0..2只有6个可能的排列，并且排列在算法中按逻辑顺序进行。 （X |（X-1））+ 1并不一定与河内问题有深层次的联系，也可能不需要;它具有复制属性就足够了，并且它恰好以正确的顺序产生正确的排列。

Answer 2

这不是直接回答这个问题，但是发表评论太长了。

我一直都是通过分析下一步应该移动的磁盘的大小来做到这一点的。如果你看一下移动磁盘，它出来到：

1 disk : 1 
2 disks : 1 2 1 
3 disks : 1 2 1 3 1 2 1 
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 

奇大小总是甚至那些相反的方向移动，以便如果钉（0，1，2，重复）或（2，1 ，0，重复）。

如果在模式看一看，环移动的最高位设置的移动次数和+ 1

Answer 3

antti.huima的解决方案基本上是正确的移动次数的xor的，但我想要更严格的东西，这太大了，不适合发表评论。这里所说：

首先说明：在中间步骤x = 2 ^{N-1，该算法的}， “从” PEG是0，并且 “到” PEG是2 ^Ñ％3.本叶2 ^（N-1）％3为“备用”挂钩。 对于算法的最后一步也是如此，所以我们发现实际上作者的算法 是一个轻微的“作弊”：它们将磁盘从挂钩0移动到挂钩2而不是挂钩，而不是一个固定的， 预先指定“to”挂钩。这可以改变，没有太多的工作。

原始河内算法是：

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

在堵 “由”= 0， “到”= 2 ^Ñ％3， “备用”= 2 ^N-1％3，我们得到（抑制％3'S）：

hanoi(0, 2**N, 2**(N-1), N): 
(a) hanoi(0, 2**(N-1), 2**N, N-1) 
(b) move(0, 2**N) 
(c) hanoi(2**(N-1), 2**N, 0, N-1) 

基本这里的观察是： 在线（c）中，PEG是河内（0的完全钉，2 ^N-1，2 ^N，N-1）移位了2 ^N-1％3，即 它们正好是线（a）的挂钩，这个数量加到它们。

我要求它遵循的是，当我们 运行线（c）中，“从”和“到” PEG是行的相应钉（a）以2 ^N-1％3.本 移从hanoi(a+x, b+x, c+x, N)这个简单的，更一般的引理可以看出，“from”和“to pegs完全从hanoi(a, b, c, N)中移出x。

现在考虑的功能
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

要证明给定的算法的工作，我们只需要表明：

• F（2 ^N-1）== 0和g（2 ^N-1）== 2 ^N
• for 0 < <我2 ^Ñ，我们已经F（2 ^Ñ - ⅰ）== F（2 ^Ñ + I）+ 2 ^Ñ％3，和g（2 ^Ñ - ⅰ）==克（2 ^ñ + I）+ 2 ^ñ％3.

两者都是容易显现。