汉诺塔程序实验报告

汉诺塔程序实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 篇一:汉诺塔程序实验报告 实验 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目: Hanoi塔问题 一、问题描述: 假设有三个分别命名为A，B和C的塔座，在塔座B上插有n个直径大小各不相同、从小到大编号为1，2，„，n的圆盘。现要求将塔座B上的n个圆盘移至塔座A上并仍按同样顺序叠排，圆盘移动时必须遵守以下规则: (1)每次只能移动一个圆盘; (2)圆盘可以插在A，B和C中任一塔上; (3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 要求:用程序模拟上述问题解决办法，并输出移动的总次数，圆盘的个数从键盘输入;并想办法计算出程序运行的时间。 二、 算法思路: 1、建立数学模型: 这个问题可用递归法解决，并用数学归纳法又个别得出普遍解法: 假设塔座B上有3个圆盘移动到塔座A上: (1)"将塔座B上2个圆盘借助塔座A移动到塔座C上; (2)"将塔座B上1个圆盘移动到塔座A上; (3)"将塔座C上2个圆盘借助塔座B移动到塔座A上。 其中第2步可以直接实现。第1步又可用递归方法分解为: 1.1"将塔座B上1个圆盘从塔座X移动到塔座A; 1.2"将塔座B上1个圆盘从塔座X移动到塔座C; 1.3"将塔座A上1个圆盘从塔座Z移动到塔座C。 第3步可以分解为: 3.1 将塔座C上1个圆盘从塔座Y移动到塔座B; 3.2 将塔座C上1个圆盘从塔座Y移动到塔座A; 3.3 将塔座B上1个圆盘从塔座X移动到塔座A。 综上所述:可得到移动3个圆盘的步骤为 B->A,B->C, A->C, B->A, C->B, C->A, B->A, 2、算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 : 将n个圆盘由B依次移到A，C作为辅助塔座。当n=1时，可以直接完成。否则，将塔座B顶上的n-1个圆盘借助塔座A移动到塔座C上;然后将圆盘B上第n个圆盘移到塔座A上;最后将塔座C上的n-1个圆盘移到塔座A上，并用塔座B作为辅助塔座。 三、原程序 #include<stdio.h> #include <iostream.h> #include <windows.h> int times = 0; void move(char a, char b) { printf("%c ----> %c \n", a,b); } void hno(int n,char a , char b, char c) { if (n==1) { move(a,c); times ++; } else { hno(n-1,a,c,b); move(a,c); times ++; hno(n-1,b,a,c); } } void main() { unsigned start,finish; int N; printf("请输入汉诺塔的层数:"); scanf("%d",&N); start=GetTickCount();// hno(N,'B','C','A'); finish=GetTickCount(); float time=(finish-start)/1000.0; printf("共移动了%d次! \n",times); cout<<"总共需要时间为: "<<time<<endl; } 四: 五(结论分析 通过对上述递归在 Hanoi 塔问题上的应用分析，可以得出如下结论: 递归应用中的Hanoi塔问题分析递归应用中的 1、Hanoi 塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事: 1将所有的实参、返回地址等信息传递给被调用函数保存。 ? 2为被调用函数的局部变量分配存储区; ? 3将控制转移到被调用函数的入口。 ? 从被调用函数返回调用函数前，系统也应完成3件事: ?保存被调用函数的结果; ?释放被调用函数的数据区; ?依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成 嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转 移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个 栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数 退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。 2、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化; 3、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源(包括堆栈、软中断和存贮空间等)，并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但 4、递归是串行的，其第n步运算依赖于第 n-1 步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是 否存在并行递归计算有待进一步探讨。 篇二:汉诺塔演示程序实验报告 课 程 设 计 报 告 课程名称:高级语言课程设计 课程代码: 07300561 设计内容: 汉诺塔演示系统 专 业:计算机科学与技术 2012 年 12月 16日 目 录 1.课程设计目的............................................................ 3 1.1 内容简介............................................. 错误～未定义书签。 1.2 功能实现............................................. 错误～未定义书签。 2.课程设计题目描述和要求.................................................. 3 2.1 描述................................................. 错误～未定义书签。 2.2 要求................................................. 错误～未定义书签。 3.课程设计报告内容........................................................ 3 3.1 内容概要............................................. 错误～未定义书签。 3.2 功能实现............................................. 错误～未定义书签。 3.3 程序 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图........................................... 错误～未定义书签。 3.4程序截图 .............................................................. 6 3.5详细内部设计介绍 4.总结 5小组分工情况 1.课程设计目的 随着社会的进步我们用来娱乐的游戏世界也越来越丰富，越来 越复杂。本程序的汉诺塔游戏不但包括了游戏最基本的功能，而且还能培养用户的逻辑思维能力，本游戏实现的是一个自动演示搬移汉诺塔的功能，此功能能够帮助初次接触此游戏的用户了解此游戏的玩法。 2.课程设计题目描述和要求 2.1 描述 本程序是一个能够实现汉诺塔搬移演示功能的MFC程序 2.2要求 实现用图形界面，画出三个杆和最多七个矩形盘子，形成三个塔，分别为A、B、C塔，同时盘子数目可以人工进行设定，让程序自动的完成把A塔上的盘子搬移到C塔上的过程，实现自动演示。 3.课程设计报告内容 3.1内容概要 有三个 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示塔的对象，分别命名为A、B、C塔，A上有若干个(不超过七个)盘子，盘子大小不等，并按照大小顺序依次摆放在A塔上，大盘在下小盘在上，程序实现自动演示，把A塔上的盘子依次全部搬移到C塔上，要求每次只能移动一个盘子并且在任何时候不允许大盘子在小盘子之上，并且在演示过程中可以实现暂停功能。 3.2功能实现 设计图形用户界面的MFC程序，用户可以通过单击汉诺塔界面中提供的按钮，进行盘子数量的设置并且单击开始按钮让程序自动演示A塔上盘子移动到C塔上的过程，并且在程序运行过程中可随时单机程序界面中提供的按钮实现游戏暂停，重新开始游戏 等功能。 3.3程序流程图 3.4程序截图 1、开始游戏: 为了更好地人机交互，在执行游戏时会弹出一个欢迎的对话框。 功能图: 相关代码:int CMyDlg::OnCreate(LPCREATESTRUCT lpCreateStruct) { if (CDialog::OnCreate(lpCreateStruct) == -1)return -1; // TODO: Add your specialized creation code here MessageBox("欢迎进入游戏!"); return 0; } 2(游戏主界面 2.开始演示 相关代码: void CMyDlg::OnButton1() { 篇三:汉诺塔问题实验报告 1.实验目的: 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔 游戏的时间复杂性和空间复杂性。 2.问题描述: 汉诺塔问题来自一个古老的传说:在世界刚被创建的时候有一 座钻石宝塔(塔A),其上有64个金碟。所有碟子按从大到小的次 序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔B 和塔C)。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 3.算法设计思想: 对于汉诺塔问题的求解，可以通过以下三个步骤实现: (1)将塔A上的n-1个碟子借助塔C先移到塔B上。 (2)把塔A上剩下的一个碟子移到塔C上。 (3)将n-1个碟子从塔B借助于塔A移到塔C上。 4.实验步骤: 1. 用c++ 或c语言设计实现汉诺塔游戏; 2. 让盘子数从2 开始到7进行实验，记录程序运行时间和递归调用次数; 3. 画出盘子数n和运行时间t 、递归调用次数m的关系图，并进行分析。 5.代码设计: Hanio.cpp #include "stdafx.h" #include <stdlib.h> #include <stdio.h> #include <iostream> void hanoi(int n,char x,char y,char z) { if(n==1) { printf("从%c->搬到%c\n",x,z); } else { hanoi(n-1,x,z,y); printf("从%c->%c搬到\n",x,z); hanoi(n-1,y,x,z); } } void main() { int m ; printf("input the number of diskes:"); scanf("%d",&m); printf("The step to moving %3d diskes:",m); hanoi(m,'a','b','c'); } 自定义头文件 :#pragma once #include "targetver.h" #include <stdio.h> #include <tchar.h> 结果(本文来自:WWw.HNboxU.com 博 旭 范文 网:汉诺塔程序实验报告)如下: 6.递归应用中的Hanoi塔问题分析 1)Hanoi塔问题中函数调用时系统所做工作 一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事: ?将所有的实参、返回地址等信息传递给被调用函数保存。 ?为被调用函数的局部变量分配存储区; ?将控制转移到被调用函数的入口。 从被调用函数返回调用函数前，系统也应完成3件事: ?保存被调用函数的结果; ?释放被调用函数的数据区; ?依照被调用函数保存的返回地址将控制转移到调用函数。 当有多个函数构成嵌套调用时，按照“后调用先返回”的原则(LIFO)，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈 顶。堆栈特点:LIFO，除非转移或中断，堆栈内容的存或取表 现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。 一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层;从第i层递归调用本函数为进入下一层，即i，1层。反之，退出第i层递归应返回至上一层，即i,1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。 2)Hanoi塔问题递归程序的复杂度分析 ? 运行hanoi程序的时间 程序 hanoi.c 在硬件环境为赛扬 400MHz、内存128M的计算平台(不同机器运行时间有一定差别)运行，可得出如下时间结果: 盘子数 时间结果 <=12个 <=1秒 14个 2秒 16个13秒 20个 204秒 ? 时间复杂度 程序所花时间正比于所输出的信息行数目，而信息行的数目则等价于盘子的移动次数。考察程序，设盘子移动次数为moves(n)，则: moves(n)= 用迭代方法计算公式，得到结果moves(n)=2n-1。因此，hanoi函数的时间复杂度为O(2 n) 。 ? 空间复杂度 从每个塔上移走盘子时是按照LIFO进行，因此可以把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是n个。如果使用链表形式的堆栈，只需申请n个元素所需要的空间。如果使用的是基于公式化描述的堆栈，塔1和塔2的容量都必须是n，而塔3的容量是n,1，因此所需要的空间总数为3n,1。 Hanoi塔问题的复杂性是以n为指数的函数，因此在可以接受的范围内，只能解决n值比较小(n<=30)的hanoi问题。对于这个较小的n值，堆栈在空间需求上的差别相当小，可以随意使用。 7、结论 通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论: 1、递归调用过程中，在程序执行之前无法知道控制这种调用栈 的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化; 2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源(包括堆栈、软中断和存贮空间等)，并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但 3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。 8、总结