微课-汉诺塔问题教案

1、本微课适用范围如下所示：课程所属学科：计算机适用专业：计算机应用技术、计算机软件工程、电子信息适用课程：C语言程序设计、C+§序设计、JAVA程序设计、数据结构适用对象：有一定编程基础的同学汉诺塔问题微课教案学院（部）：软件学院 系（教研室）：网络教研授课教师：杨 培职 称：副教授课程名称汉诺塔算法解析及其程序实现课程类别微课教学授课对象具有一定程序设计基础考核方式自我理解与自我实现微课”是指以视频为主要载体记录教师在课堂教育教学过程中围绕某个知识点或教学环节而开展的精彩教与字活动全过程。微课”的核心组成内容是课堂教学视频（课例片段），同时还包含与该教学主题相关的教学设计、素材课件、

2、教学反思、练习测试及学生反馈、教师点评等辅助性教学资源，它们以一定的组织关系和呈现方式共同 营造”了一个半结构化、主题式的资源单兀应用 小环境” 因此，微课”既有别于传统什资源类型的教学课例、教学课件、教学设计、教学反思等教学资源。利用“微课”这种形式，师生可流畅地在线观摩课例，查教 学看教案、课件等辅助资源；也可灵活方便地将真下载保存到终端设备（如笔记本电脑、手机、MP4等）上实现移动学习、泛在学习”，非常适合于教师的观基摩、评课、反思和研究。本课程的性质和任务目 的汉诺塔问题是一个数据结构、程序设计与算法分析课程中的一个经典问题。 是函数设计与调用、递归设计与调用和算法分析的一个经典综合问

3、题。理解、和掌握与实现汉诺塔问题对进一步理解、巩固掌握数据结构、程序设计与算法分要 求析课程中的相关知识点，提高学习的逻辑思维能力。在理解掌握的基础上可与 计算机图形设计、游戏设计相结合起来，增加学习趣味性。也是一次综合实践的课程片段，既要掌握概念，又要动手编程，还要上机调试运行。对计算机专业和理工类专业来说是对课堂教学的有益补充。课程的教学目标本课程的教学目标是：通过理论和实践教学，使学生较好地掌握理解与巩固函数设计与调用、递归设计与调用和算法分析知识，掌握基本的程序设计过程和技巧，具备初步的图形设计与游戏设计的能力，并能熟练应用C、C+/Java集成环境进行程序的编写、编译与调试，解决一般

4、编程问题的水平。一、函数的设计与应用重点：C或C+中的函数设计教学重点和难点二、堆栈的应用重点：数据结构中栈的相关概念与应用。三、顺序结构程序设计重点：递归的应用。教材：C程序设计（第三版）谭浩强著清华大学出版社2005参考资料参考书：C语言程序设计案例教程张基温等清华大学出版社引言汉诺塔源自古印度神话，曾经是一个趣味数学难题，在无计算机的年代基本无法求解，在计算机帮助下可以很好的解决这个问题，但也受到计算机运算速度的影响。讲授一、问题出现的历史背景(1)汉诺塔问题也是世界末日问题之一。(2)古印度趣味数学问题之一。二、汉诺塔问题的特点重复同一种运算，但是计算机量非常巨大。三、汉诺塔问题求解方

5、法(1) 三根杆子，64个盘子。(2) 依据“大盘在下，小盘在上”的顺序放在同一根杆上。(3) 利用剩余的两根空杆，将盘子移致另一根杆子上。但是不能违背“大盘在下，小盘在上”原则。四、算法的结构(3个C程序引入C程序结构)(1)设计递归函数用递归的方法求fac(n)=n !fac(n尸n*fac(n-1) (n > 1)(递归公式)教学安排fac(n)=1 (n=1)(递归边界条件)2 2)设计 recursion formula ( 递归公式)if ( n > 1 )hanoi ( n-1, A,C,B );printf("%c%cn", A, C);hano

6、i ( n-1, B,A,C );(3)设计 Ending condition(边界条件)if ( n = 1 )printf(" %c%cn",A, C);(4)设计递归函数 void hanoi(int n,char A,char B,char C) if ( n>1 ) hanoi ( n-1, A, C, B );printf("%d: %c -> %cn”,+i,A, C);hanoi ( n-1, B, A, C ); elseprintf("%d: %c -> %cn”,+i,A,C);(5) Complexity ana

