可能的重复：
这是如何运作的？奇怪的河内塔解决方案
在浏览 Google 时，我发现了 Hanoi 塔的这个有趣的解决方案，它甚至不使用堆栈作为数据结构。
谁能简单地解释一下我，它实际上在做什么？
这个解决方案真的可以接受吗？
Code
#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 在这里做什么？
在伪代码中可能更容易看到：
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 的 n 次方，在 4 个磁盘的情况下为 16。
如果您手动执行此序列，您应该会看到磁盘移动的进度。 http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
