c - 这个迭代的汉诺塔是如何工作的？ C

这个问题已经在这里有了答案:




11年前关闭。






在浏览Google时，我发现了针对塔河内的一个有趣的解决方案，它甚至不使用堆栈作为数据结构。

有人可以简单地解释一下我吗，它实际上在做什么？

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

代码

#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在这里做什么？

最佳答案

在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

n位偏移1个位基本上是n的2的幂，在4个磁盘的情况下为16。

If you walk through this sequence manually, you should see the progression of movement of the disks. http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif