C语言程序设计课程设计报告汉诺塔问题.docx
- 文档编号:15430884
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:13
- 大小:122.64KB
C语言程序设计课程设计报告汉诺塔问题.docx
《C语言程序设计课程设计报告汉诺塔问题.docx》由会员分享,可在线阅读,更多相关《C语言程序设计课程设计报告汉诺塔问题.docx(13页珍藏版)》请在冰点文库上搜索。
C语言程序设计课程设计报告汉诺塔问题
XXXX大学
计算机科学与技术学院
课程设计报告
2012—2013学年第一学期
课程名称C/C++高级语言程序设计课程设计
设计题目小游戏和图形处理
汉诺塔问题
学生姓名XXX
学号XXXXXXX
专业班级XXXXXXXXXXX
指导教师XX
2012年X月XX日
1、课程设计问题描述
1、课程设计题目
汉诺塔问题
2、设计任务要求
输入盘子数(2个以上有效),移动速度,开始演示汉诺塔移动的步骤,要求:
盘子A,B,C柱需要自己绘制,初始时盘子在A柱上通过B柱最终移动到C柱上,显示出盘子在几个柱之间的移动过程。
2、总体设计
1、设计思路
对于一个类似的这样的问题,任何一个人都不可能直接写出移动盘子的每一个具体步骤。
可以利用这样的统筹管理的办法求解:
我们假设把该任务交给一个僧人,为了方便叙述,将他编号为64。
僧人自然会这样想:
假如有另外一个僧人
能有办法将63个盘子从一个座移到另一个座,那么问题就解决了,此时僧人
ABC
64只需这样做:
(1).命令僧人63将63个盘子从A座移到C座
(2).自己将最底下的最大的一个盘子从A座移到C座
(3).再命令僧人63将63个盘子从B座移到C座
为了解决将63个盘子从A座移到B座的问题,僧人63又想:
如果能再有一个僧人62能将62个盘子移动到另一座,我就能将63个盘子从A座移动到B座。
他是这样做的:
(1).命令僧人62将62个盘子从A移动到C
(2).自己将一个盘子从A座移动到B座
(3).再命令僧人62将62个盘子移到B座
再进行一次递归。
如此“层层下放”,直到后来找到第2个僧人,让他完成将2个盘子从一个座移到另一个座,进行到此,问题就解决了。
最后找到第1个僧人,让他完成将一个盘子从一个座移动到另一个座,至此,全部工作已经完成,都是可以执行的。
按照如此的思路设计递归算法,很容易得出盘子的移动方案。
2、汉诺塔求解流程图
输入盘子数n
是n<=2否
输出:
输入错误递归调用
输出结果
结束
3、详细设计
1、汉诺塔问题描述
可以看出,递归调用的结束条件是最后一个步骤只需要移动一个盘子。
否则,递归过程还将继续进行下去。
只有僧人1的任务完成后,僧人1的任务才能完成。
若将问题简化,将两个盘子移动的过程可以这样描述:
(1).将盘子1移动到B座
(2).将盘子2移动到C座
(3).将盘子1从B座移动到C座
一共经历了3个步骤,我们可以很容易地推断出,移动N个盘子需要
个步骤。
编写程序时,用若干个程序实现这个操作,用hanoi函数实现编号较大的僧人需要完成的任务。
用move()实现编号较小的僧人需要完成的任务。
2、算法分析
题目实现的是设计一个盘子移动的方案。
使得A号塔上的所有盘子借助于B号塔按照原来的次序移动到C号塔上,并且给出完整的最佳的盘子移动的方案。
从实际的、具体的盘子的移动过程来分析,找出问题内在的规律。
经分析无论盘子的个数有多少,是1、2、3或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(intn,charA,charB,charC),按如下步骤进行解题(设初始盘子个数为n):
若A塔上仅仅只有一个盘子(n=1),则直接从A移动到c,问题完全解决。
若A塔上有一个以上的盘子(n>1),则需要考虑以下三个步骤:
第一步:
把(n—l)个盘子从A塔经过移动,叠放到B塔上。
在不违反规则情况下,所有(n一1)个盘子不能作为一个整体一起移动,而是要符合要求地从一个塔移到另一个塔上。
用Hanio(n—l,A,C,B)调用递归方法,注意:
这里是借助于C塔,将(n—l)个盘子从A塔移动到B塔,A是源塔,B是目标塔。
第二步:
将剩下的第11个盘子(也就是最底下的一个)直接从A塔叠放到空着的C塔上。
第三步:
用第一步的方法,再次将B塔七的所有盘子叠放到C塔上。
同样,这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。
用Hanio(n—l,B,A,C)调用递归方法,注意:
这里是借助于A塔,将(n一1)个盘子从B塔移动到C塔,B是源塔,C是目标塔。
这个算法达到了预期的目标。
即在C塔上按正确的次序叠放了所有的圆形盘子。
有了前面问题算法分析的基础,继而,可以用C语言来实现算法。
3、实现递归的条件
用递归法解决的问题,应该符合以下3个条件:
(1).能把原问题转化成一个新问题,且新问题的求解方法与原问题相同
(2).将原问题转化成新问题后,能使求解算法的规模减小
(3).递归有一个明显的出口,或称为递归的边界,而边界问题的解是显而易见的或已知的
4、用C语言实现
依据上述分析可知,汉诺塔问题符合实现递归的条件,而C语言又可解决递归问题,据此,我们用C语言来实现对汉诺塔问题的求解,我们用han函数来实现原问题转化为新问题的操作,用move函数实现递归边界的操作,用main主函数提出问题,确定需移动盘子的数目,现编写程序步骤如下:
(1).n为A塔初始盘子个数;
(2).A塔上盘子从上到下、从小到大编号依次为l,2,3⋯;
(3).hanoi方法采用递归算法,实现盘子移动的最佳方案。
递归算法的执行过程分为递推和回归两个阶段。
在递推阶段,把较为复杂的问题(如规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解,例如上面分析过程中。
为求解Hanio(n,A,B,c),推到计算Hanio(n一1,A,C,B)。
在回归阶段,当获得最简单情况的解后,逐级返回,依次获得稍复杂问题的解。
在这里的“汉诺塔”问题中。
有它的特别的地方,回归的过程当中,还要涉及到递推。
4、程序运行结果测试与分析
1、打开MicrosoftVisualC++6.0操作平台输入以下的源代码
#include
voidhanoi(intn,chara,charb,charc,int&step);//移动盘子
oidmove(intnum,charfron,charto,int&step);//显示盘子移动步骤及步数
intstep;
intmain()
{
intn;
printf("请输入汉诺塔的金片数:
");
scanf("%d",&n);
step=0;
if(n<=2)
{printf("输入错误\n");
return0;
}
printf("移动盘子的步骤:
\n",n);
hanoi(n,'A','B','C',step);
printf("移动盘子的步数:
%d\n",step);
return0;
}
voidhanoi(intn,chara,charb,charc,int&step)
{
if(n==1){move(n,a,b,step);}//盘子从a移动到b
else{
hanoi(n-1,a,c,b,step);//将第n-1个盘子,借助于b由a移动到c
move(n,a,b,step);//第n个盘子由a-》b
hanoi(n-1,c,b,a,step);//将第n-1个盘子,借助于a由c移动到b
}
}
voidmove(intnum,charfrom,charto,int&step)
{
step++;
printf("move%d:
from%cto%c\n",num,from,to);
}
2、编译源代码
3、组建
4、执行
5、运行结果
(1).输入2运行结果如下
(2).输入4运行结果如下
6、按任意键结束程序
5、结论与心得
通过此次对MicrosoftVisualC++6.0的使用,对MicrosoftVisualC++6.0的功能和作用有了更多的理解。
以前我总是以为MicrosoftVisualC++6.0是很简单的工具,只能在文本方式下运行,过往想当然的想法使我对软件开发工作没有全面而客观的认识。
而现在通过这个课程设计题目,并而我选择了一个对我来讲相当富有挑战性的题目,这更使我认识到,仅仅是学会书面知识是不行的,一方面,对程序设计语言本身的理解不够透彻,另一方面,由于对数据结构及常用算法的理解上的欠缺,再加上我自己在这方面的练习相当少,这些都不同程度地添加了我完成这个题目的困难度。
要做算法的设计首先是对程序设计语言的相当的熟悉,而且能够实际熟练地运用,要能够把自己的想法,转换为由程序设计语言来表达。
这就要求自己不仅仅要会解决实际问题,而且要有能够将实际问题抽象化,数学建模,以及能用计算机程序设计语言来表达实现。
这对我们的程序设计水平和对程序语言代码的敏感度以及专业修养是一个很好的挑战。
其次,算法设计的要求也不仅仅是程序设计语言,前面讲到了由实际具体问题抽象建模,由于计算机内部是由二进制来表示和存储数据,程序设计语言实现了计算机内部表示和程序员和计算机交流的语言断层,而程序设计语言和自然语言之间又有一个断层,这个断层就需要靠程序员的集体或个人脑力劳动来弥补。
软件总体质量的好坏除了对软件工程的设计者相关,程序设计者的水平至关重要。
从自然语言到计算机能够读懂的程序设计语言,是对程序设计能力的考验。
仅仅是对程序设计语言的熟悉理解和熟练操作运用是不行的。
算法的设计是一个多方面的工作,一方面,我们需要对实际工作中所涉及到的可行性进行分析,另一方面,我们还需要完成对实际问题的研究性解决。
有时候,一个问题的解并不是唯一的,而多解问题并不是每个解都是同质同性的,它们之间或多或少有这样那样量度甚至质的区别。
比如在我们这个课题中,我们选择了汉诺塔求解演示。
通过计算机设计的算法,求解得到较优化的图形演示方案。
我们所涉及的问题是怎样尽可能地使界面美观而又能直观、生动地达到演示效果,在这些方案中,不断地比较,进行优化选择。
前面已经提到了,经过反复的测试比较,还能找出这个设计的很多不足甚至于错误,也就是说,我现在所做的设计并不是那么尽善尽美的。
但它相比较其它同类型的演示程序,已经有了很大的进步。
最后,感谢指导老师悉心指导,感谢同学们无私的帮助。
6、参考文献
[1]陆润民.C语言绘图教程.北京:
清华大学出版社,1996
[2]陈锦昌,赵明秀.C语言计算机绘图教程.广州:
华南理工大学出版社,
1998.9
[3]网冠科技.C语言时尚编程百例.北京:
机械工业出版社,2004.1
[4]贾宗璞,许合利.C语言程序设计.北京:
人民邮电出版社,2011.8
7、附录:
程序源代码
#include
voidhanoi(intn,chara,charb,charc,int&step);//移动盘子
voidmove(intnum,charfron,charto,int&step);//显示盘子移动步骤及步数
intstep;
intmain()
{
intn;
printf("请输入汉诺塔的金片数:
");
scanf("%d",&n);
step=0;
if(n<=2)
{printf("输入错误\n");
return0;
}
printf("移动盘子的步骤:
\n",n);
hanoi(n,'A','B','C',step);
printf("移动盘子的步数:
%d\n",step);
return0;
}
voidhanoi(intn,chara,charb,charc,int&step)
{
if(n==1){move(n,a,b,step);}//盘子从a移动到b
else{
hanoi(n-1,a,c,b,step);//将第n-1个盘子,借助于b由a移动到c
move(n,a,b,step);//第n个盘子由a-》b
hanoi(n-1,c,b,a,step);//将第n-1个盘子,借助于a由c移动到b
}
}
voidmove(intnum,charfrom,charto,int&step)
{
step++;
printf("move%d:
from%cto%c\n",num,from,to);
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言程序设计 课程设计 报告 汉诺塔 问题