本站原创
摘 要：对汉诺塔问题的算法进行了具体分析，提出了四种不同的经典算法，并通过对此问题给出不同的算法，以期激发出学习者对经典汉诺塔问题新算法的探究热情。
关键词：汉诺塔；问题分析；算法设计；实现程序
2095-1302（2013）07-0048-02
0 引 言
大约在19世纪末，在欧州的商店中出售了一种智力玩具，该玩具在一块铜板上有3根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔，其目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
图1 圆盘搬动示意图
由于一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是18 446 744 073 709 55 615。
这是一个天文数字，若1 μs可计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔问题，但很难用计算机解决64层的汉诺塔问题。
针对具体问题，我们必须找出移动盘子的正确算法。首先考虑x杆下面的盘子而非杆上最上面的盘子，于是任务变成：
（1）将上面的63个盘子移到y杆上；
（2）将x杆上剩下的盘子移到z杆上；
（3）将y杆上的全部盘子移到z杆上。
将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子……的工作。为了更清楚地描述算法，可以定义一个函数movedisc（n，a，b，c）。该函数的功能是：将N个盘子从x杆上借助z杆移动到y杆上。这样，移动N个盘子的工作就可以按照以下过程进行：
（1） movedisc（n-1，x，y，z）；
（2） 将一个盘子从x移到y上；
（3） movedisc（n-1，z，y，x）；
（4） 重复以上过程，直到将全部的盘子移动到位时为止。
（1） 基于C语言的汉诺塔的算法实现程序如下：
void hanoi（int n，char x，char y，char z）
{
if（n==1）
move（x，1，z）；
else{
hanoi（n-1，x，z，y）；
move（x，n，z）；
hanoi（n-1，y，x，z）；
}
}
（2） 基于C++的汉诺塔的算法实现程序如下：
void Move（int i，char x，char y）
{
fout<<" 把" <}
void Hannoi（int n，char x，char y，char z）
{
if（n==1）
Move（1，x，z），
else
{
Hannoi（n-1，x，z，y）；
Move（n，x，z）；
Hannoi（n-1，y，x，z）；
}
}
int main（）
{
fout<<"下面是7层汉诺塔的解法：" <Hannoi（7，'x'，'y'，'z'）；
fout.close（）；
cout<<" 输出完毕！" <return 0；
}
（3） 基于Ja的汉诺塔的算法实现程序如下：
public class HanoiTower {
static int nDisks = 3；
public static void main（String[] args） {
hanoiTower（nDisks， 'x'， 'y'， 'z'）；
}
public static void hanoiTower（int topN， char src， char inter， char dest） {
if （topN == 1）
System.out.println（"Disk 1 from " + src + " to " + dest）；
else {
// src to inter
hanoiTower（topN - 1， src， dest， inter）；
// move bottom
System.out.println（"Disk " + topN + " from " + src + " to " + dest）；
//inter to dest
hanoiTower（topN - 1， inter， src， dest）；
}
}
}
图2 基于组合数学思想的分析模型
检测设a1=1，a2=3，对于任何n≥3，那么：可以作如下设计：
第一步，将套在柱x的上部的n-1个盘按要求移到柱y上，共搬动了an-1次；
第二步，将柱x上的最大一个盘移到柱z上，只要搬动1次；
第三步，再从柱y将n-1个盘按要求移到柱z上，也要用an-1次。
则由加法法则，{an}满足：
参 考 文 献
南基洙.组合数学[M].北京：高等教育出版社，2008.
（美）RICHARD Johnsonbaugh.大学算法教程[M].北京：清华大学出版社，2007.
[3] 严蔚敏，陈文博.数据结构及应用算法教程[M]..北京： 清华大学出版社，2011.
[4] 王春森.程序员教程[M].修订版.北京：清华大学出版社，2001.
[5] 刘军，张志峰.汉诺塔总是算法分析及C语言实现[J].计算机教学与教育信息化，2008，2（17）：1496-1498.
关键词：汉诺塔；问题分析；算法设计；实现程序
2095-1302（2013）07-0048-02
0 引 言
大约在19世纪末，在欧州的商店中出售了一种智力玩具，该玩具在一块铜板上有3根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔，其目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
1 问题分析与算法设计
汉诺塔（Hanoi）问题是一个著名的问题。64个圆盘按从小到大的顺序依次套在柱x上，如图1所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不许大盘放在小盘上，且只有x、y、z三根柱子可供使用。图1 圆盘搬动示意图
由于一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是18 446 744 073 709 55 615。
这是一个天文数字，若1 μs可计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔问题，但很难用计算机解决64层的汉诺塔问题。
针对具体问题，我们必须找出移动盘子的正确算法。首先考虑x杆下面的盘子而非杆上最上面的盘子，于是任务变成：
（1）将上面的63个盘子移到y杆上；
（2）将x杆上剩下的盘子移到z杆上；
（3）将y杆上的全部盘子移到z杆上。
将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子……的工作。为了更清楚地描述算法，可以定义一个函数movedisc（n，a，b，c）。该函数的功能是：将N个盘子从x杆上借助z杆移动到y杆上。这样，移动N个盘子的工作就可以按照以下过程进行：
（1） movedisc（n-1，x，y，z）；
（2） 将一个盘子从x移到y上；
（3） movedisc（n-1，z，y，x）；
（4） 重复以上过程，直到将全部的盘子移动到位时为止。
2 汉诺塔问题算法
下面是基于三种语言的汉诺塔算法实现程序。（1） 基于C语言的汉诺塔的算法实现程序如下：
void hanoi（int n，char x，char y，char z）
{
if（n==1）
move（x，1，z）；
else{
hanoi（n-1，x，z，y）；
move（x，n，z）；
hanoi（n-1，y，x，z）；
}
}
（2） 基于C++的汉诺塔的算法实现程序如下：
void Move（int i，char x，char y）
{
fout<<" 把" <
void Hannoi（int n，char x，char y，char z）
{
if（n==1）
Move（1，x，z），
else
{
Hannoi（n-1，x，z，y）；
Move（n，x，z）；
Hannoi（n-1，y，x，z）；
}
}
int main（）
{
fout<<"下面是7层汉诺塔的解法：" <
fout.close（）；
cout<<" 输出完毕！" <
}
（3） 基于Ja的汉诺塔的算法实现程序如下：
public class HanoiTower {
static int nDisks = 3；
public static void main（String[] args） {
hanoiTower（nDisks， 'x'， 'y'， 'z'）；
}
public static void hanoiTower（int topN， char src， char inter， char dest） {
if （topN == 1）
System.out.println（"Disk 1 from " + src + " to " + dest）；
else {
// src to inter
hanoiTower（topN - 1， src， dest， inter）；
// move bottom
System.out.println（"Disk " + topN + " from " + src + " to " + dest）；
//inter to dest
hanoiTower（topN - 1， inter， src， dest）；
}
}
}
3 用组合数学的思想来分析汉诺塔问题的算法
汉诺塔问题也是组合数学中著名的问题，用组合数学的思想分析如图2所示。图2 基于组合数学思想的分析模型
检测设a1=1，a2=3，对于任何n≥3，那么：可以作如下设计：
第一步，将套在柱x的上部的n-1个盘按要求移到柱y上，共搬动了an-1次；
第二步，将柱x上的最大一个盘移到柱z上，只要搬动1次；
第三步，再从柱y将n-1个盘按要求移到柱z上，也要用an-1次。
则由加法法则，{an}满足：
3 结 语
汉诺塔问题是一个古老的数学问题，本文给出了四种不同的的经典算法，这几种算法的优点是逻辑清晰、易于理解、可读性好、算法语句少，一般论文格式范文www.udooo.com
有助于读者更好地对汉诺塔问题进行分析和探究。参 考 文 献
南基洙.组合数学[M].北京：高等教育出版社，2008.
（美）RICHARD Johnsonbaugh.大学算法教程[M].北京：清华大学出版社，2007.
[3] 严蔚敏，陈文博.数据结构及应用算法教程[M]..北京： 清华大学出版社，2011.
[4] 王春森.程序员教程[M].修订版.北京：清华大学出版社，2001.
[5] 刘军，张志峰.汉诺塔总是算法分析及C语言实现[J].计算机教学与教育信息化，2008，2（17）：1496-1498.