汉诺塔问题
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．个人测试结果（截图）
部分测试结果截图
题目2实验报告
用堆栈实现汉诺塔问题的非递归求解抽象数据类型栈(stack)的定义：栈是限定仅在表尾进行插入或删除操作的线性表。栈又称为后进先出的线性表（简称LIFO结构），对栈来说，表尾端称为栈顶（top），相应的，表头端称为栈底（bottom），不含元素的空表称为空栈。
栈有两种存储表示方法：顺序栈和链栈，本次实验采用栈的顺序存储结构。
n阶汉诺塔问题的描述:假设有3个分别命名为X，Y和Z的塔座，在塔座X上插有n 个直径大小各不相同、依小到大编号为1，2，…，n的圆盘。现要求将X塔座上的n个圆盘移至Z塔座上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在X、Y和Z中的任一塔座上；
（3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
该道题可以用递归的的方法解决，算法思想如下：
假如只有一个圆盘，即n=1，只需将编号为1的圆盘从X移到Z；
假如n>1，移动的过程可分解为三个步骤：第一步把X上的n-1个圆盘移到Y上，Z 作辅助塔；第二步把X上的一个圆盘移到Z上；第三步把Y上的n-1个圆盘移到Z上，X作辅助塔；其中第一步和第三步是类同的。
C代码的实现如下：
if(n==1)
move(x,z);
else
{
hanoi(n-1,x,z,y);
move(first,third);
hanoi(n-1,y,x,z);
}
下面给出用堆栈实现汉诺塔的非递归解法：
void hanoi(st ta[], long max)//移动汉诺塔的主要函数
{
int k = 0;
int i = 0;
int ch;
while (k < max)
{//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << ta[i%3].name <<
"--->" << ta[(i+1)%3].name << endl;
i++;//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if (k < max)
{//把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小圆盘if (ta[(i+1)%3].Top() == 0 ||
ta[(i-1)%3].Top() > 0 &&
ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << ta[(i-1)%3].name
<< "--->" << ta[(i+1)%3].name << endl;
}
else
{
ch = ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout << ++k << ": " << ta[(i+1)%3].name
<< "--->" << ta[(i-1)%3].name << endl;
}
}
}
}
为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前活动指针”。递归函数结构清晰，程序易懂，而且它的正确性容易得到证明，因此，利用允许递归调用的语言进行程序设计时，给用户编制程序和调试程序带来了很大方便。
不过因为对这样一类递归问题编程时，不需要用户而由系统来管理递归工作栈，不便于用户理解栈的工作原理，也增加了系统的负担，因为递归算法语句虽少，但需要大量的栈空间，运行效率不高；用非递归的方法解决汉诺塔的问题，仅用少量的存储空间克服了递归算法的不足，兼顾了时间与空间的复杂度，提供了解决汉诺塔问题的新方法，缺点是理解起来可能比较困难，可读性也不是很好。
部分测试结果截图：
汉诺塔问题的三种实现
// 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、讲解汉诺塔的游戏规则。 二、课程设计目的： 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柱上．．．．．． 神奇汉诺塔游戏活动方案 汉诺塔问题在教学届有很高的研究价值，至今还在被一些数学家们研究，也是我们所喜欢的一种益智游戏。它可以帮助开发智力，激发我们的思维，让小学生接触这款益智游戏，利用一次次不断的探索和尝试，可以激发他们的兴趣，积极应对困难，获得成功体验，锻炼他们的思维，同时也培养学生主动探究，不服输的精神。把组成“金塔”的圆片按照下大上小依次放在中央的柱子上，每次只能移动一个圆片，在移动的过程中，大圆不能压在小圆上面，每次移动的圆片只能放在左中右的位子，将整座“金塔”移到另外一根柱子上即告胜利。 和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨?班?达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第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．实验目的 （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 实验题目： 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 从汉诺塔问题看递推关系在实际问题中的应用 姓名:孙瑞 学号: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 神奇的汉诺塔教学设计 【教学目标】 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.能用有条理的、清晰的语言阐述自己的想法，学会用简单的方式记录活动过 程 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柱（两生合作，一人边说边移动，一人把移动过程记录下来）完成活动单第一列 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 互换。以及下面的代码，得出 ```````````````````````````````````````````````` 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．个人测试结果（截图） 部分测试结果截图 “汉诺塔”问题探趣 洞头县实验小学 502班叶钫舟 指导老师洞头县实验小学陈素萍 一、问题的提出： 一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 尽管这个传说并不可信，但现在却成就了一种益智玩具━━“汉诺塔”(如图)的诞生。对下面这个8层汉诺塔，如何按以上要求将所有的圆盘从最左边的柱子上移到最右边的柱子上来呢？并如何保证移动的步子最少呢？ 对这个富有挑战性的游戏，我非常有兴趣，于是我开始了研究！ 二、研究过程： 1、简化器材，方便携带，随时演练，不断研究 “汉诺塔”游戏器材，体积较大，质量也大，不方便随身携带，因而也不能让我随时随地进行演练。 考虑到它最关键的是体现由小到大的一种排列，我用扑克牌同色的1（A），2，3，4，5，6，7，8来代替这个“汉诺塔”，平时演练，只要假想桌子上有左0、中1、右2三个档位即可，将这8张扑克牌从上到下按由小到大的顺序叠放在一起，放置在左边档位0处，然后将按游戏规则将它们依次全部移到最右边档位2处即可。 我把这种用扑克牌玩“汉诺塔”游戏称为“汉诺牌”，这样就很方便了！有时忘记了带扑克牌，我就用笔在纸上写下1～8这张8张“牌”，就可以玩了！ 汉诺塔、数形结合及其他——卞强老师讲座中的故事 [ 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.程序说明； 由来 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 [2] 不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n 片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时， 假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下： 18446744073709551615秒 这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。 印度传说 和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。 那么，宰相要求得到的麦粒到底有多少呢？总数为 1+2+2^2 + … +2^63=2^64-1 等于移完汉诺塔所需的步骤数。我们已经知道这个数字有多么大了。人们估计，全世界两千年也难以生产这么多麦子！ [3] 汉诺塔-教学反思 第三小学翟燕燕汉诺塔游戏，起源于古印度的一个传说，这一堂从游戏中开始的数学课，将一改有些学生认为“数学很枯燥的”的想法，通过让学生自己动手去体验，不仅是在学习数学知识，更是在训练数学思维。揭开的不仅是谜底，更是想教给学生如何学好数学的一种方法。过程课中，第一，开始通过师生会话自然导入，如：你喜欢玩游戏吗？你还想继续玩吗？通过传说中关于世界末日的预言，让学生迫不及待的想找到问题的答案。第二，通过让学生到黑板上贴标题的方法，一方面自然出现课题，另一方面通过这种活动又复习了游戏规则，让学生通过活动说出游戏规则。如，师：孩子们，眼睛看到这儿来，你发现了什么？生：老师，汉诺塔这款游戏器具既有立柱，还有圆盘，我发现黑板上只有三根立柱，而缺少圆盘。师：孩子，你有一双善于发现的眼睛。圆盘在老师手里。谁来将这三个纸质圆盘贴到黑板上的第一根圆柱上？生贴师：大家同意他的贴法吗？理由是什么？师：同学们同意他的观点吗？生：。。。师：是的，小盘在上，大盘在下，这是我们玩这款游戏的规则之一（PPT出示），汉诺塔仅仅这一个规则吗？生：老师，我知道。玩汉诺塔还有一个规则是：一次只能移动一个圆盘。师：说的很好。请同学们仔细观察，看老师的操作是否正确，并说出理由。（师故意做错误演示）生：。。。。第三，注重在各个环节 中渗透对学生的情感目标。比如“师：孩子们知道了游戏规则，我想征求大家的意见，此时，你最想干什么？”通过询问，拉近和学生的距离，建立一种平等民主的教学环境。又如“师：XX同学，不仅善于分析，还讲述的非常清楚，跟大家分享了他的成功。孩子们，分享别人的成功，也是一种进步。”让学生知道要取长补短，互相学习。第四，通过让学生找最少步数之间的规律进行拓展延伸，找到里面的数学奥秘，让学生觉得数学是很有趣的，数学无处不在，我们可以用数学问题解释生活中的很多事情。如，师：要是我们一直这样做下去，还没有做到咱们所有的9个圆盘的游戏，就已经下课了，来，我们先一起看一下我们的研究成果，认真看，你发现这些数字有什么规律了吗？最后，作为奖励我给学生讲了一个小故事，这个故事正好体现了本节课的数学问题，让学生在课下研究探索，找到问题的答案，寓教于乐。师：同学们，今天的这堂课老师分享了你们的成功和快乐，老师有一个故事也想和大家分享一下，“百万富翁的破产”：杰米是百万富翁，一天，他碰到上一件奇怪的事。一个叫韦伯的人对他说，我想和你订个合同，我将在整整一个月中每天给你10万元，而你第一天只需给我1分钱，以后你每天给我的钱是前一天的两倍。杰米说，真的？！你说话算数？合同开始生效了，杰米欣喜若狂。第一天杰米支出1分钱，收入10万元。第二天，杰米支出2分钱，收入10万元。到了第10天，杰米共得100万元，而总共才付出5元1角2分。到了第20天，杰米共得200万元，而韦伯才得千千元多。杰米想：要是合同订、三个月该多好！结果杰米却破产了。汉诺塔问题在数学界有很高的研究价值，而且至今还在被一些数学家们所研究，它可以帮助开发智力，激发 有趣的汉诺塔 ——思维潜能开发校本教材 河山实验学校小学部时美娟 前言 数学教学游戏（思维潜能开发）课程是按照《优质课堂与现代教学技艺运用的研究》总课题组倡导的“教学游戏”理念,借鉴国内外“思维潜能开发”的有效经验，结合心理学、认知科学和脑科学的最新研究成果,经过本土化再造后, 逐步形成的教学游戏课程的训练体系。其核心是以“益智”为载体，通过愉悦的探究体验活动，开发学生的思维潜能，促进学生身心健康的全面发展。 教学游戏（思维潜能开发）课程实质上是一种思维潜能开发训练。它采用课程化的训练体系，试图跳出目前“题型”和“分数”的羁绊，在充满游戏乐趣和紧张思维碰撞的精神活动中挑战固有的思维定势，开发学生的智慧潜能。它不仅是一种在探索中进行创新思维的学习，还是落实《义务教育阶段数学课程标准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语言实现 数学游戏班第1课时活动设计 【课题】汉诺塔 【教学时间】月日 【教学目标】1、认识汉诺塔 2、了解汉诺塔历史 3、理解汉诺塔的规则 4、进行一层、二层、三层的移动 【教学内容】认识汉诺塔 【课前准备】 教师：名单、课件 学生：汉诺塔 【活动过程设计】 一、汉诺塔知识 1、了解汉诺塔的由来 在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。 2、认识汉诺塔 3、汉诺塔游戏规则 （1）每次只能移动一片； （2）小盘在上，大盘在下； （3）从A柱到C柱，步数要最少。 二、汉诺塔游戏 1、尝试一层、二层、三层的移动 2、发现规律、引出技巧 第一步最少步数 一层 C 1 二层 B 1+1+1=3 三层 C 3+1+3=7 3、练习 三层：A→C C→B B→A A→B B→C C→A 数学游戏班第2课时活动设计 （设计者：舒彩霞） 【课题】汉诺塔 【教学时间】月日 【教学目标】1、能进行汉诺塔的四层、五层的移动。 2、能推算出第一步要移到哪根柱上。 3、能推算出需要的最少的步数。 【教学内容】汉诺塔四层、五层的移动 【课前准备】 教师：汉诺塔、记录单 学生：汉诺塔 【活动过程设计】 一、熟练进行三层的移动 二、四层汉诺塔 1、尝试移动四层汉诺塔 2、发现规律、引出技巧 第一步最少步数 一层 C 1 二层 B 1+1+1=3 三层 C 3+1+3=7 四层 B 7+1+7=15 3、四层练习 四层：A→C C→B B→A A→B B→C C→A 三、五层汉诺塔 1、尝试移动五层汉诺塔 2、发现规律、引出技巧 第一步最少步数 一层 C 1 二层 B 1+1+1=3 三层 C 3+1+3=7 四层 B 7+1+7=15 五层 C 15+1+15=31 3、五层练习 五层：A→C C→B B→A A→B B→C C→A 数学游戏班第3课时活动设计 （设计者：舒彩霞） 【课题】汉诺塔 【教学时间】月日 【教学目标】1、能进行汉诺塔的六层的移动。 2、能推算出第一步要移到哪根柱上。 3、能推算出需要的最少的步数。汉诺塔课程设计
智慧汉诺塔活动方案
汉诺塔问题
汉诺塔问题的重点是分析移动的规则
汉诺塔程序实验报告
从汉诺塔问题看递推关系在实际问题中的应用
汉诺塔问题实验报告
奇妙的汉诺塔教学设计
小学人教四年级数学策略(汉诺塔)
汉诺塔程序解读
汉诺塔问题
汉诺塔探趣
汉诺塔、数形结合及其他——卞强老师讲座中的故事
汉诺塔问题C语言程序设计
河内塔问题简介
(完整版)汉诺塔教学反思
汉诺塔教材
北师大版小学数学《数学游戏汉诺塔教案》精品教案设计