这是如何运作的？河内解决方案的怪异塔 [英] How does this work? Weird Towers of Hanoi Solution

问题描述

我失去了互联网上的时候，我发现这个的不寻常的，迭代解决了河内塔：

I was lost on the internet when I discovered this unusual, iterative solution to the towers of Hanoi:

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

<一个href="http://stackoverflow.com/questions/480093/should-i-use-recursion-or-memoization-for-an-algorithm">This帖子也有类似的德尔福code的答案之一。

This post also has similar Delphi code in one of the answers.

不过，对于我的生活，我似乎无法找到一个很好的理由来解释为什么这个工程。

However, for the life of me, I can't seem to find a good explanation for why this works.

谁能帮我明白了吗？

推荐答案

递归地解决河内塔的工作原理，这样，如果你想从挂钩A到C移动n个磁盘，您首先将N-1从A到B ，那么您将底部的一个C，然后再从B将N-1磁盘C.从本质上说，

the recursive solution to towers of Hanoi works so that if you want to move N disks from peg A to C, you first move N-1 from A to B, then you move the bottom one to C, and then you move again N-1 disks from B to C. In essence,

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

显然河内（_，_，_，1）需要一个移动和河内（_，_，_，K）需要尽可能多的移动2 *河内（_，_，_，K-1）+ 1因此该溶液的长度长的序列1，3，7，15，...这是相同的序列（1＆其中;＆所述; k）的 - 1，这解释了贴在算法中循环的长度。

Clearly hanoi( _ , _ , _ , 1) takes one move, and hanoi ( _ , _ , _ , k) takes as many moves as 2 * hanoi( _ , _ , _ , k-1) + 1. So the solution length grows in the sequence 1, 3, 7, 15, ... This is the same sequence as (1 << k) - 1, which explains the length of the loop in the algorithm you posted.

如果你看一下自己的解决方案，对于N = 1你

If you look at the solutions themselves, for N = 1 you get

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你

And for N = 3 you get

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

的溶液的递归性因为，从和到列跟随一个递归逻辑：如果采取中间条目上的列，上方的部分和下面是彼此的副本，但随着置换的数字。这是该算法本身不就挂号码执行任何算术的一个明显的结果，而是仅permutes它们。在这种情况下，N = 4的中间一行是在x = 4（标有三颗星以上）。

Because of the recursive nature of the solution, the FROM and TO columns follow a recursive logic: if you take the middle entry on the columns, the parts above and below are copies of each others, but with the numbers permuted. This is an obvious consequence of the algorithm itself which does not perform any arithmetics on the peg numbers but only permutes them. In the case N=4 the middle row is at x=4 (marked with three stars above).

现在的EX pression（X及（X-1））取消X的至少设置位，所以它映射例如：编号从1到7这样的：

Now the expression (X & (X-1)) unsets the least set bit of X, so it maps e.g. numbers form 1 to 7 like this:

   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）。这实现了复制的属性，添加中间一行的实现置换一部分。这位前pression（X |（X-1））+ 1套最低零位有那些其权利，并清除这些的，所以它有预期相似的特性：

The trick is that because the middle row is always at an exact power of two and thus has exactly one bit set, the part after the middle row equals the part before it when you add the middle row value (4 in this case) to the rows (i.e. 4=0+4, 6=2+6). This implements the "copy" property, the addition of the middle row implements the permutation part. The expression (X | (X-1)) + 1 sets the lowest zero bit which has ones to its right, and clears these ones, so it has similar properties as expected:

   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

至于为什么这些序列实际上产生正确的盯住数字，让我们考虑从列。递归溶液开始河内（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，和行5，6，7为1,1,0，同一模式的所有置换版本）。

As to why these sequences actually produce the correct peg numbers, let's consider the FROM column. The recursive solution starts with hanoi(0, 2, 1, N), so at the middle row (2 ** (N-1)) you must have movedisk(0, 2). Now by the recursion rule, at (2 ** (N-2)) you need to have movedisk(0, 1) and at (2 ** (N-1)) + 2 ** (N-2) movedisk (1, 2). This creates the "0,0,1" pattern for the from pegs which is visible with different permutations in the table above (check rows 2, 4 and 6 for 0,0,1 and rows 1, 2, 3 for 0,0,2, and rows 5, 6, 7 for 1,1,0, all permuted versions of the same pattern).

现在则一切都有他们创建自己身边的两个，而是与偏移证书副本这个属性的功能，作者已经选择那些生产模3的正确排列。这不是一个公开的困难的任务，因为只有6个可能的三个整数0..2并且在算法中的逻辑顺序排列的进展排列。 （X |（X-1））+ 1不一定是深与河内问题联或它并不需要是;它足够它具有复制性，它发生产​​生正确排列在正确的顺序

Now then of all the functions that have this property that they create copies of themselves around powers of two but with offsets, the authors have selected those that produce modulo 3 the correct permutations. This isn't an overtly difficult task because there are only 6 possible permutations of the three integers 0..2 and the permutations progress in a logical order in the algorithm. (X|(X-1))+1 is not necessarily deeply linked with the Hanoi problem or it doesn't need to be; it's enough that it has the copying property and that it happens to produce the correct permutations in the correct order.

这篇关于这是如何运作的？河内解决方案的怪异塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！