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 #include #include 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); } 2 } 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 #include 结果如下: 3 6 .递归应用中的Hanoi 塔问题分析 1)Hanoi 塔问题中函数调用时系统所做工作 一个函数在运行期调用另一个函数时,在运行被调用函数之前,系统先完成3 件事: ①将所有的实参、返回地址等信息传递给被调用函数保存。 ②为被调用函数的局部变量分配存储区; ③将控制转移到被调用函数的入口。 从被调用函数返回调用函数前,系统也应完成3 件事: ①保存被调用函数的结果; ②释放被调用函数的数据区; ③依照被调用函数保存的返回地址将控制转移到调用函数。 当有多个函数构成嵌套调用时,按照“后调用先返回”的...