姜華林 李立新 陳強(qiáng)

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

關(guān)鍵詞： 三柱漢諾塔； 四柱漢諾塔； Frame算法； 非遞歸算法

中圖分類號(hào)：TP302 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

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

1 三柱漢諾塔非遞歸算法

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

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

性質(zhì)3 三柱漢諾塔碟子最少移動(dòng)步驟的移動(dòng)序列為碟子序號(hào)的一個(gè)對(duì)稱數(shù)列。如3個(gè)碟子時(shí)，其移動(dòng)序列為：1213121。

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

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

⑵ n為偶數(shù)時(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，可得如下非遞歸算法：

⑴ 初始化碟子序號(hào)列表中每個(gè)序號(hào)的來源柱及所在柱信息；

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

⑶ 移動(dòng)序列列表當(dāng)前序號(hào)前的所有對(duì)應(yīng)序號(hào)，獲取新的所在柱及目標(biāo)柱后存入移動(dòng)序列列表，同時(shí)更新碟子序號(hào)列表對(duì)應(yīng)序號(hào)來源柱及所在柱信息；

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

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

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

private string inQuence（int qnum）

{ int i， j；

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

int index； //qList的序號(hào)

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

if （qnum%2==0）

{ inco=1； //移動(dòng)序號(hào)為奇數(shù)則增1

ince=-1； //移動(dòng)序號(hào)為偶數(shù)則減1

}

else

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

ince=1； //移動(dòng)數(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前面的所有項(xiàng)

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 四柱漢諾塔算法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑴ 目標(biāo)字符串進(jìn)隊(duì)，同時(shí)置可分解標(biāo)識(shí)為1；

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

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

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

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

① 對(duì)應(yīng)四柱移動(dòng)方案更新目標(biāo)字符串后進(jìn)隊(duì)；

② 對(duì)應(yīng)三柱移動(dòng)方案更新目標(biāo)字符串后進(jìn)隊(duì)；

③ 對(duì)應(yīng)四柱移動(dòng)方案更新目標(biāo)字符串后進(jìn)隊(duì)；

執(zhí)行⑵；

⑹ 三柱移動(dòng)方案又重新進(jìn)隊(duì)，執(zhí)行⑵；

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

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

⑼ 算法結(jié)束。

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

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

{ …

//將minmp個(gè)盤子移動(dòng)方式入隊(duì)

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個(gè)盤子移動(dòng)方式入隊(duì)

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

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

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

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

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

qu.Enqueue（strtmp）；

//將minmp個(gè)盤子移動(dòng)方式入隊(duì)

strtmp=minmp.ToString（）；

strtmp+=maxnp.ToString（）；

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

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

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