汉诺塔（共5篇）
汉诺塔 篇1
摘要：分析汉诺塔递归算法的特点,由递归算法,结合二叉树的中序遍历算法,提出汉诺塔二叉树的概念及创建方法,并证明汉诺塔二叉树特点。由此进一步导出兼顾时间效率与空间效率的非递归算法。最后,提供实现算法的C语言程序。
关键词：汉诺塔,非递归算法,二叉树
1 引言
汉诺塔问题说的是，有三根柱子，不妨称为A、B、C三柱，A柱上有大小不同的n个盘子，最上面的盘子最小，最下面的盘子最大，不妨用1,2,3，……，n从上到下对n个盘子编号，每次从一个柱中移动一个盘到另一柱上，同时，做到大不压小，最后把n个盘移到C柱，要求写出移动过程。汉诺塔问题常用的解法是用递归算法，这是数据结构课中递归算法的经典例子。但不难发现，这种递归算法占用相当大栈空间，而且运行速度较慢，当盘数n较大时，常常会因栈溢出而无法运行。近几年，不少学者对汉诺塔问题的非递归算法作了大量的研究，有的利用两次移动n-1个盘的相似特点[1]，用递推的方法解决递归，但它仍需要大量的存储空间;有的非递归算法，存储空间虽然很小，但时间复杂度却增加了不少。有没有一种兼顾时间和空间的非递归算法呢?文中对此作了研究，并给出了一种算法。
2 汉诺塔递归算法
n个盘的汉诺塔问题可用如下递归方法实现。
当盘数为1时，将第n盘从A移到C即可。记作：nA-->C
当盘数不为1时，将n-1盘从A(利用C柱过渡)移到B，然后，将第n盘从A移动到C，最后，将n-1个盘从B(利用A柱过渡)移动到C。程序如下：
3 兼顾时间与空间的非递归算法
3.1 操作过程与二叉树的对应关系
从汉诺塔的递归算法中可知，当盘子的个数大于2时，汉诺塔的移动过程分为3步，第一步将n-1个盘从A移到B;第二步将第n盘从A移到C;第三步将n-1个盘从B移到C。如果把移动过程看作是二叉树的中序遍历[2]，则可用图1的二叉树与汉诺塔移动过程建立对应关系[3]。
按照同样的方法，处理图1中的左右子树，便得到图2形式的二叉树。
直到盘的个数为1时，不再有左右子树。
从建树的过程可知，同一层的结点，要么都没有子树(最后一层)，要么每个结点均有两个子树。因些，整个一棵树构成了n层的满二叉树。该树的中序遍历结果就是汉诺塔的移动过程的解。
为了更好地分析这个特殊的满二叉树，不妨对汉诺塔的操作进行编号，如表1。
如此，与汉诺塔相对应的二叉如图3。
这种二叉树，不妨称为汉诺塔二叉树，它的特点如下：
特点一：除最后一行结点没有孩子外，每个结点的左右孩子如图4所示。
对这个特点，用归纳法作出如下证明。
证明：(1)当盘数n等于1时，此时结点没有左右孩子。对应的二叉树只有一个结点，处于最后一行。因此，结论成立。
(2)当盘数n=2时，由于该二叉树是满二叉树，所以，由建树过程知，从A柱移到B柱，对应的二叉树只能是图a，从B柱移到C柱时，对应的二叉树为图b，同理，其它情况所对应的二叉树分别为：图c、图d、图e及图f。因此，当n=2时结点符合图4特点。
(3)设盘数n=k时，结点符合图4特点。
(4)当盘数n=k+1时，先考虑k+1个盘从A柱移到C时，根据建树的方法知，根结点编号3，其左子树为k个盘从A移到C，因此，左子树的根结点编号为0，同理，右子树的根结点编号为1，其汉诺塔二叉树如图5所示，根结点符合图4特点。
而图5中的左右子树是盘数为k的汉诺塔二叉树，由(3)的假设知，它们都符合图4特点。所以，图5所有结点符合图4特点。
类似地，k+1个盘从A移到B、从B到A、从B到C，从C到A，以及从C到B盘，同理可知结点符合图4特点。所以，盘数n=k+1时，结点符合图4特点。
由上可知，对任意个盘，除最后一行结点没有孩子外，每个结点的左右孩子如图4所示。
特点二：n个盘从A移到C的汉诺塔二叉树，从水平方向看，奇数层结点是3、4、5、3、4、5……循环;偶数层结点是0、1、2、0、1、2……循环。
证明：(1)根据特点一，如果上一层结点编号3、4、5、3，则下一层结点必然是0、1、2、0、1、2、0、1，所以，如果上一层结点编号3、4、5、3……循环，下一层必是0、1、2、0……循环。
(2)同理，如果上一层是0、1、2、0……循环，则下层是3、4、5、3……循环。
(3)n个盘从A移到C的汉诺塔二叉树，第一层结点编号为3，符合3、4、5、3……循环，所以由(1)知，第2层符合0、1、2、0……循环，再由(2)知，第3层符合3、4、5、3……循环，所以，对于有限盘数n，所有结点符合特点二。
3.2 非递归算法实现
因为汉诺塔树二叉树具有上述特点，所以，可以无须存储整个树而达到中序遍历的结果。下面给出它的中序遍历算法。将二叉树严格按照左子树在左，右子树在右画，中序遍历的结果应该是结点从左到右的一个排列。由于它是满二叉树，整个输出过程是，先输出最下层的一个结点，然后，输出上层中第一个左子树能包含该结点的结点，然后，再输出下层的下一个结点，再输出上层中第一个左子树能包含该结点的结点......如此，直到下层的结点全部输出完为止。
用一维数组level_position[]存储某一层已输出的结点序号。由于该二叉树是满二叉树，上层第i个结点的左孩子一定是下层的第2i-1个结点，右孩子一定是下层的第2i个结点。
这样，判断下层结点是否是上层结点的右孩子，只要判断上下层结点在其本层的编号是否构成2倍关系即可，整个算法程序实现如下：
4 结语
汉诺塔问题是经典的递归算法例子，语句虽少，但需要大量的栈空间，运行效率不高。文中介绍用非递归方法解决汉诺塔问题的算法，仅用少量的存储空间克服了递归算法的不足。兼顾了时间与空间的复杂度，提供了解决汉诺塔问题的新方法。
参考文献
[1]邱宁.汉诺塔问题的非递归算法分析[J].浙江树人大学学报,2005.
[2]王晓东.数据结构与算法[M].北京:高等教育出版社,2003.
[3]赵东跃.汉诺塔非递归算法研究[J].计算机应用与软件,2008.
汉诺塔 篇2
游戏辅导意向：
1、学习汉诺塔的玩法，愿意尝试独立完成游戏。
2、能运用恰当的.语言表达自己的想法，有一定的自我评价意识。
3、不怕挫折，勇于接受新挑战。
游戏准备
汉诺塔16个、红苹果和小红星若干，音乐等。
游戏规则及玩法
将汉诺塔的每一层由一根柱子移至另一根柱子上，自上而下由小到大进行排列，每次只能移动一个圆层，在移动过程中，大圆层不能放置在小圆层上。
行为观察
1、幼儿是否能按照游戏规则进行游戏。
2、幼儿能否完成三层或三层以上汉诺塔的游戏。
3、幼儿是否愿意接受更高难度的挑战。
4、幼儿能否积极的想办法解决游戏中的困难。有没有放弃游戏。
澄清讨论
这次你完成游戏了吗?你心里感觉怎样?你遇到困难了吗?你有没有放弃?为什么?你是怎么做的?还想继续挑战吗?你有信心完成吗?
外显行为评价要点
汉诺塔 篇3
汉诺塔是一个非常古老而有趣的数学问题, 它由3根柱子和一堆可摆放在不同柱子上的大小不一的盘子组成。最初所有盘子按照尺寸大小顺序地被放置在一根柱子上, 最大的盘子在最下面, 最小的盘子在最上面, 从而形成一个圆锥形状。游戏的结果是将所有的盘子移动到另一根柱子上, 移动过程中的规则是: (1) 每次只能移动一个盘子; (2) 每次将一根柱子上面的盘子移动到另一根柱子的上面, 即只有某根柱子最上面的盘子才可以移动; (3) 大盘子不能放置在小盘子之上[1]。自计算机出现以来, 汉诺塔问题出现了各种各样的解决方法。与此同时, 它在计算机专业课程教育中出现频率也是非常高的。例如, 数据结构中用它来描述递归思想;算法设计与分析中用它的不同解法来展现算法的多样性;高级语言程序设计中用来展示它的动态演示[2,3,4,5,6]。根据程序应用范围和服务对象的不同, 汉诺塔的动态演示也是各有特色的。例如以算法思想描述为主的讲解中, 汉诺塔的动态演示通过PPT动作设置即可完成盘子移动过程;高级语言的基本语法讲解中主要以文字描述各个盘子移动过程等等。本文讨论的是应用对象与组件技术来快速高效地实现经典汉诺塔问题的动态演示程序, 以面向对象思想解决该问题, 使用组件技术突出代码的重用性。
1对象设计
面向对象的软件技术以对象为核心, 用这种技术开发出的软件系统由对象组成。其软件开发过程从始至终都是围绕着建立问题领域的对象模型来进行;对问题领域进行自然的分解, 确定需要使用的对象和类, 建立适当的类等级, 在对象之间传递消息实现必要的联系, 从而按照人们习惯的思维方式建立起问题领域的模型。
在汉诺塔的动态显示中有1个基板、3个柱子、 不同尺寸的盘子。动态演示的效果要求能够根据求解结果, 完整而又灵活地单步体现这些盘子的先后移动过程。为简单起见, 这里假设盘子个数为3并只介绍重要数据结构和关键代码的细节实现。为了提高代码重用性, 适应不同的语言环境, 程序使用了Visual Studio.NET中的MFC Active X进行组件开发。
根据面向对象技术, 该汉诺塔演示程序需要构建2个类:CPeg柱子类和CBoard基板类。CPeg类和CBoard类的定义分别如下所示:
在CPeg类中, 数组disk[]表示当前在该柱子上的盘子符号, 下标越大则表示盘子越大, 例如disks=100表示该柱子上只有编号为1的盘子。变量topx和topy表示柱子顶部坐标;pegheight表示柱子高度;topdiskx和topdisky表示当前该柱子上最顶端盘子的中心坐标;diskheight表示盘子高度;为美观起见, 盘子之间设置了一小段间隔, 使用diskin- terval变量表示。
在CBoard类中, 变量maxdiskscount表示盘子最大个数, 这里为3;boardx1和boardy1表示整个背景框的左上角坐标;boardx2和boardy2表示背景框的右下角坐标;baselength表示放置柱子的底座长度;baseinterval表示底座之间的间隔;maxdisklength表示最大盘子的长度;diskdesc表示盘子长度的递减量;basex[]和basey[]表示底盘左边点的x和y坐标。
CPeg类和CBoard类中各个变量的具体表示如图一所示。
CPeg各个数据成员的初始化在其构造函数中进行。由于每根柱子上的盘子都会时增时减, 因此CPeg类有removedisk和adddisk两个方法, 其实现代码也非常简单, 如下所示:
CBoard类的构造函数除了对各个变量初始化, 重点就在于如何对图形的各个坐标进行初始化计算, 其主要代码如下所示:
CBoard类的move方法则是充分利用了CPeg类的2个方法, 其定义如下:
参数from和to表示了柱子, diskno表示当前移动的盘子编号, 在这里是数组下标。从代码组成中可以看到, 不论是CPeg类还是CBoard类, 虽然由于布局灵活性需要的数据成员较多, 但是方法及其简单。至此, 本汉诺塔动态演示所需要的类就基本定义完成了。
2图形绘制
在MFC应用程序中, 一般情况下, 很多绘图操作都是在视类的On Draw () 成员函数中进行的。On- Draw () 函数参数中自动有1个CDC的指针p DC, 利用p DC调用CDC类的成员函数完成绘图操作。 另外, 当用户需要立即绘制图像时, 可以通过调用更新窗口函数Invalidate () 使Windows送出WM_PAINT消息, 自动调用On Draw () 函数来重绘图形。
在本文的动态演示程序中, 图形的绘制代码就是放置在On Draw () 函数中。根据汉诺塔动态演示的需求可以发现, 需要使用到的图形为直线和矩形;由于CBoard类的构造函数已经将主要坐标和变量值确定好, 那么绘制过程就以此为基础, 进行适当的加减运算, 完成相应的绘制过程。关键代码如下:
从代码中可以看出, 由于柱子和底座个数都为3, 因此可使用循环绘制出每个底座、每根柱子以及所拥有的盘子。每根柱子上盘子的有无、尺寸大小、 坐标位置都在内层循环中判断、计算和绘制。
3组件实现
组件是具有特定功能的软件模型, 一种优秀的软件重用技术, 与开发工具语言无关。本演示系统采用MFC Active X技术, 应用在Visual Basic.Net环境下。在完成对象构建和绘制图形后, 现在需要设置相应的方法, 因此在组件实现过程中增加1个对外加以调用的movedisk方法, 代码如下:
编译成功之后, 在工具下的ACTIVEX测试容器中, 选择Hanoi Activex Control, 就可以查看基本效果。在VB.Net运行环境中, 通过工具箱中的COM组件来添加刚刚生成好的汉诺塔演示组件, 将其拖到Form上, 其组件调用代码如下:
由于对象构建和组件方法设计中使用的多是整形数据, 因此需要进行类型转化, 简化的效果图如图二所示。
4结束语
本文中的汉诺塔动态演示系统运行效果良好, 完成步骤清晰有序, 代码简单明了, 有利于学生对于组件级编程的更好理解与掌握。该演示系统可以通过简单的调整来完成更加复杂的应用, 例如修改对象方法、设置组件属性和事件、将纯演示功能转换为移动盘子的小游戏。计算机课程的学习中依靠这些小实例进行讲解, 不仅增加学生的学习乐趣, 更能提高授课的效果。
参考文献
[1] (美) Peter Maurer, 著.施诺, 译.组件级编程[M].北京:清华大学出版社, 2003.
[2]卫洪春.图形环境下的汉诺塔演示[J].电子设计工程, 2014, 22 (15) :8-10, 14.
[3]付明柏.基于Turbo C的“汉诺塔”问题CAI课件[J].昭通师范高等专科学校学报, 2010, 21 (05) :42-45.
[4]徐晓琴, 徐勇.用VB编写Hanoi塔问题动态演示程序[J].电脑编程与技巧与维护, 2008, (16) :12-14.
[5]彭伟.汉诺塔问题的非递归算法那设计及可视化实现[J].武汉船舶职业技术学院学报, 2011, (06) :55-59, 72.
[6]李健.汉诺塔算法演示系统的设计与实现[J].现代计算机, 2011, (10) :76-80.
[7]朱从旭.Visual Basic程序设计综合教程[M].北京:清华大学出版社, 2005.
汉诺塔 篇4
问题提出：
有三个塔(分别为A号，B号和C号)。开始时，有n个圆形盘以从下到上、从大到小的次序叠置在A塔上。现要将A塔上的所有圆形盘，借助B塔，全部移动到C塔上，且仍按照原来的次序叠置。移动的规则如下：这些圆形盘只能在3个塔间进行移动，一次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比它小的盘子的上面。要求如下：从键盘输入初始圆形盘子个数n，用C语言实现n个盘子最佳移动的全过程。
2 算法分析
此题的目的是设计一个盘子移动的方案，使得A号塔上的所有盘子借助于B号塔按照原来的次序移动到C号塔上，并且，要给出完整的最佳的盘子移动的方案。
从实际的、具体的盘子的移动过程来分析，找出问题内在的规律。经分析，无论盘子的个数有多少，是1、2、3……或n个，也不管怎么去移动盘子(当然是按规则来移动)，但在移动的过程中，将始终会出现这样的状态情况：(n-1)个盘子将会以从下到上、从大到小的次序叠置在B塔上，这时，A塔上第n个盘子就能被轻而易举地叠放到C塔上;接着，再把B塔上的共(n-1)个盘子移动到C塔上，问题好像已经解决。
但，B塔上(n-1)个盘子怎么移动到C塔上呢芽这是要解决的第二个问题。同样，不管我们怎么移动，也将会出现这样的状态情况：(n-2)个盘子将会以从上到下、从大到小的次序叠置在A塔上，这时，B塔上第(n-1)个盘子就能被轻而易举放到C塔上;接着，把A塔上的共(n-2)个盘子移动到C塔上。
这样，不断深入，不断细小化，最终，将到达仅有一个盘的情形，这时，递归也就终止了，问题也得到了解决。通过以上分析，这里有很明显的递归关系。
由此，想到了采用递归算法来解决该问题，因为递归算法有这样的特征描述：为了求解出规模为N的问题的解，先设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的方法分解，分解成规模更小的问题，并能从这些更小的问题的解构造出规模稍大问题的解。特别地是，当规模N=1时，能直接得到解。
现在，严格按照递归算法来解决问题。先定义递归方法han(int n,char one,char two,char three)，按如下步骤进行解题(设初始盘子个数为N)：若A塔上仅仅只有一个盘子(N=1)，则直接从A移动到C，问题完全解决。若A塔上有一个以上的盘子(N>1)，则需要考虑以下三个步骤。
第一步：把(N-1)个盘子从A塔经过移动，叠放到B塔上。在不违反规则情况下，所有(N-1)个盘子不能作为一个整体一起移动，而是要符合要求地从一个塔移到另一个塔上。用han(int n-1,char one,char two,char three)调用递归方法，注意：这里是借助于C塔，将(N-1)个盘子从A塔移动到B塔，A是源塔，B是目标塔。
第二步：将剩下的第N个盘子(也就是最底下的一个)直接从A塔叠放到空着的C塔上。
第三步：用第一步的方法，再次将B塔上的所有盘子叠放到C塔上。同样，这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。用han(int n-1,char two,char one,char three)调用递归方法，注意：这里是借助于A塔，将(N-1)个盘子从B塔移动到C塔，B是源塔，C是目标塔。
这个算法达到了预期的目标，即在C塔上按正确的次序叠放了所有的圆形盘子。有了前面问题算法分析的基础，继而，就可以用C语言来实现算法。
3 算法实现
依据上述分析可知，汉诺塔问题符合实现递归的条件，而C语言又可解决递归问题，据此，用C语言来实现对汉诺塔问题的求解，用han函数来实现原问题转化为新问题的操作(问题分析的一、三步)，用move函数实现递归边界的操作(问题分析的第二步)，用main主函数提出问题，确定需移动盘子的数目，现编写程序如下：
4 结束语
其实，递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较为复杂的问题(如规模为N)的求解推到比原问题简单一些的问题(规模小于N)的求解。例如上面分析过程中，为求解han(int n,char one,char two,char three)，推到计算han(int n-1,char two,char one,char three)。
在回归阶段，当获得最简单情况的解后，逐级返回，依次获得稍复杂问题的解。在这里的“汉诺塔”问题中，有特别的地方，回归的过程当中，还要涉及到递推。另外，在编写递归方法时要注意的是：每次调用递归方法，方法中的参数只是局限于当前调用层的，当递推进入“简单问题”层时，原来层次上的参数便被隐藏起来。在一系列“简单问题”层，都各有自己的参数。
最后，通过经典“汉诺塔”问题移动过程的分析、解决以及最后C语言编程的实现，从而掌握了解决此类问题的方法，对递归算法也有了更加深刻的理解。
参考文献
[1]王春森.程序员教程.北京:清华大学出版社,2001-05.
汉诺塔 篇5
1 汉诺塔问题分析
假设要移动的汉诺塔共有N个金片,对金片从小到大依次编号,最小的金片为1号,次之为2号,依次类推,则最大的金片的编号为N。
一种可能:假设A塔只有一个金片,则只需将它从A塔上移到C塔上即可;
另一种可能:如果汉诺塔的层数为N(N>1),将分位两部:圆盘最下面的N和上面的N-1个。汉诺塔可以按下面的方式进行操作:
(1)将A塔上面的N-1个金片,借助C塔,移到B塔上;
(2)将A塔上剩余的N号金片移到C塔上;
(3)将B塔上的N-1个金片,借助A塔,移到C塔上[1]
汉诺塔的本质其实就是一个递归算法的问题,不妨打个简单的比方:
方丈让个老和尚要把A塔上的n圆盘搬到C塔上,老和尚叫个小和尚帮他把除最下面的n-1个圆盘搬到B塔上,然后他只需搬最大的一个圆盘到C塔上,小和尚再B塔上的所有圆盘搬到C塔就可以。
小和尚呢?他又叫了个小小和尚帮他把n-2个圆盘搬到面的B塔上,自己把第二大的盘子移到C塔上,再叫小小和尚把n-2个盘子搬到C塔上就可以。依次类推,直到有个小和尚将最小一个盘子直接搬到C塔上。
2 基于Prolog语言的解决方案
Prolog(Programming in Logic)是一种高级人工智能语言。它建立在逻辑学的理论基础上,最初应用于自然语言领域,现广泛应用于专家系统、自然语言理解等人工智能领域。
作为高级人工智能语言的Prolog语言,能够用来编写程序解决非数值计算、知识处理、推理、规划、决策等具有智能的各种复杂问题,它具有如下特点:
(1)具有处理符号的能力;
(2)适合于结构化程序的设计且容易编程;
(3)能够轻松实现递归和回溯的功能;
(4)丰富的人机交互功能。[2]
正因为语言具有这些优点,它才更加适合通过推理解决汉诺塔问题。
3.1 Prolog语言实现
3.1.1 Prolog基本语句结构
Prolog语言是人工智能开发常用的一种语言,其核心部分由三种基本语句组成,即事实、规则和目标,且都用谓词表示,文法简洁,清晰易懂。
3.1.2 定义汉诺塔问题状态的描述形式
事实:假设3个塔1、2、3和两个盘A、B(A盘小于B盘)
规则:每次可移动一个盘子上方是空顶的盘子,不允许大盘放在小盘之上。
目标:A,B盘按大小一次放在塔3上
定义用Z=(ZA,ZB)表示问题的状态,ZA表示盘子A所在的塔号,ZB表示盘子B所在的塔号。[3]
3.1.3 用定义的状态描述形式表示盘子所在塔的位置
盘子和塔的状态描述如下:
3.1.4 定义一组运算符
定义运算符Y(a,b)表示把Y盘子从a塔搬到b塔的操作,定义后共有如下12个运算符:
A(1,2);A(1,3);A(2,1);A(2,3);A(3,1);A(3,2);
B(1,2);B(1,3);B(2,1);B(2,3);B(3,1);B(3,2);
从这个问题可以知道盘子移动起始运算符是A(1,2),终止于A(3,2),那么最简洁的运算符就是A(1,2),B(1,3),A(2,3)。
3.2 汉诺塔的编程实现
盘子为3个时,演示效果如图2:
4 结束语
本文形象地介绍了使用高级人工智能语言Prolog解决汉诺塔问题的全过程,整个过程相对于其他语言更加容易理解而且编程语句简练容易掌握。不但对理解递归算法有一定的帮助,更主要的是它给我们提出了一个新的思路——使用人工智能语言处理推理性问题。
摘要：汉诺塔问题是经典递归程序设计案例,一直以来,大家多利用面向对象、过程等编程语言来实现。当今人工智能发展迅速,能否利用人工智能语言解决汉诺塔问题成为一个新的研究领。此次研究利用结构式分析方法,借助人工智能语言推理强的特征,解决了汉诺塔问题。
关键词：汉诺塔,人工智能语言,Programming in Logic,递归算法
参考文献
[1]严蔚敏,吴伟民.数据结构.北京:清华大学出版社.2006
[2]张海藩.软件工程导论1.M2.北京:清华大学出版社.1998
[3]王晓东.数据结构与算法.北京:高等教育出版社.2003