第8课《快速定位查找算法》课件信息技术九下

1、说课人：说课人：XXXXXX1 1、教材分析、教材分析2 2、教学目标、教学目标 3 3、教学重点与难点、教学重点与难点 4 4、教学方法、教学方法5 5、教学过程、教学过程教材分析教材分析 第二章 算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是顺序查找和对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。 从课程标准和学科教学指导意见对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。对学生来说，要求通过这一课时的学习能初步掌握

2、或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。教学目标教学目标 知识和能力：通过实例使学生理解对分查找的特点及设计思想，并学会用对分查找来解决一些实际问题。重视知识的迁移，会将对分查找运用到学习的其它地方，提高学生解决问题的能力。 过程和方法：由小游戏引入，通过实例的渐进学习，学生分组合作交流讨论，理解对分查找的方法。 情感态度和价值观：激发学生学习兴趣和主动思维，并能初步利用这一方法解决一些同类型的实际生活问题。教学重点与难点教学重点与难点 教学重点：教学重点： 初步掌握顺序查找和对分查找算法的特点。 教学难点：教学难点： 能理解对分查找算法的设计思想。教学

3、方法教学方法 图示法，在对算法进行讲解时给出流程 图。 提问法：让同学们补充程序设计。 教学过程教学过程 1 1、新课导入、新课导入 （1）热身）热身：游戏 展示一件物品，让一个学生来猜这个物品的价格，给出提示：在1到50之内，我将根据这个学生猜出的价格提示“高了”或是“低了”。 （2）讨论：）讨论： 你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？你从这个游戏当中得到什么启示？ （3）教师引导：）教师引导： 这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个非常经典的算法。相信通过这节课的学习就会找到更快的方法来猜出数字了！实例实例学车问答 http:/ 学车问题 开车问题 学

4、车怎么办？驾校大全 http:/ 中国驾校报名 考试 理论学习 地址 介绍英格驾考 http:/ 驾考单机版软件车类小游戏 http:/ 学车小游戏大全2 2、新课：、新课： 教学步骤一：解释查找的概念和查找的方法有教学步骤一：解释查找的概念和查找的方法有顺序查找和二分查找顺序查找和二分查找 查找的概念 一种数据查询的技术 在数组变量中存储的一批数据中找出一个特定的数据. 查找的分类：顺序查找和二分查找 1、 通过图示得出算法的描述： 取得要找的元素值key 从数组的第i个位置开始找(i开始等于1) 如果d(i)=key ,则输出i,并退出循环 否则i指向下一个位置,继续找 如果找到数组末尾还

5、没找到,则输出找不到. 2、构建顺序查找的流程图流程图，把它转化为程序，让同学们补充完整整个程序。 3、对顺序查找进行分析，得出顺序查找所需的平均查找次数为（n+1）/2教学步骤二：分解顺序查找算法教学步骤二：分解顺序查找算法实例实例教学步骤三：分解对分查找算法教学步骤三：分解对分查找算法 解释二分查找的条件和思想解释二分查找的条件和思想 一、二分查找的先决条件 表中结点按关键字有序，且顺序（一维数组）存储。 二、二分法思想：取中，比较 2 2、假设、假设：用一个数组d（1 to 10）来存放升序的元素序列，用low表示查找范围的起始位置的下标，high表示终止位置的下标,mid表示中间位置元

6、素的下标。 以查找键KEY=21为例分析 第一次比较：第一次比较： 范围d(1)d(11),mid=d(1+11)2)=56, d(mid)Key 所以可以确定接下来要找的范围是前半部分。 比较后high=mid-1 第二次比较：第二次比较： 范围d(1)d(5),mid=d(1+5)2)=19,d(mid)key，在左子表中继续 进行二分查找； 若r（mid）key，则在右子表中继续进行二分查找。构建二分查找的流程图流程图二分查找方法的初步程序实现教学步骤四：评价。教学步骤四：评价。 评价学生的程序实现情况，并讨论或实践问题：如果是降序序列，该怎么样改动程序？如果序列元素不是11个，而是10

7、0个或更多呢？教学步骤五：总结提升。教学步骤五：总结提升。 （1）由于二分查找过程中的每次比较都能使得搜索空间减半，二分查找将不会使用超过log2n次比较来找到目标值。 （2）提升二分查找算法的实际意义：同学们可能还没有意识到二分查找是多么高效，那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字，二分查找可以让你不超过21次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序，那么你可以在35步以内找到任何人。下一页页展示一件物品，让一个学生来猜这个展示一件物品，让一个学生来猜这个物品的价格，给出提示：在物品的价格，给出提示：在1到到50之内，之内，我将根据这个学生猜出的价格提示我

8、将根据这个学生猜出的价格提示“高了高了”或是或是“低了低了”。 29讨论：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？返回27363218d (1) d (2) d (3) d (4) 输入查找的元素值输入查找的元素值key=32i=1i=2i=3此时d(i)=key,数组中的第3个位置如果输入查找的元素值key=22i=1i=2i=3i=4i=527363218d (1) d (2) d (3) d (4) 此时i等于5,超过数组中元素个数,找不到返回Private Sub Command3_Click() Key = Val(Text2.Text)i = 1Do While If The

9、n Text3.Text = 在数组的第 + Str(i) + 个位置 Exit Do End IfLoopIf i = n + 1 Then Text3.Text = 在数组中没有找到 + Str(Key)End IfEnd Subd(i) = Keyi=i+1以n来表示数组中元素个数i= n开始i=1in thenif in then返回5 13 19 21 37 56 64 75 80 88 92lowmidhigh5 13 19 21 37lowhigh21 37lowhighmidmid21返回YYN开开始始i1,j10计算计算midd(mid)=key?Ni= =mid+1J= =

10、mid-1N继续查继续查找？找？输出输出“未找未找到到”Y输出找到的输出找到的信息信息结束结束ijmid=(i+j)2d(mid) high Then 没有查找到没有查找到 index = -1 Exit Sub End If mid = (low + high) 2 取查找区间的中点取查找区间的中点 If Key = a(mid) Then 查找到，返回下标查找到，返回下标 index = mid Exit Sub ElseIf Key a(mid) Then 查找区间在上半部分查找区间在上半部分 high = mid - 1 Else low = mid + 1 查找区间在下半部分查找区间

11、在下半部分 End If Call birSearch(a, low, high, Key, index) 递归调用查找函数递归调用查找函数 End Sub调用方法：调用方法： Private Sub Command1_Click() Dim a(11) a(1) = 5: a(2) = 13: a(3) = 19: a(4) = 21: a(5) = 37 a(6) = 56: a(7) = 64: a(8) = 75: a(9) = 80: a(10) = 88: a(11) = 92 Dim ind As Integer Call birSearch(a, LBound(a), UBou