汉诺塔探趣

“汉诺塔”问题探趣

洞头县实验小学 502班叶钫舟

指导老师洞头县实验小学陈素萍

一、问题的提出：

一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

尽管这个传说并不可信，但现在却成就了一种益智玩具━━“汉诺塔”(如图)的诞生。对下面这个8层汉诺塔，如何按以上要求将所有的圆盘从最左边的柱子上移到最右边的柱子上来呢？并如何保证移动的步子最少呢？

对这个富有挑战性的游戏，我非常有兴趣，于是我开始了研究！

二、研究过程：

1、简化器材，方便携带，随时演练，不断研究

“汉诺塔”游戏器材，体积较大，质量也大，不方便随身携带，因而也不能让我随时随地进行演练。

考虑到它最关键的是体现由小到大的一种排列，我用扑克牌同色的1（A），2，3，4，5，6，7，8来代替这个“汉诺塔”，平时演练，只要假想桌子上有左0、中1、右2三个档位即可，将这8张扑克牌从上到下按由小到大的顺序叠放在一起，放置在左边档位0处，然后将按游戏规则将它们依次全部移到最右边档位2处即可。

我把这种用扑克牌玩“汉诺塔”游戏称为“汉诺牌”，这样就很方便了！有时忘记了带扑克牌，我就用笔在纸上写下1～8这张8张“牌”，就可以玩了！

2、简化问题，循序渐进，对比分析，寻找规律

刚开始玩这个游戏，还真有些难，走了几步后，就乱了，因为还摸不清规律。于是我想，能不能先研究一下简单一点的，就是减少层数，当然最少就是“一层汉诺”啦，这个太简单，一步就完成了！哈哈！可是没有发现什么规律呀！所以研究“二层汉诺塔”，经过几步推敲，也轻松搞定，只要3步，没有什么难度呀！那么“三层汉诺”呢？这个就有一点点难度了，但我对此进行稍许研究之后，也轻松完成！

“三层汉诺”要想从最左边移到最右边，而且不走多余步骤，只要7步就能完成，不过我还是花了五分钟时间才完全弄清楚的，并且还摸出了一点点门道，就是第一步应当把最小的移到最右边档位上才行，如果第一步错了，就会产生许多多余的步骤。

为了检验自己的走法的正确性，我立即对“四层汉诺塔”进行了研究。这个有些难，就要花一些时间了，我试着将第一小块移到最右边档位上，结果走了几步后，发现不对头，于是从新来过，结果发现，必须将第一小块移到中间档位上，才能顺利完成。对此，我又反复演练了好几遍，直到完全熟练。这个要走15步！

重新审视这几个简单的“汉诺塔”，我把它们的走法做了一个比较：

几种简单汉诺塔的走法比较

从中，我意识到，这里边一定有规律：

（1）若层数为单数，第一步应当把1（A）移到右边档位2上；若层数为双数，第一步应当把1（A）移到中间档位1上，然而再继续进行！

（2）从完成的步子数上看，从1层增至2层，增加的步数为2，从2层增至3层，增加的步数为4（2×2），从3层增至4层，增加的步数为8（4×2）！而总步数应当为（2N－1）步。

对此，我感到很高兴！我把自己的研究结果告诉了爸爸，他要求我对“五层汉诺”先根据自己研究的“规律”进行猜测，然后进行验证，看看“规律”对不对！

从表格的规律中，我猜测：“五层汉诺”的第一步应当把1（A）移到右边档位2上，并且完成的总步数应当是15＋16 = 31 = 24－1步！

然后就是进行演练验证了！

经过长达10分钟的研究，我终于熟练完成了“五层汉诺”的操作。果然与我的猜想相一致，这让我十分兴奋！

我立即跑去告诉了爸爸，爸爸对我的研究表示了肯定，并让我对“八层汉诺塔”

进行操作，看看能不能顺利完成。

我回到房间，立即着手研究“八层汉诺塔”。根据“规律”，第一步应当把1（A）移到中间档位1上，完成的总步数应当为28-1=255步，这个步数太多了，一下子无法完成。虽然我知道了第一步，但中间如果有一步走错，难免要从头再来，会浪费太多的时间，这可不比低层数的“汉诺塔”，因为低层数的总步数不多，是不会浪费太多的时间。

怎么办呢？我又去与爸爸研讨。经过他的指点，我发现只有对第二步及后边的步子都要进行认真的剖析研究，才能找到“后续步骤的行走规律”，从而保证正确完成“八层汉诺塔”的操作！

3、熟练操作，归纳心得，总结要领，修正“规律”

由于对复杂问题研究有困难，爸爸让我先对较低层级

又有多步的“三层汉诺塔”进行反复研究（如右图：“三

层汉诺塔”分步图），并对“后续步骤的行走规律”进

行剖析探讨！结果如下：

第(1)步，单数层，块1首先到2柱；

原因：“三层汉诺塔”，要移到右边柱位上，应当先让

块1和块2都移到中柱1后，才能移动块3（如右图C），

这就要求块2向中柱走时，块1不在中柱1，只能在右柱

2上（如右图B）。所以，第(1)步，块1“首先到右柱”（如

