汉诺塔问题实验报告

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

2、碟子借助塔C先移到塔B上。(2) 把塔A上剩下的一个碟子移到塔C上。(3) 将n-1个碟子从塔B借助于塔A移到塔C ±o4. 实验步骤：1. 用c卄或c语言设计实现汉诺塔游戏；2. 让盘子数从2开始到7进行实验，记录程序运行时间和递 归调用次数；3. 画出盘子数n和运行时间t、递归调用次数m的关系图, 并进行分析。5. 代码设计： Hanio.cpp ttinclude "stdafx. h" include <stdlib. h> include <stdio. h>include <iostream>void hanoi(i

3、nt n, char x,char y, char z)if(n=l)printf ("从搬到%cn*, x, z);elsehanoi(nl,x,z,y);printf (*从%c>%c搬到n", x, z);hanoi (n_l, y, x, z);void main()int m ;printf("input the number of diskes：");scanf&m);printf(*The step to moving %3d diskes:",m); hanoi (m. ' a' .' b&

4、#39;,' c');)自定义头文件:pragma once#include "targetver h"井include <stdio. h>#include <tchar h>结果如下:movincfHII2 dishes:从搬到bO t Jup eu p ninput the numbei' of diskes ：3The step to mouing 3 diskes "!扁-b攥到人C->搬到h 畑-兀搬到 丛b->搬至aAb->c搬到 从应-> 搬到Cinput the number

5、 of diskes:4The step to moving 4 disk&s二从搬到b 从a-c搬到搬到 从a-b搬钊 从c->b搬刘 从&->搬到b 从a->G搬到 从h->攒王ijc 从bf搬到 从c->搬到 从h->(:搬到 如->搬到b 如亠搬到 如-> 槻予k6递归应用中的Hanoi塔问题分析1) Hanoi塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时，在运行被调用函数之前，系 统先完成3件事： 将所有的实参、返回地址等信息传递给被调用函数保存。 为被调用函数的局部变量分配存储区； 将控制转移到被调用

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

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

8、层的返回地址。每进入一层递归， 就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹 出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的 工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶 指针为“当前环境指针”。2） Hanoi塔问题递归程序的复杂度分析运行hanoi程序的时间程序hanoi. c在硬件环境为赛扬400MHz、内存128M的汁算平台 （不同机器运行时间有一定差别）运行，可得出如下时间结果：盘子数时间结果<=12 个<=1秒14个2秒16个13秒20个204秒时间复杂度程序所花时间正比于所输出的信息行数LI,而信息行的数目则等价 于盘子的移动次

9、数。考察程序，设盘子移动次数为moves (n),贝归moves(n)二用迭代方法计算公式，得到结果moves (n)-2n-lo因 此，hanoi函数的时间复杂度为0(2 n)。空间复杂度从每个塔上移走盘子吋是按照LIFO进行，因此可以 把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是 n个。如果使用链表形式的堆栈，只需申请n个元素所需要的空间 如果使用的是基于公式化描述的堆栈，塔1和塔2的容量都必须是 n,而塔3的容量是n1,因此所需要的空间总数为3n-loHanoi塔问题的复杂性是以n为指数的函数，因此在可以接受的范 围内，只能解决n值比较小(n<=30)的hanoi问题。对于这个较 小的n值，堆栈在空间需求上的差别相当小，可以随意使用。7、结论通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下 结论：1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的 规模，因为这一规模取决于递归调用的次序。在这种情况下，程序 的地址空间可能动态变化；2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程 序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机 时需要占用大量系统资源(包括堆栈、软中断和存贮空间等)，并 消耗大量处理时间。因此，可以考