河內迭代塔如何工作？ ç

可能重複：
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

河內迭代塔如何工作？ ç

回答

相關問題