右图A）。由此，我发现，“块3要到柱2”，必须先“块

2到柱1”，而这又得先“块1到柱2”。

清楚了这一点，对“五层汉诺塔”也可类似倒推：

其他“奇数层汉诺塔”

均可类似分析出第一步是同样的走法！

（如果是双数层：块1先走中间柱；）

第(2)步，块2走到另一柱（中间柱）；

这个是必然的，只有这个地方可以走！

第(3)步，块1跟到2块处（跟到块2上来）；

只有这样，块3才能到2柱来！

对应“三层汉诺塔”分步图的图C，实质上是完成了将一个“二层汉诺塔”从左柱移到中间柱的过程之后的图样！

第(4)步，块3走到右边柱；

第(5)步及其后，就是将中间柱上的“二层汉诺塔”走到右边柱块3 上边来；

通过对“三层汉诺塔”分步剖析之后，我对每一步都有了一定的理解。这种理解

对“四层汉诺塔”的操作应当也能运用！果然，我在操练“四层汉诺塔”时，进一步领会到它与“三层汉诺塔”有许多共同之处：

(1)要将一个N层汉诺塔移到右边柱上，首先应当将（N－1）层汉诺塔移到中间柱上来；而要将（N－1）层的汉诺塔移到中间柱上来，就得先将（N－2）层汉诺塔移到右边柱上，这又得先把（N－3）层汉诺塔移到中间柱上，……最终就是首先要把第一层移到某柱上！

(2)每当一较大的块正确移到某个柱上，其他比它小的块都要依次转移到这个较大的块的上边来！

(3)三根柱子在不同阶段，一为出发地，一为目的地，还有一为中间过渡用！

(4)多层汉诺塔的总步数，为一个低一层汉诺塔走两遍，再加一步（最大块转移到目的地的这一步）！

(5)一个多层汉诺塔，包含着一个个低层的汉诺塔，规律大致相同！

这样，我便初步领会了多级汉诺塔的操作要领，于是我便去解这个有255步的“八层汉诺塔”，果然，第一遍虽然比较慢，只花了12分钟就完成了。为了表明我的“速度”，我让爸爸为我计时，第二遍，我只用了8分25秒！哈哈，有了很大的进步！经过多次演练，我的最快成绩（当然是用扑克牌演练的）是：5分22秒！再过一段时间，相信会更加快的！

4、编制口诀，便于操作

单双层数分开走，对清层数再动手；一牌走，二牌走，一牌跟着二牌走；

三牌走，另一头，一二跟着三牌走；小牌走，大牌走，小牌跟着大牌走。

第一、二句是讲如何走第一步，第三四句是完成二级汉诺塔的转移，第五六句是完成三层汉诺塔的转移，第七八句是以后更多层的继续！只要一张大牌移动到一个新的位置，比它小的牌就要依次跟到它的上边来！如此进行下去，最终就会正确地完成！

5、继续探究，创新玩法

几天的演练，使我对“汉诺塔”游戏有了进一步的了解！我也常与爸爸进行比赛，看谁更快，结果不相上下！有时总因为想快而走乱了，正应了那“欲速反不达”之言！不过，在失败之余，我

和爸爸却发现了一种创新的

玩法，就是先将几张汉诺牌

按自上而下由小到大分成两

份或三份，随意放在三个

“柱”位上（如图），做为开

始状态，然后要求按照汉诺

塔的规则，将它们全部移到

某一根“柱”位上！这个就

更有点难度了！

经过一阵子研究，我们也会玩了，而且是步步正确，没有任何多余的步骤！

6、推广相关研究心得

希望能够组织一些小型的比赛，并由老师开展一些讲座让有兴趣的同学学习这个游戏的玩法，最好象玩魔方一样！我也可以为同学们进行一些演示和示范！

三、研究结论

一个“n层汉诺塔”步步正确，至少要2n－1步才能完成。为保证步步正确，就必须理解“低层数汉诺塔”的每一步走的原因，并掌握我们编制的口诀，理解其中的内容与含义！

“汉诺塔”游戏是个应用逻辑分析的益智游戏，对培养学生的抽象思维能力有一定的作用，如果能对每一步的道理加以理解，则可以由小及大，由少及多，触类旁通，它与我所玩过的“九连环”有异曲同工之处，甚至步数的规律也接近相同！四、研究收获

通过对“汉诺塔”游戏解法的详细研究，我不仅获得了游戏成功的快乐，也全面掌握了“汉诺塔”步步正确的最简操作方法，并从中深刻体会到数学的“美”！

在研究中，我深切地体会到：做一个小研究真的也很不容易，但只要对所关心的问题有浓厚的兴趣，就会有很大的动力，就可以进行较为深入的研究，有时在研究取得了一点小小的进展和收获，自己都会兴奋不已，因为这是自己的研究成果，成功总会让我感到无比喜悦。

研究问题的过程中，我体会到应当把复杂问题化为简单问题进行研究，并从多个递进关系的例子中，寻找规律，进行猜测，并设法进行验证和推广，这可是对各种问题进行研究的主要步骤，这对我今后再做其他数学问题的研究很有参考价值！

