汉罗塔___数据结构实验.docVIP

计算机科学与工程学院 《算法与数据结构》试验报告[三] 专业班级 试验地点 计算机大楼计工教研室 学生学号 指导教师 学生姓名 试验时间 试验项目 算法与数据结构 试验类别 基础性（） 设计性（） 综合性（√） 其它（ ） 试验目的及要求 掌握用VC++上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。 成 绩 评 定 表 类 别 评 分 标 准 分值 得分 合 计 上机表现 积极出勤、遵守纪律 主动完成设计任务 30分 程序与报告 程序代码规范、功能正确 报告详实完整、体现收获 70分 备注： 评阅教师：  日 期： 年 月 日 试 验 内 容 一、实验目的和要求 1、实验目的： （1）掌握栈的特点及其存储方法； （2）掌握栈的常见算法以及程序实现； （3）了解递归的工作过程。 2、实验内容：Hanoi塔问题。（要求4个盘子移动，输出中间结果） 3、实验说明：三个盘子Hanoi求解示意图如下： 三个盘子汉诺塔算法的运行轨迹： Hanio算法如下： 1 void Hanoi(int n, char A, char B, char C) //第一列为语句行号 2 { if (n==1) Move(A, C); //Move是一个抽象操作，表示将碟子从A移到C上 else { Hanoi(n-1, A, C, B); Move(A, C); Hanoi(n-1, B, A, C); } } 设计分析 将所有的盘子看作三部分，最底层，倒数第二层以及上面的一个整体，进行基本移动操作，上面的一整体再次被分为三个部分，递归直到基层。在调用程序时只需要输入盘子的个数即可，移动盘子次数为。这可以作为一项程序无误的检测指标。 源程序代码 #include stdio.h void hanoi(int n,char A,char B,char C) { if(n=1) { hanoi (n-1,A,C,B) ; printf(将盘子从%c移动%c\n,A,C) ; hanoi(n-1,B,A,C); } } void main () { int n; printf(请输入盘子的个数:\n); scanf(%d,n); hanoi(n,A,B,C); } 四、测试用例（尽量覆盖所有分支） 1。n=1时。直接从C移动到A。 符合实际。 2。n=2时，C移动到B，C移动到A。 3.n比较大时，n=5。 盘子移动31次等于2的5次方减去1，无误。 五、实验总结 汉罗塔是典型的递归问题，通过这次实验，深刻理解了递归的含义，就像把洋葱的皮一层一层地剥下来。汉罗塔这个问题和栈的操作规则相同，通过这个对这个问题的研究，也加深了对栈的理解以及应用规则。实验过程中代码比较简短，但是比较难以理解，通过询问同学，上网查资料才弄明白操作的整个过程，受益匪浅。 计算机科学与工程学院 2 《算法与数据结构》试验报告 BA A BA CA A BA CA A CA A BA CA (a) (b) (c) (d) ⑸ ⑼ ⑶ Hanio(3,A,B,C) Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(2,A,C,B) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,C,A,B) Move (C,B) Move (A,B) Hanio(2,B,A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (B,A) 递归第一层 递归第二层 递归第三层 ⑴ ⑵ ⑷ ⑹ ⑺ ⑻ ⑽ ⑾ ⑿ ⒀ ⒁