7、lysis of algorithm(算法复杂度分析)-1)+ 1=2(2A(h - 2) + 1)+ 1=2)+ 2 + L =+ 2-1 + - + 21 + 2J + 1=k 4- - + 21 + 21 +1=- I时间复杂度为：O(2n)思考题、课后作业阅读：相关的汉诺塔的资料课后设计：编写一个汉诺塔的游戏程序主要参考资料数据结构、C语言程序设计、C+和序设计教材教材课后自我 总结分析通过本课程的学习，可以帮助同学进一步理解递归问题和栈的应用。并且可以提高同学的动 手编程能力备注程序实现部分汉诺塔问题的递归实现：#include<stdio.h>void hanoi(in

8、t n,char A,char B,char C) if(n=1) printf("Move disk %d from %c to %cn",n,A,C); elsehanoi(n-1,A,C,B);printf("Move disk %d from %c to %cn",n,A,C);hanoi(n-1,B,A,C); main() int n;printf(" 请输入数字n以解决n阶汉诺塔问题：n");scanf("%d",&n);hanoi(n,'A','B','

9、;C'); 汉诺塔算法的非递归实现C+源代码#include <iostream>using namespace std;/圆盘的个数最多为64const int MAX = 64;/用来表示每根柱子的信息struct stint sMAX; /柱子上的圆盘存储情况int top; /栈顶，用来最上面的圆盘char name; /柱子的名字，可以是 A, B, C中的一个int Top()/取栈顶元素return stop;int Pop()/ 出栈return stop-;void Push(int x)入栈s+top = x;long Pow(int x, int y)

10、; 计算 xAyvoid Creat(st ta口，int n); /给结构数组设置初值void Hannuota(st ta, long max); /移动汉诺塔的主要函数int main(void)int n;cin >> n; /输入圆盘的个数st ta3; 三根柱子的信息用结构数组存储Creat(ta, n); 给结构数组设置初值long max = Pow(2, n) - 1; 动的次数应等于 2An - 1Hannuota(ta, max);/移动汉诺塔的主要函数system("pause");return 0;void Creat(st ta口，i

11、nt n) = 'A'ta0.top = n-1;/把所有的圆盘按从大到小的顺序放在柱子A上for (int i=0; i<n; i+)ta0.si = n - i;/柱子B, C上开始没有没有圆盘ta1.top = ta2.top = 0;for (int i=0; i<n; i+)ta1.si = ta2.si = 0;若n为偶数，按顺时针方向依次摆放 ABC if (n%2 = 0) = 'B' = 'C'else 若n为奇数，按顺时针方向依次摆放A C B = &

12、#39;C' = 'B' long Pow(int x, int y) long sum = 1;for (int i=0; i<y; i+) sum *= x; return sum;void Hannuota(st ta, long max) int k = 0; / 累计移动的次数 int i = 0;int ch;while (k < max) /按顺时针方向把圆盘 1从现在的柱子移动到下一根柱子 ch = tai%3.Pop();ta(i+1)%3.Push(ch); cout << +k << "

13、:" << "Move disk " << ch << " from " << tai%3.name << "to " << ta(i+1)%3.name << endl; i+;/把另外两根柱子上可以移动的圆盘移动到新的柱子上 if (k < max) /把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆 盘if (ta(i+1)%3.Top() = 0 |ta(i-1)%3.Top() > 0 &&am

14、p;ta(i+1)%3.Top() > ta(i-1)%3.Top() ch = ta(i-1)%3.Pop();ta(i+1)%3.Push(ch);cout << +k << ": " << "Move disk "<< ch << " from " << ta(i-1)%3.name<< "to " << ta(i+1)%3.name << endl;elsech = ta(i+1)%3.Pop(

15、);ta(i-1)%3.Push(ch);cout << +k << ": " << "Move disk "<< ch << "from " << ta(i+1)%3.name<< "to " << ta(i-1)%3.name << endl;汉诺塔问题的非递归实现#include <stdio.h>#include <math.h>#include <stdlib.h>

16、;第0位置是柱子上的塔盘数目int zhua100=0,zhub100=0,zhuc100=0;char charis(char x,int n)/左右字符出现顺序固定，且根据n值奇偶而不同switch(x)case 'A':return (n%2=0)?'C':'B'case 'B':return (n%2=0)?'A':'C'case 'C':return (n%2=0)?'B':'A'default:return '0'void

17、print(char lch,char rch)/打印字符if(lch='A')case 'B':zhub0+;zhubzhub0=zhuazhua0;zhuazhua0=0;zhua0-;break;case 'C':zhuc0+;zhuczhuc0=zhuazhua0;zhuazhua0=0;zhua0-;break;default:break;if(lch='B')switch(rch)case 'A':zhua0+;zhuazhua0=zhubzhub0;zhubzhub0=0;zhub0-;break;c

18、ase 'C':zhuc0+;zhuczhuc0=zhubzhub0;zhubzhub0=0;zhub0-;break;default:break;if(lch='C')switch(rch)case 'A':zhua0+;zhuazhua0=zhuczhuc0;zhuczhuc0=0;zhuc0-;break;case 'B':zhub0+;zhubzhub0=zhuczhuc0;zhuczhuc0=0;zhuc0-;break;default:break;printf("t");int i;printf(&

19、quot;(");for(i=1;i<=zhua0;i+)printf(" %d ",zhuai);printf(")");printf("(");for(i=1;i<=zhub0;i+)printf(" %d ",zhubi);printf(")");printf("(");for(i=1;i<=zhuc0;i+)printf(" %d ",zhuci);printf(")");printf("n

20、");void Hannuo(int n)/分配2An个空间bool *isrev;isrev=(bool *)malloc(sizeof(bool)*(int)pow(2,n);for(int i=1;i<pow(2,n);i+)isrevi=false;/循环计算是否逆序for(int ci=2;ci<=n;ci+)for(int zixh=(int)pow(2,ci-1);zixh<pow(2,ci);zixh+=4)/初始值重复一次，自增值可加4,减少循环次数。isrevzixh=isrev(int)pow(2,ci)-zixh;/该位置为中间位置，且奇次幕

21、逆序，偶数幕不逆序 isrev(int)pow(2,ci)=(ci-1)%2=0)?false:true;char lch='A',rch;rch=(n%2=0?'B':'C');printf("%dt",1);printf("%c->%c",lch,rch);print(lch,rch);for(int k=2;k<pow(2,n);k+)if(k%2=0)rch=charis(lch,n);elselch=charis(rch,n);printf("%dt",k);if(

22、isrevk)printf("%c->%c",rch,lch);print(rch,lch);elseprintf("%c->%c",lch,rch);print(lch,rch);int main()int n;printf("Input the num:");scanf("%d",&n);zhua0=n;for(int i=1;i<=n;i+)zhuai=n-i+1;Hannuo(n);return 0;汉诺塔汉诺塔问题的递归Java语言实现import java.util.Scann

23、er;public class HanoiTest public static void hanoi(int level,String a,String b,String c)if(level=1)move(1,a,c);elsehanoi(level-1,a,c,b);move(level,a,c);hanoi(level-1,b,a,c);static void move(int level,String a,String b)System.out.println(level+" 层："+a+"->"+b);public static void

24、 main(String口 args) Scanner sc = new Scanner。，括号中是输入，提交不上去所以就没写System.out.println(" 请输入汉诺塔的层数：");int n = sc.nextInt();System.out.println(n + "层汉诺塔的解法是：");hanoi(n,"A","B","C");汉诺塔动画 C+实现程序这是经典问题汉诺塔的解题演示动画，代码如下：/程序名称：汉诺塔移动动画/ 编译环境：Visual C+ 6.0,作 者：/最后

25、修改：/#include <graphics.h>#include <conio.h>#include <stdio.h>#define MAX 64/ 圆盘的最大数目#define NULL 0/定义栈struct STKNODEint a4;struct STKSTKNODE* stackMAX; inttop;/定义全局变量状态STK s3;/声明三个栈，分别代表一号二号三号钢针上圆盘的int v = 5;/ 调整速度/函数声明/初始化栈/汉诺塔递归/ 开始画面void Initstk(STK* s);void Hannoi(int n, char a

26、, char b, char c);void start();void Move(int n, char a, char b); int switchab(char a);void adjust();/移动过程/返回钢针号/调整速度暂停/ 主函数void main()int n, ta4 = 115, 500, 285, 520;printf("尽量小于 16n");会显示有误，但程序可以正常运行printf("请输入汉诺塔的层数(164)：”);scanf("%d", &n);STKNODE* p;p = (STKNODE*)mall

27、oc(n * sizeof(STKNODE *);n个的动态STKNODE型指针数组for (int i2 = 0; i2 < n; i2 +)pi2 = (STKNODE *)malloc(sizeof(STKNODE); 请空间Initstk(&s0);Initstk(&s1);Initstk(&s2);start();/sefillstyle(YELLOW);for (int i=0; i < n; i+) ta0 += 5;ta1 -= 20;ta2 -= 5;ta3 -= 20;bar(ta0, ta1, ta2, ta3);叠放的黄色圆盘+s0.

28、top;for (int i1 = 0; i1 < 4; i1+)/第一个圆盘的位置/因为大于十六时就/声明一个元素为/为每一个指针中/将三个栈初始化呈现开始画面/圆盘的颜色/ 画出n个从大到小一次/进栈pi->ai1 = tai1;记录每个矩形的位置,汉诺塔递归函数s0.stacks0.top = pi;/top为圆盘的个数 Hannoi(n, 'a', 'b', 'c');/system("pause"); printf("ttttGame Over!n"); /函数定义/汉诺塔的递归voi

29、d Hannoi(int n, char a, char b, char c) if(n = 1)Move(1, a, c);elseHannoi(n-1, a, c, b);Move(n, a, c);Hannoi(n-1, b, a, c);/栈的初始化void Initstk(STK *s)int i;s->top = 0;for (i = 0; i <= MAX; i+) s->stack+s->top = NULL;s->top = 0;/移动过程void Move(int n, char a, char b)int i3, i4 = 0, i5 = 0

30、;/目的钢针与源钢/源钢针钢针号/目的钢针号/两个中间结点用13 = b - a;针的位置差值14 = switchab(a);15 = switchab(b);STKNODE *q1, *q0;于源栈和目的栈问的值得传递，q1为目的栈，q0为源栈q1 = (STKNODE *)malloc(sizeof(STKNODE);q0 = (STKNODE *)malloc(sizeof(STKNODE);/源栈与目的栈值的传递q0 = si4.stacksi4.top;+si5.top;/ 进栈q1->a0 = q0->a0 + i3 * 200;q1->a1 = 500 - s

31、i5.top * 20;q1->a2 = q0->a2 + i3 * 200;q1->a3 = 500 - si5.top * 20 + 20;si5.stacksi5.top = q1;-si4.top;/ 出栈/ 向上运动while (q0->a1 >= 100)sefillstyle(YELLOW);bar(q0->a0, q0->a1, q0->a2, q0->a3);adjust();/ 调整函数Sleep(10 * v);/ 暂停(ms)sefillstyle(WHITE); bar(q0->a0, q0->a1,

32、q0->a2, q0->a3); setcolor(RED); line(q0->a0 + q0->a2) / 2, q0->a1, (q0->a0 + q0->a2) / 2, q0->a3);/重新画上被擦掉原有的红线q0->a1 -= 10;q0->a3 -= 10;if (si4.top = 0)/重新画上最后一个矩形块擦掉的底座上的两条红线line(110 + i4 * 200, 500, 290 + i4 * 200, 500);line(110 + i4 * 200, 493, 290 + i4 * 200, 493);

33、/向左或右运动，与i3 的正负有关while (q0->a2 != q1->a2)sefillstyle(YELLOW);bar(q0->a0, q0->a1, q0->a2, q0->a3);adjust();Sleep(10 * v);sefillstyle(WHITE);bar(q0->a0, q0->a1, q0->a2, q0->a3);if (i3 < 0)q0->a0 -= 20;q0->a2 -= 20;elseq0->a0 += 20;q0->a2 += 20;/向下运动while (q

34、0->a3 <= q1->a3)setfillstyle(YELLOW);bar(q0->a0, q0->a1, q0->a2, q0->a3);adjust();Sleep(10 * v);setfillstyle(WHITE);bar(q0->a0, q0->a1, q0->a2, q0->a3);setcolor(RED);if (q0->a1 > 100)线setcolor(RED);line(q0->a0+ q0->a2)/ 2, q0->a1,/ 2, q0->a3);/ i3&l

35、t;0 向左移/ i3>0 向右移/重画被擦掉的红(q0->a0+ q0->a2)q0->a1 += 10;q0->a3 += 10;在目的钢针上的相应位置绘制出黄色矩形块sefillstyle(YELLOW);bar(q1->a0, q1->a1, q1->a2, q1->a3);/绘制开始界面void start()/初始化画面大小 initgraph(800, 650);/背景设为白色 setbkcolor(WHITE);/用白色填充整个画面 cleardevice();/绘制彩虹，形成一道彩虹，摘自 easyx帮助文档示例程序 fl

36、oat H, S, L;H = 0;/色相S = 1;/饱和度L = 0.5f;/亮度setlinestyle(PS_SOLID, NULL, 2);/ 设置线宽为2for(int r = 600; r > 544; r-)H += 5;setcolor( HSLtoRGB(H, S, L); circle(750, 900, r);/说明setfont(50, 0,"华文楷体");setcolor(RED);outtextxy(200, 150,"汉诺塔移动动画");setfont(20, 0," 黑体")；outtextxy

37、(600, 200, "BY:Ronald");outtextxy(500, 200," 版本 V1.1");setfont(50, 0," 黑体");setcolor(GREEN);outtextxy(200, 350,"随便按一个键开始吧！");/绘制运动的矩形while (1)/检测是否有键盘敲击if (kbhit()break;/向右int a = 40, b = 40;/ 初始位置while (a <= 760)setfillstyle(YELLOW);bar(a, b, a + 10, b + 2

38、0);Sleep(10);setfillstyle(WHITE + a);bar(a, b, a + 10, b + 20);a += 10;if (kbhit()break;/向下while (b<=610)setfillstyle(RED);bar(a, b, a + 10, b + 20);Sleep(10);setfillstyle(WHITE - b); bar(a, b, a + 10, b + 20); b += 10;if (kbhit()break;/向左while (a >= 40)setfillstyle(GREEN);bar(a, b, a + 10, b

39、+ 20);Sleep(10);setfillstyle(WHITE - a); bar(a, b, a + 10, b + 20); a -= 10;if (kbhit()break;/向上while (b >= 40)setfillstyle(BLUE);bar(a, b, a + 10, b + 20);Sleep(10);setfillstyle(WHITE + b); bar(a, b, a + 10, b + 20); b -= 10;/清空开始界面cleardevice();/绘制运动画面的的环境 setcolor(RED);/三根红色线段作为钢针 line(400, 11

40、0, 400, 500);line(600, 110, 600, 500);line(200, 110, 200, 500);/长方体形的底座sefillstyle(LIGHTGRAY);bar3d(80, 500, 720, 510, 10, true);/暂停按钮 bar(360, 540, 440, 580);setfont(30, 0," 黑体");setcolor(GREEN);outtextxy(370, 550," 暂停");setfont(20, 0," 宋体"););setcolor(RED);outtextxy(3

41、00, 580,"鼠标暂停后请按空格继续/加速按钮bar(160, 540, 240, 580);setfont(30, 0," 黑体");setcolor(GREEN);outtextxy(170, 550," 加速");setfont(20, 0," 宋体");setcolor(RED);outtextxy(170, 580," 请按 d");/减速按钮bar(560, 540, 640, 580);setfont(30, 0," 黑体");setcolor(GREEN);outt

42、extxy(570, 550," 减速");setfont(20, 0," 宋体");setcolor(RED);outtextxy(570, 580," 请按 a");/说明setfont(50, 0," 宋体”)；setcolor(GREEN);outtextxy(10, 10,"正在进行中请欣赏：");/判断目的钢针与源钢针的钢针号返回钢针号int switchab(char a)switch (a)case 'a':return 0;case 'b':return 1;case 'c':return 2;default:return 0;/调整函数，实现加速，减速，暂停void adjust()char f;/接收键盘敲进去的按钮和鼠标点击时赋予的变化值/用f接受键盘的键入值if(kbhit() f = getch();/检测鼠标消息if (MouseHit()=true)/接收鼠标消息MOUSEMSG Mouse;Mouse = GetMo