Linux环境下汉诺塔算法分析.doc

2013 —2014 学年第 一 学期 物电 学院期末考试卷 《Linux操作系统》 学号: 201172020142 姓名: 张靖峰 班级: 11级电子1班 成绩： 评语： （考试题目及要求） 题目：Linux环境下汉诺塔算法分析 要求：从键盘输入初始圆形盘子个数n，用C语言实现n个盘子最 佳移动的全过程。 目录 摘 要 2 （一） 问题描述 3 （二） 算法分析 3 （三） 关于Linux中C程序的运行 5 (四). Linux下C语言实现 7 1.说明 7 (四) 实现 12 (五) 运行结果: 14 (六) 课程设计总结： 15 致谢： 15 (七) 参考文献 15 Linux环境下汉诺塔算法分析 摘 要 汉诺塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。 传说固然只是传说，这个古老的故事到今天又引申出一连串的包括统筹、管理等等数学问题。在现实生活中，任何一个人都不可能直接写出移动盘子的每一个具体步骤。比较经典的使用递归算法也是在这方面做了大量研究得出的一种相对优化的算法方案。 文章对“汉诺塔”问题进行了详细的分析，给出了一种实现的算法，并用C语言实现。通过该问题的c实现，可使学习者清晰地观测到解决该问题的全过程。 关键词 汉诺塔，图形，点阵，直接写屏，动画，演示 （一） 问题描述 问题提出：有三个塔(分别为A号，B号和C号)。开始时，有n个圆形盘以从下到上、从大到小的次序叠置在A塔上。现要将A塔上的所有圆形盘，借助B搭，全部移动到c搭上，且仍按照原来的次序叠置。 移动的规则：这些圆形盘只能在3个塔间进行移动，一次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比它小的盘子的上面。 要求：从键盘输入初始圆形盘子个数n，用C语言实现n个盘子最佳移动的全过程。 （二） 算法分析 题目实现的是设计一个盘子移动的方案。使得A号塔上的所有盘借助于B号塔按照原来的次序移动到C号塔上，并且给出完整的最佳的盘子移动的方案。 从实际的、具体的盘子的移动过程来分析，找出问题内在的规律。经分析无论盘子的个数有多少，是1、2、3或n个，也不管怎么去移动盘子(当然是按一定规则移动)，但在移动的过程中，将始终会出现这样的状态情况：(n-1)个盘子将会以从下到上、从大到下的次序叠置在B塔上，这时，A塔上第n个盘子就能被轻而易举叠放到c塔上；接着，我们再把B塔上的共（n-1）个盘子移动到C塔上，问题好像已经解决。 但，B塔上（n-1）个盘子怎么移动到c塔上呢?这是要解决的第二个问题。同样，不管怎么移动，也将会出现这样的状态情况： (n-2)个盘子将会以从上到下、从大到小的次序叠置在A塔上，这时，B塔上第(n—1)个盘子就能被轻而易举放到c塔上；接着，把A塔上的共(n一2)个盘子移动到C塔上。 这样，不断深入，不断细小化。最终。将到达仅有一个盘的情形，这时，递归也就终止了，问题也得到了解决。通过以上分析，这里有很明显递归关系。 由此，想到了采用递归算法来解决该问题，因为递归算法有这样特征描述：为了求解出规模为n的问题的解，我们先设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的方法分解，分解成规模更小的问题。并能从这些更小的问题的结构造出规模稍大问题的解。特别地是，当规模n=l时，能直接得到解。 现在，严格按照递归算法来解决问题。先定义递归方法Hanio(int n,chlll-A，char B,char C)，按如下步骤进行解题(设初始盘子个数 为N)：若A塔上仅仅只有一个盘子(n=1)，则直接从A移动到c，问题完全解决。若A塔上有一个以上的盘子(n1)，则需要考虑以下 三个步骤。 第一步：把(n—l价盘子从A塔经过移动，叠放到B塔上。在不违反规则情况下，所有(n一1)个盘子不能作为一个整体一起移动，而是要符合要求地从一个塔移到另一个塔上。用Hanio(n—l，A，C，B)调用递归方法，注意：这里是借助于C塔，将(n—l价盘子从A塔移动到B塔，A