这个迭代的河内塔是如何工作的?C [英] How does this iterative Tower of Hanoi work? C

问题描述

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

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

While surfing Google, i found this interesting solution to Tower Of Hanoi which doesn't even use stack as data structure.

谁能简要解释一下，它实际上在做什么?

Can anybody explain me in brief, what is it actually doing?

这种解决方案真的可以接受吗?

Are this solution really acceptable?

代码

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

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

更新:硬编码的数字 3 在这里做什么?

推荐答案

在 PSEUDOCODE 中可能更容易看到:

Might be easier to see in 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.

1 LEFT SHIFTED BY n BITS is basically 2 to the power of n, 16 in the case of 4 disks.

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

这篇关于这个迭代的河内塔是如何工作的?C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！