四柱漢諾塔非遞歸研究與實現(xiàn)

姜華林 李立新 陳強

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

關(guān)鍵詞： 三柱漢諾塔； 四柱漢諾塔； 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 引言

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

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

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

本文首先研究了一種三柱漢諾塔非遞歸算法，然后在此基礎(chǔ)上根據(jù)四柱漢諾塔Frame算法[2]實現(xiàn)四柱漢諾塔非遞歸算法。

1 三柱漢諾塔非遞歸算法

性質(zhì)1 三柱漢諾塔上的任意碟子的移動是循環(huán)式的，即兩種方式：ABCA式循環(huán)和ACBA式循環(huán)。

性質(zhì)2 三柱漢諾塔碟子總數(shù)為奇數(shù)時，碟子序號為奇數(shù)的移動方式為：A->C、C->B、B->A，碟子序號為偶數(shù)的移動方式為：A->B、B->C、C->A；碟子總數(shù)為偶數(shù)時，碟子序號為奇數(shù)的移動方式為：A->B、B->C、C->A，碟子序號為偶數(shù)的移動方式為：A->C、C->B、B->A。

性質(zhì)3 三柱漢諾塔碟子最少移動步驟的移動序列為碟子序號的一個對稱數(shù)列。如3個碟子時，其移動序列為：1213121。

性質(zhì)4 碟子數(shù)為n的三柱漢諾塔最少移動步驟的完整移動序列為：

⑴ n為奇數(shù)時，1A->C 2A->B 1C->B 3A->C 1B->A 2B->C 1A->C 4A->B 1C->B 2C->A …；

⑵ n為偶數(shù)時，1A->B 2A->C 1B->C 3A->B 1C->A 2C->B 1A->B 4 A->C 1B->C 2B->A …。

根據(jù)性質(zhì)1～4，可得如下非遞歸算法：

⑴ 初始化碟子序號列表中每個序號的來源柱及所在柱信息；

⑵ 依次掃描第i個碟子序號，將第i個碟子序號的所在柱及目標柱（根據(jù)碟子序號奇偶性及循環(huán)移動方式可得）存入移動序列列表，同時更新碟子序號列表對應(yīng)序號來源柱及所在柱信息；

⑶ 移動序列列表當前序號前的所有對應(yīng)序號，獲取新的所在柱及目標柱后存入移動序列列表，同時更新碟子序號列表對應(yīng)序號來源柱及所在柱信息；

⑷ 若所有碟子序號已經(jīng)掃描完成，執(zhí)行⑸，否則i=i+1，執(zhí)行⑵；

⑸ 結(jié)束，返回移動序列列表。

算法的關(guān)鍵源碼如下（C#）：

private string inQuence（int qnum）

{ int i， j；

int inco， ince； //增量為奇或偶

int index； //qList的序號

int inum； //qList已有項數(shù)

if （qnum%2==0）

{ inco=1； //移動序號為奇數(shù)則增1

ince=-1； //移動序號為偶數(shù)則減1

}

else

{ inco=-1； //移動數(shù)為奇數(shù)則減1

ince=1； //移動數(shù)為偶數(shù)則增1

}

qList.Clear（）；

for （i=0； i

{ nfList[i].FromLoc=nfList[i].NowLoc；

if （i%2==0）

nfList[i].NowLoc+=inco；

else

nfList[i].NowLoc+=ince；

…

numFromList nfl1=new numFromList（）；

nfl1.Num=nfList[i].Num；

nfl1.NowLoc=nfList[i].NowLoc；

nfl1.FromLoc=nfList[i].FromLoc；

qList.Add（nfl1）；

inum=qList.Count；

buchou++；

//添加inum-1前面的所有項

for （j=0； j

{ numFromList nfl2=new numFromList（）；

nfl2.Num=qList[j].Num；

nfl2.NowLoc=qList[j].NowLoc；

nfl2.FromLoc=qList[j].FromLoc；

qList.Add（nfl2）；

nfList[nfl2.Num-1].FromLoc=nfList[nfl2.Num-1].NowLoc；

index=qList.Count-1；

if （j%2==0）

nfList[nfl2.Num-1].NowLoc+=inco；

else

nfList[nfl2.Num-1].NowLoc+=ince；

qList[index].FromLoc=nfList[nfl2.Num-1].FromLoc；

…

qList[index].NowLoc=nfList[nfl2.Num-1].NowLoc；

buchou++；

}

}

…

return strM；

}

2 四柱漢諾塔算法分析

以下是對四柱漢諾塔的Frame算法[2]描述。

對于碟數(shù)為n的四柱漢諾塔，假定碟數(shù)i小于n 時的算法已經(jīng)確定，i個碟子的四柱漢諾塔需要移動的步數(shù)記為F（i）。可把A柱上的碟子分成上、下兩部分，下部分共有r個碟子，上部分n-r個碟子，1≤r≤n。具體操作步驟如下：

⑴ 用四柱漢諾塔Frame算法將A柱上部分的n-r個碟子經(jīng)過C柱和D柱移到B柱上，需要F（n-r）步；

