这是怎么工作的?河内诡异之塔解决方案

河内塔楼的递归解决方案是这样的,如果你想将n个磁盘从PEG A移动到C,首先将n-1从A移动到B,然后将底部的一个移动到C,然后再将n-1磁盘从B移动到C。本质上,

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

很明显,河内(_uuuuu1)采取了一个动作,河内(_uuuuk)采取的动作多达2个*河内(_uuuuuuk-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

由于解决方案的递归性质,从列和到列遵循递归逻辑:如果在列上取中间条目,则上面和下面的部分是彼此的副本,但要排列数字。这是算法本身的一个明显结果,它不对peg数执行任何运算,只对它们进行排列。在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)时,中间行后面的部分等于它前面的部分。这实现了“copy”属性,中间行的添加实现了排列部分。表达式(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

至于为什么这些序列实际产生正确的peg数,让我们考虑一下from列。递归解决方案从河内(0,2,1,n)开始,因此在中间一行(2**(n-1))必须有movedisk(0,2)。现在根据递归规则,at(2**(n-2))需要有movedisk(0,1)和at(2**(n-1))+2**(n-2)movedisk(1,2)。这将为从PEG创建“0,0,1”模式,该模式在上表中以不同排列方式可见(在第2、4和6行中检查0,0,1,在第1、2、3行中检查0,0,2,在第5、6、7行中检查1,1,0,所有排列版本都相同)。

现在,在所有具有这一性质的函数中,作者都选择了那些产生模3的正确排列的函数,这些函数的复制是围绕两次幂(但带有偏移量)创建的。这不是一个非常困难的任务,因为在算法中,三个整数0..2只有6个可能的排列,排列按逻辑顺序进行。(x(x-1))+1不一定与河内问题有深刻的联系,也不必如此;它具有复制性质,并且恰好以正确的顺序产生正确的排列就足够了。

Huima的解决方案基本上是正确的,但我想要更严格的解决方案,而且它太大了,不适合发表评论。下面是:

第一个注意事项:中间步骤x=2 ^N-1 在该算法中,“从”Peg为0,“到”Peg为2。 ⁿ % 3。这留下2 ^(n-1) %3用于“备用”销钉。 对于算法的最后一步也是如此,所以我们看到了作者的算法 有点“欺骗”:他们正在将磁盘从PEG 0移动到PEG 2 ⁿ %3,而不是固定的, 预先指定的“到”栓。这可以用很少的工作来改变。

最初的河内算法是:

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的):

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)行中,标桩正是河内的标桩(0,2 ^N-1型 ,2 ⁿ ,n-1)移动2 ^N-1 % 3,即 它们正是(a)行中加上这个数量的挂钩。 .

我声称当我们 运行线(c),“从”和“到”标桩是(a)线的相应标桩,移动2 ^N-1 %第三条:这个 从简单的,更一般的引理 hanoi(a+x, b+x, c+x, N) “从”和“到”的标桩精确地从“in”移到“x”。 hanoi(a, b, c, N) .

现在考虑函数
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

为了证明给定的算法有效,我们只需证明:

• F(2) ^N-1 =0和g(2) ^N-1 = 2 ⁿ
• 对于0<I<2 ⁿ ,我们有F(2 ⁿ -i==f(2) ⁿ +i)+ 2 ⁿ % 3,G(2) ⁿ -i==g(2) ^N号 +i)+ 2 ⁿ % 3。

这两个都很容易展示。

这不是直接回答问题,但发表评论时间太长。

我总是通过分析下一个应该移动的磁盘的大小来完成这项工作。如果您查看移动的磁盘,它会显示为:

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

奇数大小总是以偶数大小的相反方向移动,如果为pegs(0,1,2,repeat)或(2,1,0,repeat),则按顺序移动。

如果你看一下模式,要移动的环是 xor 移动次数和移动次数+1。