「漢諾塔」遞歸不是那麼簡單，因爲它似乎

我被要求執行遞歸「漢諾塔」，和我心中的工作這樣的邏輯：「漢諾塔」遞歸不是那麼簡單，因爲它似乎

移動從開始1個磁盤到緩衝
從開始從緩衝器移動到其餘目標
移動1個磁盤上目標

每個測試除了通過「Towers_of_hanoi（3，開始，目標）」

原來的正確實施是：

移動N - 1個磁盤從開始到緩衝區
移動1從起點到目標
移動N - 從緩衝區1個磁盤到目標

我已經學會了將遞歸作爲解決問題的一種方法，在我看來，兩種實現都是這樣做的。我的想法與將其分解的正確方法有什麼根本的缺陷？

2014-10-26 user96454

河內塔的事情是，你只能有3個堆棧，你不能把更大的磁盤放在較小的磁盤上，所以你需要確保你使用的棧作爲'緩衝區'在進行遞歸調用之前，不包含任何較小的磁盤。在你的情況下，你將最小的磁盤移動到緩衝區，然後嘗試遞歸移動堆棧的其餘部分，但是這會失敗，因爲緩衝區不可用。

來源

2014-10-26 22:08:33

克里斯，我確實看到了這個缺陷，但我覺得奇怪的是，教育工作者並不認爲應該提及這些技巧。我所看到的每個視頻或演講都涉及到這個問題，這讓我們對該算法有了「刷新」的高層次解釋。那麼，如果這種思維方式是遞歸所必需的，我的算法應該可以正常工作。（這是一個咆哮:) – user96454 2014-10-26 22:11:56

你的算法確實有效 - 只要它可以將大磁盤放在小磁盤上。如果你通過它，它將整個堆棧移動到緩衝區（倒置的塔），然後移動到目標。 – 2014-10-26 22:14:15

@ user96454作爲一個真正教這個並使用Hanoi Towers例子的人，我總是要指出該算法的工作原理是當移動較小的磁盤時，可以忽略較大的磁盤。我很抱歉，任何教這個的人都沒有說清楚這一點。 – templatetypedef 2014-10-26 22:15:07

「漢諾塔」遞歸不是那麼簡單，因爲它似乎

回答

相關問題