這是如何工作的？

Question

我迷失在互聯網上河內解決方案的古怪的塔當我發現this不尋常的，迭代解決河內塔：

for (int x = 1; x < (1 << nDisks); x++) 
{ 
    FromPole = (x & x-1) % 3; 
    ToPole = ((x | x-1) + 1) % 3; 
    moveDisk(FromPole, ToPole); 
} 

This post的答案中的一個也有類似的Delphi代碼。

但是，對於我的生活，我似乎無法找到一個很好的解釋，爲什麼這個工程。

任何人都可以幫助我理解它嗎？

Answer 1

河內塔的遞歸解決方案可以工作，因此如果您想將N個磁盤從掛鉤A移動到C，您首先將N-1從A移動到B，然後將底部移動到C，然後您移動再次N-1從乙磁盤C.在本質上，

hanoi(from, to, spare, N): 
    hanoi(from, spare, to, N-1) 
    moveDisk(from, to) 
    hanoi(spare, to, from, N-1) 

顯然河內（_，_，_，1）需要一個移動和河內（_，_，_，k）的取儘可能多的作爲2 * hanoi（_，_，_，k-1）+ 1移動。因此，解的長度按照1,3,7,15的順序增長。這與（1 k） - 1，它解釋了您發佈的算法中循環的長度。

如果你看一下解決方案本身，對於N = 1你

FROM TO 
      ; hanoi(0, 2, 1, 1) 
    0 2 movedisk 

對於N = 2你

FROM TO 
      ; hanoi(0, 2, 1, 2) 
      ; hanoi(0, 1, 2, 1) 
    0 1 ; movedisk 
    0 2 ; movedisk 
      ; hanoi(1, 2, 0, 1) 
    1 2 ; movedisk 

而對於N = 3你

FROM TO 
      ; hanoi(0, 2, 1, 3) 
      ; hanoi(0, 1, 2, 2) 
      ; hanoi(0, 2, 1, 1) 
    0 2 ; movedisk 
    0 1 ; movedisk 
      ; hanoi(2, 1, 0, 1) 
    2 1 ; movedisk 
    0 2 ; movedisk *** 
      ; hanoi(1, 2, 0, 2) 
      ; hanoi(1, 0, 2, 1) 
    1 0 ; movedisk 
    1 2 ; movedisk 
      ; hanoi(0, 2, 1, 1) 
    0 2 ; movedisk 

由於解決方案的遞歸性質，FROM和TO列遵循遞歸邏輯：如果您採用中間條目在列上，上面和下面的部分是每個其他部分的副本，但排列的是數字。這是算法本身的一個顯而易見的結果，它不對掛鉤數字執行任何算術運算，而只是對它們進行置換。在N = 4的情況下，中間行在x = 4處（以上面三顆星標記）。現在表達式（X &（X-1））取消了X的最小設置位，所以它映射了例如數字形式1至7這樣的：

1 -> 0 
    2 -> 0 
    3 -> 2 
    4 -> 0 (***) 
    5 -> 4 % 3 = 1 
    6 -> 4 % 3 = 1 
    7 -> 6 % 3 = 0 

訣竅是，因爲中間行始終在兩個精確的功率，因此只能有一個位集，中間行之後的部分纔等於部分當您將中間行值（在這種情況下爲4）添加到行（即4 = 0 + 4,6 = 2 + 6）時。這實現了「複製」屬性，中間行的添加實現了排列部分。表達式（X |（X-1））+ 1所設定最低零位具有那些其右側，並清除這些的，所以它具有與預期類似的性質：

1 -> 2 
    2 -> 4 % 3 = 1 
    3 -> 4 % 3 = 1 
    4 -> 8 (***) % 3 = 2 
    5 -> 6 % 3 = 0 
    6 -> 8 % 3 = 2 
    7 -> 8 % 3 = 2 

至於爲什麼這些序列實際上會生成正確的掛鉤編號，讓我們考慮一下FROM列。遞歸解決方案以河內（0,2,1，N）開始，所以在中間行（2 **（N-1）），您必須有移動（0,2）。現在通過遞歸規則，在（2 **（N-2））你需要有移動（0,1）和在（2 **（N-1））+ 2 **（N-2）移動1,2）。這爲上面的表中不同排列的pegs創建了「0,0,1」模式（針對0,0,1檢查行2,4和6，針對0,0檢查行1,2,3） ，2和1,1,6行的5,6,7行，同一模式的所有置換版本）。

現在，所有具有這個屬性的函數，他們創造了他們自己的權力兩個權力，但與偏移量，作者選擇那些產生模3正確的排列。這不是一個過分困難的任務，因爲三個整數0..2只有6個可能的排列，並且排列在算法中按邏輯順序進行。 （X |（X-1））+ 1並不一定與河內問題有深層次的聯繫，也可能不需要;它具有複製屬性就足夠了，並且它恰好以正確的順序產生正確的排列。

Answer 2

這不是直接回答這個問題，但是發表評論太長了。

我一直都是通過分析下一步應該移動的磁盤的大小來做到這一點的。如果你看一下移動磁盤，它出來到：

1 disk : 1 
2 disks : 1 2 1 
3 disks : 1 2 1 3 1 2 1 
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 

奇大小總是甚至那些相反的方向移動，以便如果釘（0，1，2，重複）或（2，1 ，0，重複）。

如果在模式看一看，環移動的最高位設置的移動次數和+ 1

Answer 3

antti.huima的解決方案基本上是正確的移動次數的xor的，但我想要更嚴格的東西，這太大了，不適合發表評論。這裏所說：

首先說明：在中間步驟x = 2 ^{N-1，該算法的}， 「從」 PEG是0，並且 「到」 PEG是2 ^Ñ％3.本葉2 ^（N-1）％3爲「備用」掛鉤。 對於算法的最後一步也是如此，所以我們發現實際上作者的算法 是一個輕微的「作弊」：它們將磁盤從掛鉤0移動到掛鉤2而不是掛鉤，而不是一個固定的， 預先指定「to」掛鉤。這可以改變，沒有太多的工作。

原始河內算法是：

hanoi(from, to, spare, N): 
    hanoi(from, spare, to, N-1) 
    move(from, to) 
    hanoi(spare, to, from, N-1) 

在堵 「由」= 0， 「到」= 2 ^Ñ％3， 「備用」= 2 ^N-1％3，我們得到（抑制％3'S）：

hanoi(0, 2**N, 2**(N-1), N): 
(a) hanoi(0, 2**(N-1), 2**N, N-1) 
(b) move(0, 2**N) 
(c) hanoi(2**(N-1), 2**N, 0, N-1) 

基本這裏的觀察是： 在線（c）中，PEG是河內（0的完全釘，2 ^N-1，2 ^N，N-1）移位了2 ^N-1％3，即 它們正好是線（a）的掛鉤，這個數量加到它們。

我要求它遵循的是，當我們 運行線（c）中，「從」和「到」 PEG是行的相應釘（a）以2 ^N-1％3.本 移從hanoi(a+x, b+x, c+x, N)這個簡單的，更一般的引理可以看出，「from」和「to pegs完全從hanoi(a, b, c, N)中移出x。

現在考慮的功能
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

要證明給定的算法的工作，我們只需要表明：

• F（2 ^N-1）== 0和g（2 ^N-1）== 2 ^N
• for 0 < <我2 ^Ñ，我們已經F（2 ^Ñ - ⅰ）== F（2 ^Ñ + I）+ 2 ^Ñ％3，和g（2 ^Ñ - ⅰ）==克（2 ^ñ + I）+ 2 ^ñ％3.

兩者都是容易顯現。