资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,查找算法设计,说课人：,XXX,1,、教材分析,2,、教学目标,3,、教学重点与难点,4,、教学方法,5,、教学过程,目录,教材分析,第二章 算法实例,2.4.3,对分查找和第五章,5.4,查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是顺序查找和对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。,从,课程标准,和,学科教学指导意见,对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。,教学目标,知识和能力：通过实例使学生理解对分查找的特点及设计思想，并学会用对分查找来解决一些实际问题。重视知识的迁移，会将对分查找运用到学习的其它地方，提高学生解决问题的能力。,过程和方法：由小游戏引入，通过实例的渐进学习，学生分组合作交流讨论，理解对分查找的方法。,情感态度和价值观：激发学生学习兴趣和主动思维，并能初步利用这一方法解决一些同类型的实际生活问题。,教学重点与难点,教学重点：,初步掌握顺序查找和对分查找算法的特点。,教学难点：,能理解对分查找算法的设计思想。,教学方法,图示法，在对算法进行讲解时给出流程 图。,提问法：让同学们补充程序设计。,教学过程,1,、新课导入,（,1,）热身,：游戏,展示一件物品，让一个学生来猜这个物品的价格，给出提示：在,1,到,50,之内，我将根据这个学生猜出的价格提示“高了”或是“低了”。,（,2,）讨论：,你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？你从这个游戏当中得到什么启示？,（,3,）教师引导：,这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个非常经典的算法。相信通过这节课的学习就会找到更快的方法来猜出数字了！,实例,学车问答,学车问题 开车问题 学车怎么办？驾校大全,中国驾校报名 考试 理论学习 地址 介绍英格驾考,车类小游戏,学车小游戏大全,2,、新课：,教学步骤一：解释查找的概念和查找的方法有顺序查找和二分查找,查找的概念,一种数据查询的技术,在数组变量中存储的一批数据中找出一个特定的数据,.,查找的分类：顺序查找和二分查找,1,、通过图示得出算法的描述：,取得要找的元素值,key,从数组的第,i,个位置开始找,(i,开始等于,1),如果,d(i)=key,则输出,i,并退出循环,否则,i,指向下一个位置,继续找,如果找到数组末尾还没找到,则输出找不到,.,2,、构建顺序查找的,流程图,，把它转化为程序，让同学们补充完整整个程序。,3,、对顺序查找进行分析，得出顺序查找所需的平均查找次数为（,n+1,）,/2,教学步骤二：分解顺序查找算法,实例,教学步骤三：分解对分查找算法,解释二分查找的条件和思想,一、二分查找的先决条件,表中结点按关键字有序，且顺序（一维数组）存储。,二、二分法思想：,取中，比较,2,、假设,：用一个数组,d,（,1 to 10,）来存放升序的元素序列，用,low,表示查找范围的起始位置的下标，,high,表示终止位置的下标,mid,表示中间位置元素的下标。,以查找键,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,个，而是,100,个或更多呢？,教学步骤五：总结提升。,（,1,）由于二分查找过程中的每次比较都能使得搜索空间减半，二分查找将不会使用超过,log2n,次比较来找到目标值。,（,2,）提升二分查找算法的实际意义：同学们可能还没有意识到二分查找是多么高效，那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字，二分查找可以让你不超过,21,次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序，那么你可以在,35,步以内找到任何人。,下一页,猜数字：,展示一件物品，让一个学生来猜这个物品的价格，给出提示：在,1,到,50,之内，我将根据这个学生猜出的价格提示“高了”或是“低了”。,29,讨论：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？,返回,顺序查找,27,36,32,18,d(1),d(2),d(3),d(4),输入查找的元素值,key=32,i=1,i=2,i=3,此时,d(i)=key,数组中的第,3,个位置,如果输入查找的元素值,key=22,i=1,i=2,i=3,i=4,i=5,27,36,32,18,d(1),d(2),d(3),d(4),此时,i,等于,5,超过数组中元素个数,找不到,返回,转化成程序,Private Sub Command3_Click(),Key=Val(Text2.Text),i=1,Do While,If Then,Text3.Text=,在数组的第+,Str(i)+,个位置,Exit Do,End If,Loop,If i=n+1 Then,Text3.Text=,在数组中没有找到+,Str(Key),End If,End Sub,d(i)=Key,i=i+1,以,n,来表示数组中元素个数,i=n,开始,i=1,in then,返回,5 13 19 21 37 56 64 75 80 88 92,low,mid,high,5 13 19 21 37,low,high,21 37,low,high,mid,mid,21,返回,Y,Y,N,开始,i,1,j,10,计算,mid,d(mid)=key?,N,i,=,mid+1,J,=,mid-1,N,继续查找？,输出“未找到”,Y,输出找到的信息,结束,ij,mid=(i+j)2,d(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,查找区间在下半部分,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),UBound(a),21,ind),Print ind,End Sub,作业：,1,、以下的三组元素序列能采用二分查找法来查找吗？,(1)19,，,33,，,35,，,53,，,56,，,67,，,78,，,99(2)53,，,35,，,67,，,78,，,56,，,99,，,33,，,19(3)99,，,67,，,56,，,45,，,33,，,10,，,9,，,1,，,0,，,-9,2,、设计一个能用二分查找算法思想解决的实际问题。,谢谢！,
展开阅读全文