通过这次数学问题的研究，也大大地提高了我的独立思考和实践操作等能力，虽然网络上应当也有其他人的研究，但我还是独立地进行了详细研究，因而对这个游戏解法的认识非常深刻，但如果只是简单去学习一下他人的研究成果，我们的体会常常是不深刻的！

另外，我还意识到，面对困难时，要适当地去寻求帮助，获得一些必要的忠告，这对我们的研究很有帮助。

当然，我对最终的成果感到自豪！

二〇一三年一月七日

汉诺塔问题的三种实现

// test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的 // //递归实现 /*#include "stdafx.h" #include using namespace std; int count=0;//记录移动到了多少步 void Move(int n,char From,char To); void Hannoi(int n,char From, char Pass ,char To); //把圆盘从From，经过pass,移动到To int main() { int n_count=0; cout<<"请输入圆盘个数:"; cin>>n_count; Hannoi(n_count,'A','B','C'); } void Move(int n,char From,char To)

{ count++; cout<<"第"<

/*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A B C； 若n为奇数，按顺时针方向依次摆放A C B。 （）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A，则把它移动到B；若圆盘在柱子B，则把它移动到C；若圆盘在柱子C，则把它移动到A。 （）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*/ /*#include "stdafx.h" #include #include

《递归算法与递归程序》教学设计

递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习

智慧汉诺塔活动方案

神奇汉诺塔游戏活动方案 汉诺塔问题在教学届有很高的研究价值，至今还在被一些数学家们研究，也是我们所喜欢的一种益智游戏。它可以帮助开发智力，激发我们的思维，让小学生接触这款益智游戏，利用一次次不断的探索和尝试，可以激发他们的兴趣，积极应对困难，获得成功体验，锻炼他们的思维，同时也培养学生主动探究，不服输的精神。把组成“金塔”的圆片按照下大上小依次放在中央的柱子上，每次只能移动一个圆片，在移动的过程中，大圆不能压在小圆上面，每次移动的圆片只能放在左中右的位子，将整座“金塔”移到另外一根柱子上即告胜利。 和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨?班?达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。 那么，宰相要求得到的麦粒到底有多少呢？总数为 1+2+2^2 + … +2^63=2^64-1 等于移完汉诺塔的步骤数——共3853步。我们已经知道这个数字有多么大了。人们估计，全世界两千年也难以生产这么多麦子！ 其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1 活动目的： 1、让学生在活动过程中，根据解决问题的需要，经过自己的探索，体验化繁为简找规律这一解决数学问题的基本策略。 2、经历收集有用的信息、进行归纳、类比与猜测、再验证猜测，这一系列数学思维过程，发展学生的归纳推理能力。 3、能用有条理的、清晰的语言阐述自己的想法。 4、在活动中，学习与他人合作，懂得谦让，能互相帮助。 5、在老师、家长的鼓励与引导下，能积极地应对活动中遇到的困难，在活动中获得成功体验。 活动时间：2014年12月 活动口号：放松心情，你行我也行！ 活动地点：怀德教育集团六（3）、六（5）班。 活动开展安排：

汉诺塔课程设计

汉诺塔课程设计 一、教学内容： 1、了解汉诺塔的历史。 2、讲解汉诺塔的游戏规则。 二、课程设计目的： 1、让伙伴们了解汉诺塔的历史，勾起孩子们的学习兴趣，让伙伴们更加热爱数学。 2、在掌握汉诺塔玩法的基础上，锻炼伙伴们的观察力，变通里，和右脑开发。 3、增强伙伴们的空间想象能力和动手能力。 4、让伙伴们体会到数学的神奇，从而对数学产生更加浓厚的兴趣。 三、培养技能：观察力、想象力、变通里、右脑开发。 四、所需工具：汉诺塔、记号笔。 五、教学流程概述： 第一节课：1、讲一个关于汉诺塔的故事。2、带领伙伴们一起观察和了解汉诺塔的游戏规则。（以三盘为例说明）（30分钟） 第二节课：汉诺塔4盘的移法。（30分钟） 第三节课：汉诺塔5盘的移法。（30分钟） 第四节课: 汉诺塔月底考核。（30分钟） 六、教学流程详细解读： 第一节课：让伙伴们了解汉诺塔的历史，勾起孩子们的学习 兴趣，让伙伴们更加热爱数学。 1、讲关于汉诺塔的故事： 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄 铜板上插着三根宝石针。印度教的主神梵天在创造世界的时 候，在其中一根针上从下到上地穿好了由大到小的64片金 片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在 按照下面的法则移动这些金片：一次只移动一片，不管在哪 根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移

、告诉伙伴们游戏规则： 以三个环为例说明： （一）先让伙伴们自己观察有几个柱子，有几个盘，并且盘是怎么排列的？ 答：有三根相邻的柱子，第一根柱子上从下到上放着3个不同大小的圆盘，并且顺序是由大到小依次叠放。 （二）分别为这3个相邻的柱子编号A柱、B柱、C柱；在为这3个圆盘编号盘1、盘2、盘3。 让伙伴们自己动脑想想：如何要把A柱上的3个盘子一个一个移动到C柱上，并且每次移动同一根柱子上都必须保持大点的盘子在下，小点的盘子在上。最后也要使移动到C 柱的圆盘从下到上按照盘3,2,1金字塔的形状排列。 （三）带领伙伴们一起动手操作： （1）、盘1移动到C柱。 （2）、盘2移动到B柱。 （3）、盘1在移动到B柱上，这时盘1在盘2上。 （4）、盘3移动到C柱上。 （5）、再将盘1移动到A柱，这时B柱就只剩盘2。 （6）、将盘2移动到C柱，在盘3上边。 （7）、再将盘1移动到C柱，这时就成功了。 （四）鼓励伙伴们再来一次，按照刚才的移动方法 将C柱的圆盘移动到A柱。 （五）等所有伙伴都移动成功都移动成功后，引导伙伴们仔细思考，看看各位伙伴在移动的过程中有发现什么规律和技巧没有？ 带领伙伴再来熟悉一遍： 第一步：盘1移动到C柱；第二步：盘2移动到B柱；．．．．．．第四步：盘3移动到C柱上．．．．．．

汉诺塔非递归算法C语言实现

汉诺塔非递归算法C语言实现 #include #include #define CSZL 10 #define FPZL 10 typedef struct hanoi { int n; char x,y,z; }hanoi; typedef struct Stack { hanoi *base,*top; int stacksize; }Stack; int InitStack(Stack *S) { S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base; S->stacksize=CSZL; return 1; } int PushStack(Stack *S,int n,char x,char y,char z) { if(S->top-S->base==S->stacksize) { S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); if(!S->base) return 0; S->top=S->base+S->stacksize; S->stacksize+=FPZL; } S->top->n=n; S->top->x=x; S->top->y=y; S->top->z=z; S->top++; return 1; } int PopStack(Stack *S,int *n,char *x,char *y,char *z) { if(S->top==S->base)

汉诺塔问题

实验二知识表示方法 梵塔问题实验 1．实验目的 （1）了解知识表示相关技术； （2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2个实验内容可以选择1个实现） （1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法； （2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求 （1）简述实验原理及方法，并请给出程序设计流程图。 我们可以这样分析： （1）第一个和尚命令第二个和尚将63个盘子从A座移动到B座； （2）自己将底下最大的盘子从A移动到C； （3）再命令第二个和尚将63个盘子从B座移动到C；（4）第二个和尚命令第三个和尚重复（1）（2）（3）；以此类推便可以实现。这明显是个递归的算法科技解决的问

题。 （2）源程序清单： #include #include using namespace std; void main() { void hanoi(int n,char x,char y,char z);

int n; printf("input the number of diskes\n"); scanf("%d",&n); hanoi(n,'A','B','C'); } void hanoi(int n,char p1,char p2,char p3) { if(1==n) cout<<"盘子从"<

汉诺塔问题与递归思想教学设计

一、教学思想（包括教学背景、教学目标） 1、教学背景 本课程“递归算法”，属于《数据结构与算法》课程中“栈和队列”章节的重点和难点。数据结构与算法已经广泛应用于各行各业的数据存储和信息处理中，与人们的社会生活密不可分。该课程是计算机类相关专业核心骨干课程，处于计算机学科的核心地位，具有承上启下的作用。不仅成为全国高校计算机类硕士研究生入学的统考科目，还是各企业招聘信息类员工入职笔试的必考科目。数据结构与算法课程面向计算机科学与技术、软件工程等计算机类学生，属于专业基础课。 2、教学大纲 通过本课程的学习，主要培养学生以下几个方面的能力： 1）理解递归的算法； 2）掌握递归算法的实现要素； 3）掌握数值与非数值型递归的实现方法。 根据学生在学习基础和能力方面的差异性，将整个课程教学目标分成三个水平：合格水平（符合课标的最低要求），中等以上水平（符合课标的基本要求），优秀水平（符合或超出课标提出的最高要求）。具体如下表：

二、课程设计思路（包括教学方法、手段） “递归算法”课程以故事引入、案例驱动法、示范模仿、启发式等多元化教学方法，设计课程内容。具体的课堂内容如下所示：

1 1 2 3 3 7 4 15 5 31 count = 2n-1 思考：若移动速度为1个/秒，则需要 (264-1)/365/24/3600 >= 5849亿年。 四、总结和思考 总结： 对于阶乘这类数值型问题，可以表达成数学公式，然后从相应的公式入手推导，解决这类问题的递归定义，同时确定这个问题的边界条件，找到结束递归的条件。 对于汉诺塔这类非数值型问题，虽然很难找到数学公式表达，但可将问题进行分解，问题规模逐渐缩小，直至最小规模有直接解。 思考： 数值型问题：斐波那契数列的递归设计。 非数值型问题：八皇后问题的递归设计。阐述总结知识拓展 三、教学特色（总结教学特色和效果） 递归算法课程主要讨论递归设计的思想和实现。从阶乘实例入手，由浅入深，层层深入介绍了递归的设计要点和算法的实现。从汉诺塔问题，通过“边提问，边思考”的方式逐层深入地给出算法的分析和设计过程。通过故事引入、案例导入、实例演示、PPT展示、实现效果等“多元化教学方式”，努力扩展课堂教学主战场。加上逐步引导、问题驱动，启发学生对算法的理解，并用实例演示展示算法的分析过程，在编译环境下实现该算法，加深对算法实现过程的认识。 1、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用，并通过“世界末日问题” 故事引入非数值型问题的递归分析，激发学习积极性，挖掘学生潜能。

数据结构实验报告汉诺塔

实验报告书 课程名：数据结构 题目：汉诺塔 班级： 学号： 姓名： 评语： 成绩：指导教师： 批阅时间：年月日

一、目的与要求 1）掌握栈与队列的数据类型描述及特点； 2）熟练掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 5）认真书写实验报告,并按时提交。 二、实验内容或题目 汉诺塔问题。程序结果：给出程序执行过程中栈的变化过程与圆盘的搬动状态。 三、实验步骤与源程序 源程序： / *编译环境Visual C++6.0 */ #include "stdafx.h" #include #include void move(int h,char c,char f) { printf("%d:%c--->%c\n",h,c,f); } void hanoi(int n,char x,char y,char z) { if(n==1) move(1,x,z); else { hanoi(n-1,x,z,y); move(n,x,z); hanoi(n-1,y,x,z); } } void main(void) { int flag; do { printf(" 汉诺塔问题\n\n"); printf("[1] 开始\n"); printf("[2] 退出\n"); printf("1--2请选择:"); scanf("%d",&flag); printf("\n"); switch(flag) { case 1:

汉诺塔程序实验报告

实验题目： Hanoi 塔问题 一、问题描述： 假设有三个分别命名为 A , B 和C 的塔座，在塔座 B 上插有n 个直径大小各不相同、从小到 大编号为1, 2,…，n 的圆盘。现要求将塔座 B 上的n 个圆盘移至塔座 A 上并仍按同样顺序 叠排，圆盘移动时必须遵守以下规则： (1 )每次只能移动一个圆盘； (2)圆盘可以插在 A , B 和C 中任一塔上； ( 3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 要求： 用程序模拟上述问题解决办法,并输出移动的总次数, 圆盘的个数从键盘输入； 并想 办法计算出程序运行的时间。 二、 算法思路： 1 、建立数学模型： 这个问题可用递归法解决,并用数学归纳法又个别得出普遍解法： 假设塔座B 上有3个圆盘移动到塔座 A 上： (1) "将塔座B 上2个圆盘借助塔座 A 移动到塔座C 上; (2) "将塔座B 上1个圆盘移动到塔座 A 上; (3) "将塔座C 上2个圆盘借助塔座 B 移动到塔座A 上。 其中第 2步可以直接实现。第 1步又可用递归方法分解为： 1.1"将塔座B 上1个圆盘从塔座 1.2"将塔座B 上1个圆盘从塔座 1.3"将塔座A 上1个圆盘从塔座 第 3 步可以分解为： 3.1将塔座C 上1个圆盘从塔座 3.2将塔座C 上1个圆盘从塔座 3.3将塔座B 上1个圆盘从塔座 综上所述：可得到移动 3 个圆盘的步骤为 B->A,B->C, A->C, B->A, C->B, C->A, B->A, 2、算法设计： 将n 个圆盘由B 依次移到A , C 作为辅助塔座。当 n=1时，可以直接完成。否则，将塔 座B 顶上的n-1个圆盘借助塔座 A 移动到塔座C 上；然后将圆盘B 上第n 个圆盘移到塔 座A 上；最后将塔座 C 上的n-1个圆盘移到塔座 A 上，并用塔座B 作为辅助塔座。 三、原程序 #include #include #include int times = 0; void move(char a, char b) { printf("%c > %c \n", a,b); } void hno(int n,char a , char b, char c) { if (n==1) { move(a,c); times ++; } X 移动到塔座 A ； X 移动到塔座 C ； Z 移动到塔座 C 。 Y 移动到塔座 Y 移动到塔座 X 移动到塔座 B ； A ；

从汉诺塔问题看递推关系在实际问题中的应用

从汉诺塔问题看递推关系在实际问题中的应用 姓名:孙瑞 学号:200640501218 指导老师:马玉田 摘要：本文主要介绍了递推关系在实际中的应用，对几个实际问题的分析，让我们清楚的看到递推关系在 解决实际问的强大作用． 关键词：数列 递推关系 汉诺塔 九连环 蛛网模型 引言: 递推关系在实际问题中有着广泛的应用.由连续变量可以建立微分方程模型,离 散变量可以建立递推关系模型. 经过分析可知，常、偏微分方程除非在极其特殊的情况下，否则一般不存在解析解，所以讨论起来非常麻烦，比如最基本的平衡点的稳定性，往往只能得到局部稳定性，全局稳定性很难得到，而递推关系模型可以达到全局的效果，另外，由递推关系获得的结果又可以进一步进行优化分析、满意度分析、分类分析、相关分析等等。而在实际中，连续变量可以用离散变量来近似和逼近，从而微分方程模型就可以近似于某个递推关系模型。递推关系模型有着非常广泛的实际应用背景,我们的前人建立了许多著名的模型,如生态模型,传染病模型,经济模型(如蛛网模型),人口控制模型(如著名的马尔萨斯人口控制模型)等等. 定义:设012,,,,n a a a a 是一个数列,把该数列中n a 与它的前面几个 (01)i a i n ≤≤-关联起来构成的方程,称为一个递推关系,即(,,)n j k a f a a = (0,1)j k n ≤≤-. 下面让我们看看递推关系在汉诺塔问题中的应用. 引例:汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动 汉诺塔问题:它是由三根固定的柱子ABC 和不同尺寸的n 个圆盘组成.开始时,这些个大小不同的圆盘依其半径大小依次套在A 柱上,使大圆盘在底下.游戏的规则是:每次的圆盘从一根柱子移到另一根柱子上,但是不允许这个圆盘放在比它小的圆盘上面.游戏的目标是

汉诺塔问题实验报告

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); }

