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

Question

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

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

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 LEFT SHIFTED BY n BITS 基本上是 2 的 n 次方，在 4 个磁盘的情况下为 16。

如果您手动浏览此序列，您应该会看到磁盘移动的进程。http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

Answer 2

它是河内塔的二元解决方案之一，在维基百科上有对该算法的详细解释 - 阅读“二元解决方案”段落。