[精品]汉诺塔问题实验报告

《[精品]汉诺塔问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1•实验目的：通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。2.问题描述：汉诺塔问题来自一个古老的传说：在世界刚被创建的吋候有一座钻石宝塔(塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔B和塔C)o从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。3.算法设计思想：对于汉诺塔问题的求解，可以通过以下三个步骤实现：(

2、1)将塔A上的ml个碟子借助塔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#ir)elude"stdafx・h"^include#include#ineludevoidhanoi(inin,charx,chary,cha

3、rz)(if(n==l){printf("从%c・〉搬到%c，，>x,z);elsehanoi(nT,x,z,y);printfC从％c->%c搬到",x,z);hanoi(r>T,y,x,z);voidmainO{intm;printf("inputthenumberofdiskes:");scanf(”%d",&m);prinl£("Thesteptomoving%3ddiskes:z，,m);hanoi(叫'「'b','c');自定义头文件:^pragmaonce^include^targetver.h"#include

4、>^include结果如下:inputthenumberofdiskes：2rhesteptomouing2diskes：从a->搬到b趴a-兀搬到从b-〉槨至lieinputthenumberofdiskes：3Thesteptomouing3disk巳s：丿』、3一>搬¥[

5、c》、a->b搬到从c->搬到b畑-〉c搬到->搬弧从b->c搬到换2->搬孤^.nputthenunberofdiskes：4u->搬到£”c->搬到从">搬到b'Aa->c搬到-〉搬或c”c->搬到从">搬到b'Aa->c搬到从、b->搬弧[Theste

6、ptomoving4diskes二从a->搬到b、a->c搬到Z.T~~■M一：pva->b搬到肛-〉搬到a从">b搬到从a->樓玉I.b''Aa->c搬到从b->搬孤从b->a搬到如-兀搬到辰-〉搬列b''Aa->c搬到6•递归应用中的Hanoi塔问题分析1）Hanoi塔问题中函数调用吋系统所做工作一个函数在运行期调用另一个函数时，在运行被调用函数Z前，系统先完成3件事：①将所有的实参、返回地址等信息传递给被调用函数保存。②为被调用函数的局部变量分配存储区；③将控制转移到被调用函数的入口。从被调用函数返回调用函数前，系统也应完成3件事：①保存被调用

7、函数的结果；②释放被调用函数的数据区；③依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（L1FO）,上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：L1F0,除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器

8、，便可正确指出最后一次信息在堆栈中存放的地址。一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i+1层。反之，退出第i层递归应返回至上一层，即i—1层。为了保证递归函数止确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返冋地址。每进

9、入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录