汉诺塔问题汇总

《汉诺塔问题汇总》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章汉诺塔问题6第一章汉诺塔问题1.1.问题描述1.1.1题目内容用一个递归算法建立程序，实现汉诺塔问题的圆盘的移动。1.1.2基本要求在这个汉诺塔问题中，假设有三个分别命名为A,B和C,在塔座A上插有n个直径大小各不同的圆盘。要求将A轴上的n个圆盘移至塔座C上并任按同样顺序叠排，圆盘移动时必须遵循以下规则：1.每次只能移动一个圆盘；2.圆盘可以在X,Y和Z中的任意塔座上；3.任何时候都不能将一只较大圆盘压在较小的圆盘之上。最后输出移动的步骤以及移动的起始位置。1.1.3待测试数据该程序输入数

2、据比较单一，为整型，可将待测试数据设置为2、3、4、5、6。1.2.需求分析1.2.1程序所能达到的基本功能汉诺塔盘座的数量是固定的，用户可以自己确定盘的数量（1~~n）。在用户确定数量之后，程序开始自动运行（移动圆盘），并依次打印出移动的步数与路线，运行结束。1.2.2输入形式和输出值的范围输入数据为整型数据，设定圆盘的数量，输出跟踪的步数也应为一个整型数据。1.2.3输出的形式将步数和移动的位置逐个输出形成一个序列。1.2.4测试数据要求输入数据为整型，且不要过大，否则运算量会很大并且没有多

3、大的实际意义。1.3.概要设计1.3.1主程序流程及模块调用关系主程序流程图见下页：第一章汉诺塔问题6主程序流程图:模块调用关系图:主程序输入模块实现模块结果输出模块图1-2模块调用关系1.1.1核心粗线条伪码算法AlgorithmTower(valmvalA,B,Crefi)1.n=m//输入一个整型数字以设定圆盘的数量2.if(i=1)第一章汉诺塔问题61.mov(A,C)//BaseCase的处理2.else//递归调用的

4、方法处理GeneralCase1.tower(n-1,A,C,B)2.mov(A,C)3.tower(n-1,B,A,C)3.endifEndTower1.4.详细设计1.4.1每个操作的伪码算法设计一个成员函数，命名为move_disk(),其中设置两个形参charsrc和chardst分别表示两个塔盘A和Co这个函数中，只做src===dst操作，同时使i的值增加1,即用语句i=i++ovoidtowers(intn,charsrc,charmid,chardst)｛//在该成员函数中，n,

5、src,mid,dst分别表示圆盘的个数与三个塔盘If(n==1)｛调用move_disk函数｝Elsetowers(n-1,src,dst,mid);〃以dst(C塔)为辅助，将1到n-1号圆盘全部移动到mid(B塔)上move_disk(src,dst);//直接将A塔上的圆盘移动到C盘上towers(n-1,mid,src,dst);//将B塔上的1至n-1号盘移动至C塔上｝1.4.2函数调用关系在主函数中，设定一个整型变量disk以用来向成员函数中传递参数做为圆盘的数量，然后直接调用以上

6、函数。再用while(n=='y'n=='Y')｛直接调用以上函数｝设定一个是否需要重复运行的功能。最后程序结束，设置结束界面。1.5.调试分析1.5.1设计与调试过程中遇到的问题及分析、体会(1).关于Basecase勺调用问题在开始时，根据程序的概要设计，分别在Hanoi类中写了BaseCase和GeneralCaseM个功能函数，move_disk()与towers()。然后再在主程序中分别对这两个函数进行调用，出现了第一行可题，例如当输入圆盘个数为3时，圆盘只移动了五次，如图1-3所示，

7、画图跟踪，其结果是错误的。经过多次的分析调试，最后在towers()函数中先调用move_disk()操作，然后在主函数中只对towers()ffi行调用，得到了正确的结果如图1-4所示。分析可知，这个错误的出现主要是对BaseCase勺理解上没有做好，只要深刻理解了BaseCas酢口General第一章汉诺塔问题6Case的意义和关系，再利用递归思想便能很好的掌握了Nunbet'o£disksCl^lS>：3stepsfroptto1A->C2C=====>B3B=====>ft4AC5A…=

8、=》CContinue.-.Nunherafdisks>：3Continue__.：_第一章汉诺塔问题6第一章汉诺塔问题6图1-3图1-4(1).输入数据的合法性的处理程序大体完成后，开始了考虑输入数据的合法性的处理，在程序中，输入数据很简单，就只有一个整型数据disks首先限定其范围，限定在1到15之间,因为数据过大没有多大的意义，且运算时间很长(15个圆盘需移动的步数已达32767之多)。然而当输入数据不是数字时，便出现了死循环如图1-5所示。图1-5经过多次分析，调试与