汉诺塔问题的非递归算法分析

汉诺塔递归与非递归算法研究 作者1，作者2，作者33 (陕西师范大学计算机科学学院，陕西西安 710062) 摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息. 关键词:关键词1; 关键词2；关键词3；……（一般可选3~8个关键词，用中文表示，不用英文 Title 如：XIN Ming-ming , XIN Ming (1.Dept. of ****, University, City Province Zip C ode, China；2.Dept. of ****, University, City Province Zip C ode, China；3.Dept. of ****, University, City Province Zip C ode, China) Abstract: abstract（第三人称叙述，尽量使用简单句；介绍作者工作（目的、方法、结果）用过去时，简述作者结论用一般现在时） Key words: keyword1;keyword2; keyword3;……（与中文关键词对应，字母小写(缩略词除外)）； 正文部分用小5号宋体字，分两栏排，其中图表宽度不超过8cm.。设置为A4页面 1 引言（一级标题四号黑体加粗） 这个问题当时老和尚和众僧们，经过计算后，预言当所有的盘子都从基柱A移到基座B上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。其实，不管这个传说的可信度有多大，如果考虑把64个盘子，由一个塔柱上移到另一根塔柱上，并且始终保持上小下大的顺序。假设有n个盘子，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题，目前还有不少的学者继续研究它的非递归解法，本文通过对递归算法的研究……. 提示：（1）可以定义问题的规模n,如盘子的数量；（2）塔柱的数量（目前有部分理论可以支撑，不妨用计算机实现）分析规模的变化与算法的复杂度比较。（3）可以对经典的汉诺塔问题条件放松、加宽，如在经典的汉诺塔问题中大盘只能在小盘下面，放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述（二级标题小五黑体加粗） 用人类的大脑直接去解3，4或5个盘子的汉诺塔问题还可以，但是随着盘子个数的增多，问题的规模变的越来越大。这样的问题就难以完成，更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n个盘的汉

