河内迭代塔如何工作？ ç

可能重复：
How does this work? Weird Towers of Hanoi Solution 河内迭代塔如何工作？ ç

虽然谷歌冲浪，我发现这个有趣的解决方案，以汉诺塔它甚至没有用到堆栈数据结构。

有人可以简单地解释我，它究竟在做什么？

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

代码

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

来源

2010-05-20 TCM

它使用标准的3根棒。 – 2010-05-20 02:42:25

它报告正确的移动顺序吗？如果是这样，它就会起作用，而且没有理由不接受它。但是，在提供它作为家庭作业的解决方案之前，您需要了解它，否则，如果您被要求解释它，您将会遇到麻烦，因为它可能与正常情况非常不同。 – 2010-05-20 02:44:28

这不是我的作业。我只是意外地发现了这个算法，并且想知道它是如何工作的。 – TCM 2010-05-20 02:48:42

可能更容易在伪代码看：

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，16的中的4个磁盘的情况下的功率。

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

来源

2010-05-20 02:44:59

感谢哈维，这个伪代码的确很容易理解:)。很好的答案！ – TCM 2010-05-20 02:51:09

呃，“BETWEEN 1 AND n”与“for（x = 1; x <（1 << n）; x ++）不一样” – 2010-05-20 02:54:34

@David：谢谢，修正。 – 2010-05-20 02:57:10

它是河内塔的二进制解决方案之一，在维基百科上有这个算法的详细解释 - 阅读the "Binary solution" paragraph。

来源

2010-05-20 02:42:36 ZelluX

河内迭代塔如何工作？ ç

回答

相关问题