漢諾塔遞歸算法

我有理解漢諾塔這種遞推算法的一個問題：漢諾塔遞歸算法

public class MainClass { 
    public static void main(String[] args) { 
    int nDisks = 3; 
    doTowers(nDisks, 'A', 'B', 'C'); 
    } 

    public static void doTowers(int topN, char from, char inter, char to) { 
    if (topN == 1){ 
     System.out.println("Disk 1 from " + from + " to " + to); 
    }else { 
     doTowers(topN - 1, from, to, inter); 
     System.out.println("Disk " + topN + " from " + from + " to " + to); 
     doTowers(topN - 1, inter, from, to); 
    } 
    } 
}

輸出是：

Disk 1 from A to C 
Disk 2 from A to B 
Disk 1 from C to B 
Disk 3 from A to C 
Disk 1 from B to A 
Disk 2 from B to C 
Disk 1 from A to C

我不明白怎麼做，我們得到：

Disk 1 from C to B 
Disk 3 from A to C 
Disk 1 from B to A

有人能解釋一下嗎？

謝謝。

來源

2012-09-18 user564927

這裏的關鍵概念是理解遞歸調用改變參數... – gtgaxiola

是的，但我明白如何磁盤1從A到C磁盤2從A到B來了，但不知何故我無法理解從哪裏磁盤1從C到B來了。你能解釋我的流程嗎？我真的很感激！ – user564927

將doTowers（nDisks，'A'，'B'，'C'）;'改爲'doTowers（nDisks，'Left'，'Right'，'Middle'）;'看看是否有助於可視化它。 – Shmiddty

將N個磁盤塔從柱A移動到C是通過將N-1（所有磁盤，但最後一個）塔從A移動到B，然後將第N個磁盤從A移動到C，最後移動塔先前已經移到B，從B移到C.只要有一個以上磁盤的塔被移動，在任何時候都適用這種情況。對於1個磁盤塔，只需移動它的唯一磁盤。

來源

2012-12-07 22:41:08 Legna

如果我沒弄錯，你可以移動1個磁盤一個釘每轉正確？因此，您將第一個磁盤從a移動到b，然後從b移動到c。這是兩招。然後，我們現在可以將磁盤2從a移動到b。現在我們可以將磁盤1從c移回到b。現在磁盤3在A上，磁盤2和1在A上。現在我們將磁盤1從a移動到b然後移動到c。不，我們需要以正確的順序獲取磁盤3上的磁盤1和2。所以我們通過將磁盤1從B移動到A來清除磁盤1.這允許我們將磁盤2從B移到C.現在我們完成將磁盤1從a移動到b然後移動到c，然後我們完成了。

這是否回答你的問題？

來源

2012-09-18 19:39:23 ajon

我理解整個工作。 ...但是當我試圖遞歸地將其分解時，我得到的所有內容是磁盤1從A到C磁盤2從A到B，磁盤2從B到C磁盤1從A到C.我以某種方式無法理解遞歸函數如何將磁盤1從C到B磁盤3從A到C磁盤1從B到A :( – user564927

漢諾塔遞歸算法

回答

相關問題