课程实践报告题目:汉诺塔姓名:学号:班级:日期:一实践目的1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力;2、进一步提升C语言的应用能力;3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力;5、训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风;6、提升文档写作能力。
二问题定义及题目分析汉诺塔(又称河内塔)问题是印度的一个古老的传说。
开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。
这是一个著名的问题,几乎所有的教材上都有这个问题。
由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:18,446,744,073,709,551,615这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年。
我们仅能找出问题的解决方法并解决较小N值时的汉诺塔,但很难用计算机解决64层的汉诺塔。
后来,这个传说就演变为汉诺塔游戏: 1.有三根杆子A,B,C。
A杆上有若干圆盘。
2.每次移动一块圆盘,小的只能叠在大的上面。
3.把所有圆盘从A杆全部移到C杆上。
经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动圆盘:如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C。
程序所能达到的功能:用户只需要输入所需的层数即可,程序会自动计算出最终需要的步骤,并同时给出中间移动的过程。
三概要设计1、设计思想如果盘子为1,则将这个盘子从塔座A移动到塔座C;如果不为1,则采用递归思想。
将塔座A的前n-1个盘子借助C盘(即目的盘)移到塔座B,移后,此时C为空座,那我们就可以将塔座A的第n个盘子移到塔座C了。
接下来就将塔座B的n-1个盘子借助A移到塔座C,从而完成盘子的移动。
2、数据类型结构体:用来存放盘子的栈。
同时,在函数的参数中还用到了结构体类型的引用。
其他类型:基本的数据类型,包括整形,字符型。
用来存放临时变量。
3、主要模块Main函数实现函数的调用,move函数实现输出,hanoi函数调用move函数实现移动和最终输出。
主要算法部分是通过函数的递归调用来实现。
4、模块关系程序从Main函数开始,到main函数结束。
Main函数通过调用hanoi函数来实现盘子的移动,然后由move函数输出在屏幕上。
四详细设计1、功能设计本程序的功能是建立一个汉诺塔模型,简化用户使用过程,便于用户直接查看一定的汉诺塔数据对应的移动步骤。
2、模块实现判断当前A柱上是否剩余一个盘子,若剩余一个,则:将其移动到C柱上;否则:将除A柱上最后一个盘子之外的所有盘子移动到B柱上,然后将A柱上最后一个盘子移动到C柱上,再将B柱上的所有盘子移动到C柱上。
直到最终所有盘子移动完毕。
五调试与测试分析1、调试错误一:void InitStack(SqStack*&s)/* 初始化栈 */{s=(SqStack)malloc(sizeof(SqStack));s->top=-1;}初始化栈的时候,把函数写成这样了,结果编译出错。
更改后如下,编译通过:void InitStack(SqStack*&s)/* 初始化栈 */{s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}错误二:for(int t=n;t>0;t--){Push(a,t);printf("\n\t将A柱的圆环移动到C柱的方法为:\n\n",n);i=Hanoi(n,a,b,c);free(a);free(b);free(c);printf("总共需要移动的次数为: %d次\n",i);}上面是主函数中的核心部分,在这种情况下,编译没有出现任何错误,但是运行时却发生了如下的现象:经过多次检查,最终发现了一个很低级的错误,改正后,运行结果正常:for(int t=n;t>0;t--){Push(a,t);}printf("\n\t将A柱的圆环移动到C柱的方法为:\n\n",n);i=Hanoi(n,a,b,c);free(a);free(b);free(c);printf("总共需要移动的次数为: %d次\n",i);2、测试共选取了两个测试用例,分别为常规的3层塔,和比较多一些的9层塔,运行结果如下:六结果分析及总结1、时空复杂度i f N=1 then write(A,’->’,C){把盘子直接从A移动到C}elseHanoi(N-1,A,C,B);{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱} //需要T(N-1)write(A,’->’,C);{把剩下的一个盘子从A移动到C} //需要1Hanoi(N-1,B,A,C); { 以A柱为中转柱将N-1个盘子从B柱移动到C柱}//需要T(N-1)即函数Hanoi(N)科分解为两个Hanoi(N-1)和一个移动操作;函数Hanoi运行时间用T(N)表示即T(N)=2T(N-1)+12、空间复杂度由于该算法主要用到了三个栈空间,大小均为N,因此空间复杂度就为O(N+N+N)。
七附录#include<stdio.h>#include<stdlib.h>#include<Windows.h>#define MaxSize30typedefstruct{int data[MaxSize];char name;int top;}SqStack;void Move(SqStack*&a,SqStack*&b);int Hanoi(int n,SqStack*&a,SqStack*&b,SqStack*&c);void InitStack(SqStack*&s);int Push(SqStack*&s,int e);/* 进栈 */int Pop(SqStack*&s,int&e);/* 出栈 */void main(){int hanoiNum,i;SqStack*a,*b,*c;InitStack(a);InitStack(b);InitStack(c);a->name='A';b->name='B';c->name='C';printf("请输入汉诺塔中圆环个数 n:");scanf("%d",&hanoiNum);for(int t=hanoiNum;t>0;t--){Push(a,t);}printf("\n\t将A柱的圆环移动到C柱的方法为:\n\n");i=Hanoi(hanoiNum,a,b,c);free(a);free(b);free(c);printf("%d层汉诺塔,总共需要移动的次数为: %d次\n",hanoiNum,i);system("pause");}void InitStack(SqStack*&s)/* 初始化栈 */{s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;}int Push(SqStack*&s,int e)/* 进栈 */{if(s->top==MaxSize-1)return0;s->top++;s->data[s->top]=e;return1;}int Pop(SqStack*&s,int&e)/* 出栈 */{if(s->top==-1)return0;e=s->data[s->top];s->top--;return1;}int Hanoi(int n,SqStack*&a,SqStack*&b,SqStack*&c){staticint i=0;if(n==1){Move(a,c);i++;}else{Hanoi(n-1,a,c,b);Move(a,c);i++;Hanoi(n-1,b,a,c);}return i;}void Move(SqStack*&a,SqStack*&b){int i;Pop(a,i);printf("\t\t%d环-->%c柱子\n",i,b->name);Push(b,i);}。