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 件事： ①保存被调用函数的结果； ②释放被调用函数的数据区； ③依照被调用函数保存的返回地址将控制转移到调用函数。 当有多个函数构成嵌套调用时，按照“后调用先返回”的...
