这个迭代的河内塔如何工作？C

Question

可能重复:
这是如何工作的？河内解决方案奇怪的塔

在浏览谷歌的过程中,我发现这个有趣的解决方案是Tower Of Hanoi,它甚至不使用堆栈作为数据结构.

任何人都能简单地解释一下,它到底在做什么？

这个解决方案真的可以接受

码

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int n, x;
   printf("How many disks?\n");
   scanf("%d", &n);
   printf("\n");
   for (x=1; x < (1 << n); x++)
      printf("move from tower %i to tower %i.\n",
         (x&x-1)%3, ((x|x-1)+1)%3);
return 0;
}

更新:3号硬编码在这里做什么？

Answer 1

在PSEUDOCODE中可能更容易看到:

GET NUMBER OF DISKS AS n
WHILE x BETWEEN 1 INCLUSIVE AND 1 LEFT-SHIFTED BY n BITS
    SUBTRACT 1 FROM n, DIVIDE BY 3 AND TAKE THE REMAINDER AS A
    OR x WITH x-1, ADD 1 TO THAT, DIVIDE BY 3 AND TAKE THE REMAINDER AS B
    PRINT "MOVE FROM TOWER " A " TO TOWER " B
    ADD 1 TO x

1个左移由n位基本上为2的幂,在4个磁盘的情况下为16.

如果手动完成此序列,则应该看到磁盘移动的进程.http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

Answer 2

它是Tower of Hanoi的二元解决方案之一,维基百科上有这个算法的详细解释 - 阅读"二元解决方案"一节.