四柱汉诺塔非递归研究与实现

姜华林 李立新 陈强

摘 要： 对“经典三柱汉诺塔”的递归求解算法及其他非递归算法问题进行了详细的分析和研究，给出了一种新的简单且高效的非递归算法。在“经典三柱汉诺塔”的非递归算法研究基础上对“四柱汉诺塔”问题的四柱汉诺塔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]实现四柱汉诺塔非递归算法。

1 三柱汉诺塔非递归算法

性质1 三柱汉诺塔上的任意碟子的移动是循环式的，即两种方式：ABCA式循环和ACBA式循环。

性质2 三柱汉诺塔碟子总数为奇数时，碟子序号为奇数的移动方式为：A->C、C->B、B->A，碟子序号为偶数的移动方式为：A->B、B->C、C->A；碟子总数为偶数时，碟子序号为奇数的移动方式为：A->B、B->C、C->A，碟子序号为偶数的移动方式为：A->C、C->B、B->A。

性质3 三柱汉诺塔碟子最少移动步骤的移动序列为碟子序号的一个对称数列。如3个碟子时，其移动序列为：1213121。

性质4 碟子数为n的三柱汉诺塔最少移动步骤的完整移动序列为：

⑴ n为奇数时，1A->C 2A->B 1C->B 3A->C 1B->A 2B->C 1A->C 4A->B 1C->B 2C->A …；

⑵ n为偶数时，1A->B 2A->C 1B->C 3A->B 1C->A 2C->B 1A->B 4 A->C 1B->C 2B->A …。

根据性质1～4，可得如下非递归算法：

⑴ 初始化碟子序号列表中每个序号的来源柱及所在柱信息；

⑵ 依次扫描第i个碟子序号，将第i个碟子序号的所在柱及目标柱（根据碟子序号奇偶性及循环移动方式可得）存入移动序列列表，同时更新碟子序号列表对应序号来源柱及所在柱信息；

⑶ 移动序列列表当前序号前的所有对应序号，获取新的所在柱及目标柱后存入移动序列列表，同时更新碟子序号列表对应序号来源柱及所在柱信息；

⑷ 若所有碟子序号已经扫描完成，执行⑸，否则i=i+1，执行⑵；

⑸ 结束，返回移动序列列表。

算法的关键源码如下（C#）：

private string inQuence（int qnum）

{ int i， j；

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

int index； //qList的序号

int inum； //qList已有项数

if （qnum%2==0）

{ inco=1； //移动序号为奇数则增1

ince=-1； //移动序号为偶数则减1

}

else

{ inco=-1； //移动数为奇数则减1

ince=1； //移动数为偶数则增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]描述。

对于碟数为n的四柱汉诺塔，假定碟数i小于n 时的算法已经确定，i个碟子的四柱汉诺塔需要移动的步数记为F（i）。可把A柱上的碟子分成上、下两部分，下部分共有r个碟子，上部分n-r个碟子，1≤r≤n。具体操作步骤如下：

⑴ 用四柱汉诺塔Frame算法将A柱上部分的n-r个碟子经过C柱和D柱移到B柱上，需要F（n-r）步；

⑵ 用三柱汉诺塔经典算法將A柱上剩余的r个碟子经过C柱移到D柱上，需要T（r）=2r-1步；

⑶ 用四柱汉诺塔Frame算法将B柱上的n-r个碟子经过A柱和C柱移到D柱上，需要F（n-r）步。

据此，计算出总步数为f（n，r），随后对所有的r（1≤r≤n）逐一进行尝试。选择一个r使得f（n，r）取最小值，并定义此时的r为R（n）。于是移完n个碟子的四柱汉诺塔需要的最少步数为[2]：

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

由式⑴可知，要用最少步数移完n个碟子的四柱汉诺塔关键在于r的取值，经过反复研究，得到如下性质。

性质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）取最小值。

性质2 当r确定时，其最优解minf（n，r）具有最优子结构性质。

现在来简单证明该最优解具有最优子结构性质，当r确定时，F（n-r）是不变的，T（r）也是不变的。而对于一个任意i（≤i≤r-1），F（n-r）为最优解时，其子问题F（r-i）和T（i）也必为最优解。如果F（r-i）和T（i）不是最优解，那么存在F'（r-i）+T'（i）

3 四柱汉诺塔非递归算法设计

以上Frame算法很容易用递归实现。本文根据性质1和性质2重点研究其非递归算法，四柱汉诺塔的非递归算法记为FourPegsHanoi算法，其算法核心思想是把要移动的碟子总数（用二位十进制数表示）、碟子最大序号（用二位十进制数表示）和四柱标识作为一个目标字符串并进队列，然后出队列并反复动态分解为最优四柱移动子方案和最优三柱移动方案，直到n-r<3为止，具体操作步骤如下：

⑴ 目標字符串进队，同时置可分解标识为1；

⑵ 如果可分解标识为1，队头出队，分解目标字符串，如果碟子总数小于3且四柱标识中的第一个标识不为“0”，则置可分解标识为0，执行⑷，否则执行⑶；

⑶ 如果四柱标识中的第一个标识不为“0”，则执行⑸，否则执行⑹；

⑷ 如果队列不为空，队头出队，分解目标字符串，如果四柱标识中的第一个标识不为“0”，则执行⑺，否则执行⑻，如果队列为空则执行⑼；

⑸ 把目标字符串动态分解为规模更小的四柱移动方案和三柱移动方案：

① 对应四柱移动方案更新目标字符串后进队；

② 对应三柱移动方案更新目标字符串后进队；

③ 对应四柱移动方案更新目标字符串后进队；

执行⑵；

⑹ 三柱移动方案又重新进队，执行⑵；

⑺ 调用不可再分解的四柱移动方案实施移动，执行⑷；

⑻ 调用三柱移动方案实施移动，执行⑷；

⑼ 算法结束。

算法的关键源码如下（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（）；