壹,课程明
单元名称 教学时间 教案设计 资结构与演算法 8 小时 郭再兴教师(国丰原高级中学教师)
本章介绍资结构与演算法的进阶概,包含递回函与图(graph)演算 法. 1,复习函观,介绍递回函的观以及基本结构. 2,藉由具备递回性质的问题,引导并培养学生设计递回函的能. 3,介绍河内塔问题,引导学生设计递回函解题. 4,介绍图的定义与使用方法 5,介绍图走访演算法并用程式实作. 1,递回函 (1)递回函:介绍基本概以及递回程式的基本型式 (2)设计递回函:加总,阶乘,最大公因,费氏 (3)介绍河内塔问题与递回演算法 2,图(graph)演算法介绍 (1)介绍图的基本概,节点(vertex),边(edge) (2)介绍邻接矩阵(adjacency matrix):概介绍,定义语法 (3)介绍无向图,有向图 (4)图形走访演算法 (5)Euler 一笔画问题与解题演算法 1,能解递回函的基本概. 2,针对符合递回特性的问题,能设计解题程,并化为可的演算法. 3,能针对已确定之演算法,以程式语言实作. 4,能解图概以及相关名词 5,能使用邻接矩阵作为图的资结构 6,能设计图走访演算法. 1,口头问答 2,课堂观察 3,随堂或课后作业 4,上机实作
主
题
项
目
教学目标
评方式
1
贰,课程规划
课程内容 一,递回函(200 分钟) (1)递回函:介绍基本概以及递回程式 的基本型式 (2)设计递回函:加总,阶乘,最大公因 ,费氏 (3)介绍河内塔问题与递回演算法 二,图资结构与演算法(200 分钟) (1)介绍图的基本概,节点(vertex),边 能指标 E-2-3 能决定适合使用科技的时机,并选择适 当工具与科技资源解决同任务和问 题. E-3-4 能针对同的研究主题,选择与应用适 当资讯工具和资源.
E-4-3 能正确选择并运用资讯科技工具,以进 研究,分析资讯,解决问题和判断决 策. (edge) (2)介绍邻接矩阵(adjacency matrix):概介 F-4-3 能使用资讯科技和同侪,专家或他人共 绍,定义语法 同解决问题,以编辑,综合,制作和传 (3)介绍无向图,有向图 播资讯,作品模型与其他创作. (4)图形走访演算法 (5)Euler 一笔画问题与解题演算法
2
,教学计画
一,递回函介绍 第 1 节教学活动 1, 复习函的定义 时间 10 分 明 1,复习函定义语法以及呼叫方法
传回资型态 函名称 (输入…) { …. return 传回值; }
主程式的呼叫方法 …. D = 函名称 ( 1, 2, …) …. 教师可视情况提示之前曾写过的函程式,恢学生记忆 2,以计算次方的程式为,复习之前学过的函观 int Npower (int { int i, result; n, int exp)
result = 1; for (i=0; i
2, 何为递回函
10 分
1,函呼叫自己就称为递回(recursion),具有此特性的 函称为递回函(recursive function),如以下是一 段递回函程式码: void ff(int a) { cout << a; ff (a); //递回呼叫 } 以上的程式码,会造成无穷呼叫,直到系统堆叠满溢 (stack overflow),教师可在黑板上模拟呼叫过程,或是实 际写一个程式执. 因此递回函一定要含中止条件,程式修正如下 void ff(int a) { if (a==0) return;
递回函明
//终止条件
else { cout << a; ff (a-1); //递回呼叫 } } 请学生观察, a=5,请问递回呼叫会发生几次 上 程式执后萤幕结果为何 2,假设 Npower(2, 4)可以计算 24, 25 = Npower(2, 5) 也可视为 2 * Npower(2,4) 3,次方运算函可改写成递回函 int Npower2(int n, int exp) { if (exp==0) return 1; else return n * Npower2(n, exp-1); } 如计算 2 的 5 次方 cout << Npower2(2, 5)