探祕漢諾塔（5）——漢諾塔的非遞歸編程

主題：漢諾塔的非遞歸編程

前面的探究一直是在為漢諾塔的非遞歸編程做準備。網上漢諾塔的非遞歸編程較好的方法和常式有近十種，歸納後有三類：

第一類（基於棧）：這種方法很直觀，幾個柱子就是幾個棧，盤子在柱子上的移出和移入操作對就出棧和進棧，而且只能對棧頂的盤子進行操作。

第二類（基於先驗知識和規律）：通過對實驗數據的分析，第m步將k號盤子從n1號柱子移動n2號柱子，以及m步將k號盤子的移動方向等都是有規律的，甚至可用數學公式來歸納。從而可以部分或全部基於先驗知識來進行非遞歸編程。

第三類（基於數學理論）：這類方法是第二類的特例，但漢諾塔遊戲背後的數學理論會遠超出中學數學的範疇，如狀態機、線性公式、矩陣變換和分形等。網上關於此部分內容的數學理論介紹文章很多，但筆者沒有發現有超出中學要求的數學來實現漢諾塔遊戲的編程實例。不過這些數學知識還有很有意義的，有興趣的同學可以去了解下。

針對以上三類方法，給同學們強調二點：

一、漢諾塔遊戲讓機器做和讓人做是兩回事。同學們在剛接觸這個問題時，你都可能經過多遍嘗試後才找到方法；而且在整個過程中你可能會出現不按規律來搬移盤子，認識到問題後又調整回某一狀態。以上三類方法都可以調整為驗證某個同學的實驗數據是否正確或最優的問題，但簡單直觀的方法可能是第一類基於棧的方法，能更深入和全面分析的可能是第三類。

二、關於時間複雜度。有網友給提出，基於通項（表達數組的下標與值之間關係的公式）時間複雜度可以是O(1)。通項就是屬於第二類的方法。我們建議同學們基於第二類方法做非遞歸實現的更多嘗試，比如：奇數步總是1號盤，對奇數個盤子或偶數個盤子1號盤的移動方向是固定的；對於偶數步來說盤子總是要移到比自己的盤號大的柱子上。

結論：練習時建議用多種方案來進行探索，在比賽時需根據自己的臨場判斷選擇一種方便直觀、易驗證結果正確性的方法來解決。磨刀不費砍柴功，平時能廣開思路才能在比賽的有限時間內一擊成功！