开发工具:
文件大小: 87kb
下载次数: 0
上传时间: 2009-03-13
详细说明： 汉诺塔 vc++ 面向对象编程课程作业 汉诺塔（Towers of Hanoi）问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔，其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔。从世界创始之日起，婆罗门的牧师们就一直在试图把塔1上的碟子移动到塔2上去，其间借助于塔3的帮助。由于碟子非常重，因此，每次只能移动一个碟子。另外，任何时候都不能把一个碟子放在比它小的碟子上面。按照这个传说，当牧师们完成他们的任务之后，世界末日也就到了。 一、问题分析 1.对三个塔进行编号，分别为a、b、c。我们有以下结论： 1）当盘子只有一个，则盘子移动情况为：a->b。 2）对于大于两个盘子的情况，我们可以把盘子看成两个部分：第n个盘子和第n个盘子上面的n-1个盘子。 2.若将除n外的n-1个盘子看成一个整体，则可将问题按以下方法考虑： 1）将a塔上的n-1个盘子借助于b塔先移动到c塔，a->c。 2）将a塔上的n 个盘子从a塔移动到b塔，a->b。 3）将c塔上的n-1个盘子借助于a塔移动到b塔，c->b。 3.再将n-1个盘子按照n个盘子的方法分析。 二、 算法选择 汉诺塔问题，是一个非常经典 的运用递归算法实现的问题。虽然也有非递归的算法可以使用，并且非递归的算法可以节省很大的预算量，但是在本程序中，我还是选择了传统的递归算法。 为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己定义自己的方法，称为递归定义。 例如： 则当 时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)…… 当n=0时，f(n)=1。 由上例我们可看出，递归定义有两个要素： 1. 递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。 2. 递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。 递归算法的效率往往很低， 费时和费内存空间。 但是递归也有其长处， 它能使一个蕴含递归关系且结构复杂的程序简介精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步没其结果仍维持原问题的关系，则采用递归算法编程比较合适。 3. 递归按其调用方式分为： 直接递归, 递归过程P直接自己调用自己。 间接递归, 即P包含另一过程D, 而D又调用P。 4. 递归算法适用的一般场合为： 数据的定义形式按递归定义。 如裴波那契数列的定义：f(n)=f(n-1)+f(n-2)；f(0)=1; f(1)=2。 数据之间的关系(即数据结构)按递归定义。如树的遍历，图的搜索等。 问题解法按递归算法实现。例如回溯法等。 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
