实验五 汉诺塔问题

一、实验目的

本实验课程是计算机、智能、物联 等专业学生的一门专业课程，通过实验，帮助学生更好地掌握人工智能相关概念、技术、原理、应用等；通过实验提高学生编写实验 告、总结实验结果的能力；使学生对智能程序、智能算法等有比较深入的认识。

二、基本要求

1.实验前，复习《人工智能》课程中的有关内容。
2.准备好实验数据。

三、实验软件

推荐使用C或C++（Visual studio等平台）（不限制语言使用，如Java，matlab，Python等都可以）。

四、实验内容：

（3）汉诺塔问题
汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。
采用问题归约法把汉诺塔问题分成以下三个步骤实现：
?将塔A上的n-1个碟子借助塔C先移到塔B上
?把塔A上剩下的一个碟子移到塔C上
?把n-1个碟子从塔B借助于塔A移到塔C上
实验要求：
1.让盘子数从2?开始到7进行实验，记录程序运行时间和递归调用次数。
2.画出盘子数n和运行时间t?、递归调用次数m的关系图，并进行分析

五、实验程序组成：

（1）使用的函数及作用：
Move(int n, char A, char B);
//移动两个盘子
Hanoi(int n,char A, char B, char C);
//分析当前状态并决定下步操作
(2)实验代码：

六、实验结果分析：

当n=2时，

当n=5时，

分析：
让盘子数从2到7进行实现，对盘子数n和运行时间t?、递归调用次数m之间的关系进行分析。
※其中 左竖坐标是时间，右竖坐标是次数，横坐标是盘子数

总结：
1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源(包括堆栈、软中断和存贮空间等)，并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。最后，通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对
程序性能的影响，也让我明白掌握了算法将会有助于提高软件的开发。

文章知识点与官方知识档案匹配，可进一步学习相关知识Python入门技能树人工智能机器学习工具包Scikit-learn215270 人正在系统学习中