⑵ 用三柱漢諾塔經(jīng)典算法將A柱上剩余的r個碟子經(jīng)過C柱移到D柱上，需要T（r）=2r-1步；

⑶ 用四柱漢諾塔Frame算法將B柱上的n-r個碟子經(jīng)過A柱和C柱移到D柱上，需要F（n-r）步。

據(jù)此，計算出總步數(shù)為f（n，r），隨后對所有的r（1≤r≤n）逐一進行嘗試。選擇一個r使得f（n，r）取最小值，并定義此時的r為R（n）。于是移完n個碟子的四柱漢諾塔需要的最少步數(shù)為[2]：

F（n）=minf（n，r）=min[2F（n-r）+2T（r）]=min[2F（n-r）+2r-1] ⑴

由式⑴可知，要用最少步數(shù)移完n個碟子的四柱漢諾塔關(guān)鍵在于r的取值，經(jīng)過反復(fù)研究，得到如下性質(zhì)。

性質(zhì)1 對于n（n≥3），要使f（n，r）取最小值，r必然大于等于且小于等于n-1，即r的取值范圍是{r|≤r≤n-1}。

取r初值為并代入上面（1）式的 f（n，r），然后對r逐次加1進行比較。必然會得到一個r使得f（n，r）取最小值。

性質(zhì)2 當r確定時，其最優(yōu)解minf（n，r）具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

現(xiàn)在來簡單證明該最優(yōu)解具有最優(yōu)子結(jié)構(gòu)性質(zhì)，當r確定時，F(xiàn)（n-r）是不變的，T（r）也是不變的。而對于一個任意i（≤i≤r-1），F(xiàn)（n-r）為最優(yōu)解時，其子問題F（r-i）和T（i）也必為最優(yōu)解。如果F（r-i）和T（i）不是最優(yōu)解，那么存在F'（r-i）+T'（i）

3 四柱漢諾塔非遞歸算法設(shè)計

以上Frame算法很容易用遞歸實現(xiàn)。本文根據(jù)性質(zhì)1和性質(zhì)2重點研究其非遞歸算法，四柱漢諾塔的非遞歸算法記為FourPegsHanoi算法，其算法核心思想是把要移動的碟子總數(shù)（用二位十進制數(shù)表示）、碟子最大序號（用二位十進制數(shù)表示）和四柱標識作為一個目標字符串并進隊列，然后出隊列并反復(fù)動態(tài)分解為最優(yōu)四柱移動子方案和最優(yōu)三柱移動方案，直到n-r<3為止，具體操作步驟如下：

⑴ 目標字符串進隊，同時置可分解標識為1；

⑵ 如果可分解標識為1，隊頭出隊，分解目標字符串，如果碟子總數(shù)小于3且四柱標識中的第一個標識不為“0”，則置可分解標識為0，執(zhí)行⑷，否則執(zhí)行⑶；

⑶ 如果四柱標識中的第一個標識不為“0”，則執(zhí)行⑸，否則執(zhí)行⑹；

⑷ 如果隊列不為空，隊頭出隊，分解目標字符串，如果四柱標識中的第一個標識不為“0”，則執(zhí)行⑺，否則執(zhí)行⑻，如果隊列為空則執(zhí)行⑼；

⑸ 把目標字符串動態(tài)分解為規(guī)模更小的四柱移動方案和三柱移動方案：

① 對應(yīng)四柱移動方案更新目標字符串后進隊；

② 對應(yīng)三柱移動方案更新目標字符串后進隊；

③ 對應(yīng)四柱移動方案更新目標字符串后進隊；

執(zhí)行⑵；

⑹ 三柱移動方案又重新進隊，執(zhí)行⑵；

⑺ 調(diào)用不可再分解的四柱移動方案實施移動，執(zhí)行⑷；

⑻ 調(diào)用三柱移動方案實施移動，執(zhí)行⑷；

⑼ 算法結(jié)束。

算法的關(guān)鍵源碼如下（C#）：

void nstest（int pnum， char ca， char cb， char cc， char cd）

{ …

//將minmp個盤子移動方式入隊

strtmp=minmp.ToString（）；

strtmp+=maxnp.ToString（）；

strtmp+=cfour[0].ToString（）；

strtmp+=cfour[2].ToString（）；

strtmp+=cfour[3].ToString（）；

strtmp+=cfour[1].ToString（）；

qu.Enqueue（strtmp）；

//將minmn個盤子移動方式入隊

strtmp=（minmn+1）.ToString（）；

strtmp+=maxn.ToString（）+"0"；

strtmp+=cthree[0].ToString（）；

strtmp+=cthree[1].ToString（）；

strtmp+=cthree[2].ToString（）；

qu.Enqueue（strtmp）；

//將minmp個盤子移動方式入隊

strtmp=minmp.ToString（）；

strtmp+=maxnp.ToString（）；

strtmp+=cfour[1].ToString（）；

strtmp+=cfour[0].ToString（）；

strtmp+=cfour[2].ToString（）；