文档介绍：5
}
实验目的：
通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。
问题描述：
汉诺塔问题來自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔(塔A),其上有64个金碟。所有碟子按从大H
II
2 dishes:从搬到b
O t Ju
p e
u p n
input the numbei' of diskes ：3
[The step to mouing 3 diskes "
!扁-〉b攥到 •
人C->搬到h 畑-兀搬到丛b->搬至[a
Ab->c搬到从应-> 搬到C
input the number of diskes:4
The step to moving 4 disk&s二从搬到b 从a-〉c搬到
搬到从a-〉b搬钊从c->b搬刘从&->搬到b 从a->G搬到从h->攒王ijc 从bf搬到从c->搬到从h->(:搬到如->搬到b 如亠搬到如-> 槻予k
6•递归应用中的Hanoi塔问题分析
1) Hanoi塔问题中函数调用时系统所做工作
一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：
将所有的实参、返回地址等信息传递给被调用函数保存。
为被调用函数的局部变量分配存储区；
3
}
将控制转移到被调用函数的入口。
从被调用函数返回调用函数前，系统也应完成3件事：
保存被调用函数的结果；
释放被调用函数的数据区；
依照被调用函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则
(LIFO),上述函数之间的信息传递和控制转移必须通过“栈”來实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO,除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指岀最后一次信息在堆栈中存放的地址。
一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i + 1层。反之，退出第i层递归应返回至上一层，即i —1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
2） Hanoi塔问题递归程序的复杂度分析
①运行hanoi程序的时间
程序hanoi. c在硬件环境为赛扬400MHz、内存128M的汁算平台（不