河內塔遞歸

我已經閱讀了河內塔問題陳述和解決方案。該解決方案指出，如果必須將一組N個磁盤從A移動到B，請將C用作臨時磁盤，並將N-1個磁盤從A傳輸到C.然後將第N個磁盤從A傳輸到B，然後將N-1個磁盤從C到B.我知道這個問題已經減小了，因此是遞歸實現的競爭者。但是，我們一次不能傳輸超過1個磁盤。我們如何能夠首先轉移N-1個磁盤。河內塔遞歸

來源

2014-09-02 sad

見http://stackoverflow.com/q/25625964/489590瞭解更多詳情。 – 2014-09-02 14:36:35

以遞歸方式傳輸'N'個磁盤的方式傳輸'N-1'磁盤。當你下到一個磁盤時，轉移是微不足道的。 – Paulpro 2014-09-02 14:37:41

@Srinath Kattula：如果你用C++標記這個問題，請添加一些源代碼或刪除標記。 – duDE 2014-09-02 14:37:52

通過使用遞歸。另請參閱Tower of Hanoi: Recursive Algorithm和維基百科頁面

遞歸如下：您知道如何移動1張光盤，假設您知道如何移動n-1張光盤，您如何移動n張光盤？

的「假設」的部分是你的遞歸：你通過移動9，然後1，那麼9
要移動的9盤10個移動盤，你的一舉一動8，然後1，然後8
要移動8盤...
...
要移動2盤，你的一舉一動1，然後1，然後按1

來源

2014-09-02 14:41:50 valjeanval42

這就是遞歸步驟。使用相同的算法從A轉移N-1磁盤，將N磁盤從A轉移到B.如果N是1，則只需移動單個磁盤即可。（或者，如果N等於零，則不做任何事情）。

僞代碼：

move(N, A, B): 
    if (N > 0) 
     move(N-1, A, C) 
     move_single_disk(A, B) 
     move(N-1, C, B)

來源

2014-09-02 14:41:55

回答

相關問題