汉诺塔问题
递归算法是计算机算法的重要内容，很多问题都可以使用递归方法解决。递归算法的特点是可以比较自然的反映解决问题的过程，并能够便于调试程序。对于某些问题（例如汉诺塔问题，树的遍历等问题），需要通过递归算法求解。
汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B 座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。
这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。
如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。
如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。
如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。
如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。
上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。
根据以上的分析，不难写出程序：
void Move(char chSour, char chDest)
{
/*打印移动步骤*/
printf("\nMove the top plate of %c to %c",chSour, chDest);
}
Hanoi(int n, char chA, char chB, char chC)
{
/*检查当前的盘子数量是否为1*/
if(n==1) /*盘子数量为1，打印结果后，不再继续进行递归*/
Move(chA,chC);
else/*盘子数量大于1，继续进行递归过程*/
{
Hanoi(n-1,chA,chC,chB);
Move(chA,chC);
Hanoi(n-1,chB,chA,chC);
}
}
main()
{
int n;
/*输入盘子的数量*/
printf("\nPlease input number of the plates: ");
scanf("%d",&n);
printf("\nMoving %d plates from A to C:",n);
/*调用函数计算，并打印输出结果*/
Hanoi(n,'A','B','C');
}
如果n为4，程序输出结果为：
Moving 4 plates from A to C:
Move the top plate of A to B
Move the top plate of A to C
Move the top plate of B to C
Move the top plate of A to B
Move the top plate of C to A
Move the top plate of C to B
Move the top plate of A to B
Move the top plate of A to C
Move the top plate of B to C
Move the top plate of B to A
Move the top plate of C to A
Move the top plate of B to C
Move the top plate of A to B
Move the top plate of A to C
Move the top plate of B to C
为了便于理解，先分析将A座上3个盘子移动到C座上的过程：
1、将A座上2个盘子移动到B座上（借助C）；
2、将A座上1个盘子移动到C座上；
3、将座上2个盘子移动到C座上（借助A）。
其中第2步可以直接实现，第1步可以用递归方法分解为：
1.1、将A上1个盘子从A移动到C；
1.2、将A上1个盘子从A移动到B；
1.3、将C上1个盘子从C移动到B。
第3步可以分解为：
3.1、将A上1个盘子从A移动到C；
3.2、将A上1个盘子从A移动到B；
3.3、将C上1个盘子从C移动到B。
综上所述，可以得到移动盘子的步骤：
A->C,A->B,C->B,A->C,B->A,B->C,A>C 共经历七步。
附相关程序：
汉诺塔c语言：
#include
intmain()
{
voidhanoi(intn,charone,chartwo,charthree);
intm;
printf("inputthenumberofdiskes:");
scanf("%d",&m);
printf("thesteptomoveing%diskes:\n",m); hanoi(m,'A','B','C');
return0;
}
voidhanoi(intn,charone,chartwo,charthree) {
voidmove(charx,chary);
if(n==1)
move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
voidmove(charx,chary)
{
printf("%c-->%c\n",x,y);
}
汉诺塔PROLOG语言：
用Prolog语言实现汉诺塔（大体描述）
谓词predicates
Hanoi(integer,integer,integer,integer)
层数，起点，临时，终点
目标goal
Hanoi(3,1,2,3)
子句clauses
hanoi(1,A,_,C):-write("No.",A,"-->No.",C),nl.
hanoi(N,A,B,C):-N1=N-1,
hanoi(N1,A,C,B),hanoi(1,A,B,C),hanoi(N1,B,A,C).
详细程序：
domains
pile_id=symbol
predicates
hanoi(integer).
move(integer,pile_id,pile_id,pile_id)
inform(pile_id,pile_id)
clauses
hanoi(N):-move(N,a,b,c).
move(1,A,_,C):-inform(A,C),!.
Hanoi(.),
Hanoi(.),
move(N,A,B,C):-N1=N-1,move(N1,A,C,B),
inform(A,C),move(N1,B,A,C).
inform(Loc1,Loc2):-write("From",Loc1,"Moveto",Loc2),nl.
汉诺塔（又称河内塔）问题其实是印度的一个古老的传说。
开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍：
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n - 1（有
兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归的实现源代码。
●汉诺塔算法的递归实现C++源代码
#include
#include
using namespace std;
ofstream fout(“out.txt”);
void Move(int n,char x,char y)
{
fout<<“把”< } void Hannoi(int n,char a,char b,char c) { if(n==1) Move(1,a,c); else { Hannoi(n-1,a,c,b); Move(n,a,c); Hannoi(n-1,b,a,c); } } int main() { fout<<“以下是7层汉诺塔的解法:”< Hannoi(7,‘a’,‘b’,‘c’); fout.close(); cout<<“输出完毕！”< return 0; } 顺便给出一个网上比较常见的一个汉诺塔游戏： // test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的 // //递归实现 /*#include "stdafx.h" #include { 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 神奇汉诺塔游戏活动方案 汉诺塔问题在教学届有很高的研究价值，至今还在被一些数学家们研究，也是我们所喜欢的一种益智游戏。它可以帮助开发智力，激发我们的思维，让小学生接触这款益智游戏，利用一次次不断的探索和尝试，可以激发他们的兴趣，积极应对困难，获得成功体验，锻炼他们的思维，同时也培养学生主动探究，不服输的精神。把组成“金塔”的圆片按照下大上小依次放在中央的柱子上，每次只能移动一个圆片，在移动的过程中，大圆不能压在小圆上面，每次移动的圆片只能放在左中右的位子，将整座“金塔”移到另外一根柱子上即告胜利。 和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨?班?达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第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）班。 活动开展安排： 汉诺塔非递归算法C语言实现 #include 实验二知识表示方法 梵塔问题实验 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 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<<"盘子从"< 汉诺塔问题的重点是分析移动的规则，找到规律和边界条件。 若需要将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 实验报告书 课程名：数据结构 题目：汉诺塔 班级： 学号： 姓名： 评语： 成绩：指导教师： 批阅时间：年月日 一、目的与要求 1）掌握栈与队列的数据类型描述及特点； 2）熟练掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧; 4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 5）认真书写实验报告,并按时提交。 二、实验内容或题目 汉诺塔问题。程序结果：给出程序执行过程中栈的变化过程与圆盘的搬动状态。 三、实验步骤与源程序 源程序： / *编译环境Visual C++6.0 */ #include "stdafx.h" #include 实验题目： 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 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 神奇的汉诺塔教学设计 【教学目标】 1.在操作探究的过程中，使学生能够初步体会从简单问题入手寻找规律从而解决实际问题的方法，学会有条理地思考。 2.经历收集有用的信息、进行归纳、类比与猜测、再验证猜测，这一系列数学思维过程，发展学生的归纳推理能力。 3.通过自主探究、合作交流、汇报展示，引导学生有条理地阐述自己想法，培养合作意识，获得成功的体验。 【教学过程】 热身练习： ① 1 3 5 7 （）（） ② 2 4 6 8 （）（） ③ 2 4 8 16 （）（） ④ 1 3 7 15 （）（） 一、故事引入，揭示课题 师：能说出其中的规律吗？ 小结：观察思考是学好数学的诀窍，他可以锻炼我们思维，当然，我们还可以通过游戏来锻炼我们的思维。 师：你们喜欢玩游戏吗？最近呀老师又迷上了一个数学游戏——汉诺塔。（板书课题）大家仔细观察这个汉诺塔，你看到了什么？ 生：（预设）有大小不一的圆环，还有3根柱子。 师：这3根柱子我们帮它取个名字，一根叫起始柱，一根叫过渡柱，一根叫目标柱。 关于汉诺塔还有一个古老的传说呢，一起听一听。 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 师：大胆的猜一猜，他要移动多少次才能全部移完？ 生：（预设）64次。 二、游戏操作，探索规律。 （1）师：那这个神奇的汉诺塔游戏怎么玩呢？大家有没有从这个故事中看出游戏规则呢？ 生：①小圆盘上不能放大圆盘。②一次只能移动一个圆盘。③可以借助过渡柱。 师：同学们掌握了游戏规则，那我们先来比比赛，看哪个小组以最少的次数移完4个圆环，比赛时间2分钟，开始。 学生动手操作。 （2）学生汇报。 师：你来演示一下是怎样移的？ 师:那有没有比这次数更少的，这个游戏是不是有什么规律呢？今天我们就来一起研究一下吧。 师：我们先从最简单的入手，先从1个圆环开始，依次叠加，把你们的操作过程记录在这张表上，孩子们，动起来吧！ 学生动手操作并填表做记录。 （3）点名同学上台边操作边汇报。 汉诺塔递归与非递归算法研究 作者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个盘的汉 河内塔游戏 活动目标： 1.本活动以河内塔做为媒介，从“玩”入手，让学生在“玩”的过程中，体会 最佳策略，初步感受递推法解决实际问题的方法。 2.能用有条理的、清晰的语言阐述自己的想法，学会用简单的方式记录活动过 程 3.培养学生的观察、分析、比较，综合思考能力。 活动材料：河内塔玩具、活动单 活动过程： 活动一：（初步感知尝试把玩） 1.师：出示河内塔玩具 谈话:今天老师给大家带来了一个玩具，见过吗？你知道这个玩具叫什么吗？ 课题：“河内塔” 想知道这个玩具怎么玩吗？ 2.（课件出示游戏玩法） 任务：将一根柱上的圆盘全部移动到另一根柱上。 规则：1.每次只能移动一个盘子，只能在3个柱子之间移动； 2.移动过程中，小盘子一定要放在大盘子的上面，不可颠倒； 3.读一读，问：谁看懂了游戏规则，和大家说一说。 4.在学生介绍的基础上老师结合操作介绍游戏规则 问：你想玩吗？那我们也来玩一玩。老师给你3分钟时间，请边玩边注意这个游戏的规则。（完好后把盘放回信封） 5.你知道吗，很多的数学家都研究过这个游戏。关于它还有一个古老传说，想不想听听。 传说印度教的主神梵天在创造世界的时候，在一块黄铜板上插着三根宝石针，并且在其中一根针上从下到上地穿好了由大到小的64片金片，不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针 上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声巨响中灭亡…… 师：传说中的河内塔上只有64个盘子，按照上面的规则移动完成后，我们的世界怎么可能灭亡呢？这中间究竟蕴含了什么样的奥秘呢？ 今天我们也来研究一下河内塔，揭开这个古老传说中的奥秘吧。 这个河内塔上有64个金环，要是直接移动是不是有些麻烦，那你想从几个开始？ 7.在学生回答的基础上小结：对于复杂的问题，我们可以从它最简单的形式开始研究，在研究的过程中找到规律就好办了。 活动二：一盘游戏 （学生说一说，教师简单演示过程） 活动三：二盘游戏 1.学生分组活动，两人一组轮流玩。（每人玩两次，比比那组最先好） 2.组织交流：操作。 （1）老师想把盘从第一根柱上移到第三根柱上，怎么移，谁来试试，指名上前操作。（要求学生一边说一边操作） （2）师：为了说起来方便我们把左边的柱子称为A柱，中间的柱子称为B柱，右边的柱子称为C柱。谁能再说一说刚才的移动过程。 （3）我们把移动过程记录下来。 小盘---B 大盘---C 小盘---C 3.讨论研究从A柱移到B柱。 学生操作，指名说说过程，老师记录过程。你能看出他完成任务了吗？ 4.一起研究从B柱移到C柱 5.小结，刚才我们研究的两个盘的移动情况，你有什么想和大家说的。 （移动的目标不同，但都移动三次就可以完成） 活动四：三盘游戏 谈话：刚才我们都玩了一把，有趣吧，想不想玩难度大一点的。（从信封袋中拿出第三个盘） 1.学生分组活动。从A柱移动到B柱（两生合作，一人边说边移动，一人把移动过程记录下来）完成活动单第一列 数据库课程设计报告------------题目：汉诺塔 学院名称：计算机学院 专业名称：计算机科学与技术 班级：计算机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 互换。以及下面的代码，得出 ```````````````````````````````````````````````` 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 } 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<<"输入的盘子数量错误!!!"< XXXX大学信息学院 课程设计报告 教师签名：xxxxx 题目1实验报告 1．数据结构定义 因为该算法需要用到循环队列、堆和线性表，因此采用以下数据类型： typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue;//循环队列 typedef struct { int *elem; int length; int listsize; }SqList;//堆排序 2．算法说明 void HeapAdjust(int flag,SqList &H,int s,int m) void HeapSort(int flag,SqList &H)//对H进行堆排序； Status InitQueue(SqQueue &Q)//构造一个空队列Q，该队列预定义大小为MAXQSIZE; Status EnQueue(SqQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素; Status DeQueue(SqQueue &Q, QElemType &e) // 若队列不空, 则删除Q的队头元素, 用e 返回其值, 并返回OK; 否则返回ERROR; Status GetHead(SqQueue Q, QElemType &e)// 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR; Status QueueLength(SqQueue Q) // 返回Q的元素个数; Status QueueTraverse(SqQueue Q)// 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR. 3．用户使用说明 运行程序，根据屏幕上的文字提示一步步操作。 4．个人测试结果（截图） 部分测试结果截图 汉诺塔、数形结合及其他——卞强老师讲座中的故事 [ 2008-9-8 13:10:00 | By: 张弛有道 ] 推荐 上周四听了卞强老师的讲座，涉及到一些有趣的故事，现搜索整理其中一部分，供大家参考。 一、汉诺塔问题 Towers of Hanoi，汉诺塔（又称河内塔、梵塔）问题是印度的一个古老的传说。传说开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在创造世界的时候，在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从原来那根针上移到另外一概针上时（规定可利用第三根针作为帮助），世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。 不管这个传说的可信度有多大，如果考虑一下把６４片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序，一共需要移到多少次。那么，不难发现：不管把哪一片移到另一根针上，移动的次数都要比移动上面一片增加一倍。这样，移动第1片只需1次，第2片需2次，第3次需4次……第64片需264次。全部次数为1+2 +22+…+263=264-1=18446744073709551615次。 假如每秒钟一次，共需多长时间呢？一年（地球绕太阳一周）的时间是365天5小时48分46秒，大约有31556926秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都已经灰飞烟灭。看来，众僧们耗尽毕生精力也不可能完成金片的移动。 后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上 此外，汉诺塔问题也体现了数学中的经典递归问题。 算法思路： 1.如果只有一个金片，则把该金片从源移动到目标棒，结束。 2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒。 这个问题即可以这样解决：把前63个看作一个整体，移动到非 三峡大学理学院2011级电信专业 《高级语言程序设计》课程设计 说明书 设计题目: 汉诺塔的搬移过程设计 班级：高级语言程序设计1 班 学号：2011142227 姓名：徐飞 完成日期：2012 年6月20日 1设计任务 设计题目：用递归法计算解决汉诺塔问题，并能够演示解决汉诺塔问题过； 要求：设计一个运用递归法计算解决汉诺塔问题C语言程序； 2 汉诺（Hanoi）塔问题的提出 古代有一个梵塔，塔内有A,B,C，3个座，座A上有64个大小不等的盘子，大的在下，小的在上（如下图）。有一个和尚想把这64个盘子从座A全部移到座C ，在移动过程中可以借用座A，座B或座C,但每次只允许移动一个盘子，并且不允许大盘放在小盘的上面。 3编程思路 首先，要找出递归的两个关键点，即： 递归终止条件：只有一个盘子时，可以移动。 递归表达式：要找出递归表达式，可以如下设想： 下面以3个盘子为例说明详细的移动过程： (1)将座A上的2个盘子移动到座B上； (2)将座A上的1个盘子移动到座C上； (3)将座B上的2个盘子移动到座C上； 上面第1步可用递归方法分解为： （1）将座A上的1个盘子从座A移动到座C上； （2）将座A上的1个盘子从座A移动到座B上； (3)将座C上的1个盘子从座C移动到座B上； 第（3）步可用递归方法分解为： （1）将座B上的1个盘子从座B移动到座A上； （2）将座B上的1个盘子从座B移动到座C上； （3）将座B上的1个盘子从座A移动到座C上; 第（1）步操作可归纳为：将座A上的2个盘子借助座C移到座B; 第（3）步操作可归纳为：将座B上的2个盘子借助座A移到座C; 因此，将n个盘子从座A移到座C可以描述为： （1）将n-1个盘子从座A借助座C移到座B; （2）将剩下的一个盘子从座A移到座C; （3）将n-1个盘子从座B借助座A移到座C; 3系统操作流程图; 4.程序说明； “汉诺塔”问题探趣 洞头县实验小学 502班叶钫舟 指导老师洞头县实验小学陈素萍 一、问题的提出： 一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 尽管这个传说并不可信，但现在却成就了一种益智玩具━━“汉诺塔”(如图)的诞生。对下面这个8层汉诺塔，如何按以上要求将所有的圆盘从最左边的柱子上移到最右边的柱子上来呢？并如何保证移动的步子最少呢？ 对这个富有挑战性的游戏，我非常有兴趣，于是我开始了研究！ 二、研究过程： 1、简化器材，方便携带，随时演练，不断研究 “汉诺塔”游戏器材，体积较大，质量也大，不方便随身携带，因而也不能让我随时随地进行演练。 考虑到它最关键的是体现由小到大的一种排列，我用扑克牌同色的1（A），2，3，4，5，6，7，8来代替这个“汉诺塔”，平时演练，只要假想桌子上有左0、中1、右2三个档位即可，将这8张扑克牌从上到下按由小到大的顺序叠放在一起，放置在左边档位0处，然后将按游戏规则将它们依次全部移到最右边档位2处即可。 我把这种用扑克牌玩“汉诺塔”游戏称为“汉诺牌”，这样就很方便了！有时忘记了带扑克牌，我就用笔在纸上写下1～8这张8张“牌”，就可以玩了！ 有趣的汉诺塔 ——思维潜能开发校本教材 河山实验学校小学部时美娟 前言 数学教学游戏（思维潜能开发）课程是按照《优质课堂与现代教学技艺运用的研究》总课题组倡导的“教学游戏”理念,借鉴国内外“思维潜能开发”的有效经验，结合心理学、认知科学和脑科学的最新研究成果,经过本土化再造后, 逐步形成的教学游戏课程的训练体系。其核心是以“益智”为载体，通过愉悦的探究体验活动，开发学生的思维潜能，促进学生身心健康的全面发展。 教学游戏（思维潜能开发）课程实质上是一种思维潜能开发训练。它采用课程化的训练体系，试图跳出目前“题型”和“分数”的羁绊，在充满游戏乐趣和紧张思维碰撞的精神活动中挑战固有的思维定势，开发学生的智慧潜能。它不仅是一种在探索中进行创新思维的学习，还是落实《义务教育阶段数学课程标准2011年版》对“四基、四能”教学要求的一种有效手段。其目的在于让学生在实践、体验中培养其创新意识、践行能力，团结协作、社会活动等方面的能力及技艺。 河内塔是根据一个传说形成的一个问题：有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？ 目录 1 基本介绍 2 历史传说 3 相似问题 4 concreteHAM 4.1 在分析⑵之前 4.2 讨论问题⑵， 4.3 算法介绍 5 汉诺塔问题的程序实现 5.1 汉诺塔问题的递归实现 5.2 汉诺塔问题的非递归实现 5.3 汉诺塔问题的递归Java语言实现 5.4 汉诺塔问题的递归pascal语言实现汉诺塔问题的三种实现
智慧汉诺塔活动方案
汉诺塔非递归算法C语言实现
汉诺塔问题
汉诺塔问题的重点是分析移动的规则
数据结构实验报告汉诺塔
汉诺塔程序实验报告
汉诺塔问题实验报告
奇妙的汉诺塔教学设计
汉诺塔问题的非递归算法分析
小学人教四年级数学策略(汉诺塔)
汉诺塔 面向对象课程设计
汉诺塔程序解读
汉诺塔问题非递归算法详解
汉诺塔问题
汉诺塔、数形结合及其他——卞强老师讲座中的故事
汉诺塔问题C语言程序设计
汉诺塔探趣
汉诺塔教材