汉诺塔问题的重点是分析移动的规则

汉诺塔问题的重点是分析移动的规则，找到规律和边界条件。 若需要将n个盘子从A移动到C就需要（1）将n-1个盘子从A移动到B；（2）将你第n个从A移动到C；（3）将n-1个盘子再从B 移动到C，这样就可以完成了。如果n!=1，则需要递归调用函数，将A上的其他盘子按照以上的三步继续移动，直到达到边界条件n=1为止。 思路清楚了，程序就好理解了。程序中的关键是分析好每次调用移动函数时具体的参数和对应的A、B、C塔的对应的关系。下面来以实际的例子对照程序进行说明。 ①move(int n,int x,int y,int z) ②{ ③if (n==1) ④printf("%c-->%c\n",x,z); ⑤else ⑥{ ⑦move(n-1,x,z,y); ⑧printf("%c-->%c\n",x,z); ⑨{getchar();}//此句有必要用吗？感觉可以去掉的吧 ⑩move(n-1,y,x,z); } }

比如有4个盘子，现在全部放在A塔上。盘子根据编号为1、2、3、4依次半径曾大。现在要将4个盘子移动到C上，并且是按原顺序罗列。首先我们考虑如何才可以将4号移动到C呢？就要以B为中介，首先将上面的三个移动到B。此步的操作也就是程序中的①开始调入move函数（首次调用记为一），当然现在的n=4，然后判断即③n！=1所以不执行④而是到⑤再次调用move函数（记为二）考虑如何将3个盘移动到B的方法。此处是递归的调用所以又一次回到①开始调入move函数，不过对应的参数发生了变化，因为这次要考虑的不是从A移动4个盘到C，而是要考虑从A如何移动移动3个盘到B。因为n=3，故不可以直接移动要借助C做中介，先考虑将两个移动到C的方法，故再一次到⑤再一次递归调用move函数（记为三）。同理两个盘还是不可以直接从A移动到C所以要以B为中介考虑将1个移动到B的过程。这次是以B为中介，移动到C为目的的。接下来再一次递归调用move函数（记为四），就是移动到B一个，可以直接进行。程序执行③④句，程序跳出最内一次的调用（即跳出第四次的调用）返回上一次（第三次），并且从第三次的调用move 函数处继续向下进行即⑧，即将2号移动到了C，然后继续向下进行到 ⑩，再将已经移到B上的哪一个移回C，这样返回第二次递归（以C 为中介将3个盘移动到B的那次）。执行⑧，将第三个盘从A移动到B，然后进入⑩，这次的调用时因为是将C上的两个盘移到B以A

scratch图解汉诺塔问题

scratch图解汉诺塔问题 汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘 在进行转移操作时，都必须确保大盘在小盘下面，且每次只能移动一个圆盘，最终c柱上有所有的盘子且也是从上到下按从小到大的顺序。 当a柱子上只有一个盘子时只要把那个盘子直接移到c就行了， 有两个盘子的话把1号盘先移到b柱，在把2号盘移到c柱，最后把b柱上的1号盘移到c柱就行了， 那么如果有n个盘子呢？ 这里我们先把上方的n-1个盘子看成整体，这下就等于只有两个盘子，自然很容易了，我们只要完成两个盘子的转移就行了,再把前n-2个盘子看作一个整

体，就这样一步步向前找到可以直接移动的盘子，n-3......，2,1，最终，最上方的盘子是可以直接移动到c柱的。 看到这里其实就已经有了程序的设计思路，那就是递归，这个时候只要理解递归最终的解决的问题是什么就行了，中间的事交给程序，递归可以很绕也可以很直接，我们按照最直接的理解就行了。

如果你想想清楚每一步执行过程，那么你可以继续往下看，确实有点乱，切记别把自己绕晕了。 举个例子：当n=7时，前6个要想办法成功移动到b柱上，7号是Boss，他不管上面的6个小弟用什么办法，我可以先等着，于是7号在等着上面6个完成移到b柱，现在6是临时老大，他也想去c柱，于是他命令前5个移到b 柱，他等着，5号也采取之前两个的做法，于是这个命令一直往前传，没办法，上面被压着自己也没法动啊。 终于到了1号，他是现在唯一能动的，于是1号移动到了b柱，好了，2号可以到c柱。不过a柱上还有3号，于是让1号移到c柱，3号可以到b柱了，之后1号和2号在想办法到b柱，于是1,2,3号在b柱，4号也要得到b柱啊，1,2,3号你们按照刚才的办法到c柱，空出b柱给4号。后面的5号、6号都重复这样的操作，终于前6号移动到b柱，7号直接跑到了c柱，于是剩下在b 柱的6个小弟还要再干一遍他们在a柱上干的事。 程序截图：

汉诺塔 面向对象课程设计

数据库课程设计报告------------题目：汉诺塔 学院名称：计算机学院 专业名称：计算机科学与技术 班级：计算机08-08班 学号：0804010807 姓名:田昊 指导教师：孙冬璞 起始时间：2011年1月5日-------2011年1月9日

摘要 汉诺塔（又称河内塔）问题是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。 利用计算机图形学进行汉诺塔演示程序设计,是利用C语言绘图函数实现汉诺塔的递归算法图形界面演示过程。通过C语言实现图形学的绘图，程序控制，以及区域填充，并根据汉诺塔的算法原理实现大小不同的盘子移动的全过程演示。 1 需求分析 1.1 需求概述 汉诺塔演示程序设计是计算机图形学中图形变换的内容之一。而图形学中的图形变换的概念是由简单图形生成复杂图形，可用二维图形表示三维形体，甚至可以对静态图形经过快速变换而获得图形的动态显示效果。其任务是研究各点坐标之间的变化规律。而本次课程设计就是利用C语言以及图形函数实现汉诺塔的递归算法来进行其盘块移动的全过程显示。在TC环境中要实现这样的功能，就要牵涉到图形设备接口的知识。Windows图形设备接口是为与设备无关的图形设计的，是Windows系统的重要组成部分,负责系统与用户或绘图程序之间的信息交换,并控制在输出设备上显示图形或文字。应用程序必须通知图形设备接口来加载特定的设备驱动，一旦驱动得以加载，就可以准备应用设备进行相关的操作这些任务都要通过创建和维护设备描述表来完成。在实现汉诺塔演示程序设计时，是利用坐标系统而得到的，而在Windows应用程序中有两种坐标系统：设备坐标系统和逻辑坐标系统。其中设备坐标系统中又有三种相互独立的坐标系统：屏幕坐标系统、窗口坐标系统和用户区坐标系统。这些坐标系统均以像素点来表示度量的单位。屏幕坐标系统使用整个屏幕作为坐标区域，原点为屏幕原点。窗口坐标系统使用了边界在内的应用程序的窗口作为坐标区域。窗口边界的左上角是坐标系统的原点。用户坐标系统是最经常使用的坐标系统。用户区是窗口工作区，不包括窗口边界、菜单条及滚动条等。用户一般只需操作应用程序的用户区，因此用户区坐标系统对大多数应用程序都是适用的。

汉诺塔程序解读

hanoi塔程序如下： main() {hanoi(3,'A','B','C'); } hanoi(n,a,b,c) int n; char a,b,c; {if (n==1) printf("%c-->%c\n",a,c); else {hanoi (n-1,a,c,b); printf ("%c-->%c\n",a,c); hanoi (n-1,b,a,c);} } 运行结果： A-->C A-->B C-->B A-->C B-->A B-->C A-->C 问题： hanoi(n,a,b,c) int n; char a,b,c; {if (n==1) printf("%c-->%c\n",a,c); else {hanoi (n-1,a,c,b); printf ("%c-->%c\n",a,c); hanoi (n-1,b,a,c);} } 我给你详细解释下这个程序中的代码吧。我也是刚学，希望对你有用。可能有些不好之处，还希望谅解。 先说下这个问题的整体思想： 1，如果只有1个盘，那么就直接把这个盘从A移动到C上。

2，如果存在两个盘，那么先把第一个盘移动到B上，在把最下面一个盘移动到C上，在把B上的盘移动到C上。 3，这样，我们可以得出一个结论，如果存在N个盘，可以先把上面N-1个盘通过C 移动到B上，然后把第N个盘移动到C上，再把B上的N个盘通过A 移动到C上。 if (n==1) printf("%c-->%c\n",a,c); 这一句，表示只有1个盘子的时候，那么就是把第一个盘子直接移到第三个盘子上。 else {hanoi (n-1,a,c,b); 如果超过一个盘字，则需要先把N-1个盘子通过C 移动到B上。 printf ("%c-->%c\n",a,c); 把剩下的第N个盘，从A移动到C上。 hanoi (n-1,b,a,c);} 再把剩下的在B上的N-1个盘，通过A移动到C上。 这属于一个递归算法。 现在，N=3。 我们看下程序怎么运行的。 else {hanoi (n-1,a,c,b); printf ("%c-->%c\n",a,c); hanoi (n-1,b,a,c);} N=3，也就是开始程序会执行 hanoi (2,a,c,b);这句语句。 再看，2还是大于1，所以 程序会继续运行。注意，这里，为hanoi (2,a,c,b); C和B 换了位置。 hanoi (2,a,c,b); 我们把数字代入，得出。 根据N=2，C和B 互换。以及下面的代码，得出 ````````````````````````````````````````````````

课程实践报告_汉诺塔

课程实践报告 题目：汉诺塔 姓名： 学号： 班级： 日期：

一实践目的 1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力； 2、进一步提升C语言的应用能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； 6、提升文档写作能力。 二问题定义及题目分析 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A，B，C。A杆上有若干圆盘。2.每次移动一块圆盘，小的只能叠在大的上面。3.把所有圆盘从A杆全部移到C杆上。经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动圆盘：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。 程序所能达到的功能： 用户只需要输入所需的层数即可，程序会自动计算出最终需要的步骤，并同时给出中间移动的过程。 三概要设计 1、设计思想 如果盘子为1，则将这个盘子从塔座A移动到塔座C；如果不为1，则采用递归思想。将塔座A的前n-1个盘子借助C盘（即目的盘）移到塔座B，移后，此时C为空座，那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C，从而完成盘子的移动。 2、数据类型 结构体：用来存放盘子的栈。同时，在函数的参数中还用到了结构体类型的引用。 其他类型：基本的数据类型，包括整形，字符型。用来存放临时变量。 3、主要模块

汉诺塔问题非递归算法详解

Make By Mr.Cai 思路介绍： 首先，可证明，当盘子的个数为n 时，移动的次数应等于2^n - 1。 然后，把三根桩子按一定顺序排成品字型（如：C ..B .A ），再把所有的圆盘按至上而下是从小到大的顺序放在桩子A 上。 接着，根据圆盘的数量确定桩子的排放顺序： 若n 为偶数，按顺时针方向依次摆放C ..B .A ； 若n 为奇数，按顺时针方向依次摆放B ..C .A 。 最后，进行以下步骤即可： （1）首先，按顺时针方向把圆盘1从现在的桩子移动到下一根桩子，即当n 为偶数时，若圆盘1在桩子A ，则把它移动到B ；若圆盘1在桩子B ，则把它移动到C ；若圆盘1在桩子C ，则把它移动到A 。 （2）接着，把另外两根桩子上可以移动的圆盘移动到新的桩子上。 即把非空桩子上的圆盘移动到空桩子上，当两根桩子都非空时，移动较小的圆盘。 （3）重复（1）、（2）操作直至移动次数为2^n - 1。 #include #include using namespace std; #define Cap 64 class Stake //表示每桩子上的情况 { public: Stake(int name,int n) { this->name=name; top=0; s[top]=n+1;/*假设桩子最底部有第n+1个盘子，即s[0]=n+1，这样方便下面进行操作*/ } int Top()//获取栈顶元素 { return s[top];//栈顶 } int Pop()//出栈 { return s[top--];

} void Push(int top)//进栈 { s[++this->top]=top; } void setNext(Stake *p) { next=p; } Stake *getNext()//获取下一个对象的地址 { return next; } int getName()//获取当前桩子的编号 { return name; } private: int s[Cap+1];//表示每根桩子放盘子的最大容量 int top,name; Stake *next; }; void main() { int n; void hanoi(int,int,int,int); cout<<"请输入盘子的数量："; cin>>n; if(n<1) cout<<"输入的盘子数量错误!!!"<