四柱漢諾塔非遞歸研究與實現

姜華林 李立新 陳強

摘 要： 對“經典三柱漢諾塔”的遞歸求解算法及其他非遞歸算法問題進行了詳細的分析和研究，給出了一種新的簡單且高效的非遞歸算法。在“經典三柱漢諾塔”的非遞歸算法研究基礎上對“四柱漢諾塔”問題的四柱漢諾塔Frame算法進行了深入的研究，實現了一種高效的四柱漢諾塔非遞歸算法，并用C#語言進行了驗證。通過該問題的C#實現，可使學習者清晰地觀測到解決四柱漢諾塔非遞歸算法的全過程。

關鍵詞： 三柱漢諾塔； 四柱漢諾塔； Frame算法； 非遞歸算法

中圖分類號：TP302 文獻標志碼：A 文章編號：1006-8228（2013）05-45-03

Research on non-recursive algorithm of 4-peg hanoi tower

Jiang Hualin1， Li Lixin2， Chen Qiang2

（1. Department of Computer Science， Zunyi Vocational and Technical College， Zunyi， Guizhou 563000， China；

2. School of computer and Information Science， Southwest University）

Abstract： Detailed analysis about hanoi issue is carried out and one easy and efficient realization of non-recursive algorithm in program C# is given.Frame algorithm of 4-peg hanoi tower is analyzed and researched based on the classic 3-peg hanoi tower program and a non-recursive and efficient algorithm of 4-peg hanoi tower is proposed. Realization of 4-peg hanoi tower algorithm though program C# can make learners observe clearly the whole process which solves this issue.

Key words： 3-peg hanoi tower； 4-peg hanoi tower； frame algorithm； non-recursive algorithm

0 引言

漢諾塔問題是一個古老的數學問題。經典漢諾塔問題是三柱的，即：有三個柱（分別為A、B和C）。開始時，有n個碟子按從下到上、從大到小的次序疊置在A柱上。現要將A柱上的所有碟子，借助B柱，全部移動到C柱上，且仍按照原來的次序疊置。三柱漢諾塔經典算法為：首先用三柱漢諾塔經典算法把A柱上面的n-1個碟子通過C柱移到B柱上，然后把A柱剩下的一個碟子移到C柱上，最后用三柱漢諾塔經典算法把B柱上所有的碟子通過A柱移到C柱上[1]。

設完成n個碟子的三柱漢諾塔需要移動的步數為T（n），則T（n）=2n-1。

四柱漢諾塔有4個柱（A、B、C和D），目標是把A柱上的n個碟子通過B柱和C柱移到D柱上。盡管四柱漢諾塔只比三柱漢諾塔多一個柱，但是解決它的難度遠大于三柱漢諾塔[2]。

本文首先研究了一種三柱漢諾塔非遞歸算法，然后在此基礎上根據四柱漢諾塔Frame算法[2]實現四柱漢諾塔非遞歸算法。……