《折半查找算法及程序实现教案》由会员分享,可在线阅读,更多相关《折半查找算法及程序实现教案(8页珍藏版)》请在金锄头文库上搜索。
1、对分查找算法及程序实现对分查找算法及程序实现设计者 边楚女单位浙江省瑞安中学 教材浙江教育出版社 算法与程序设计 适用范围 选修模块 课时一 课时 联系方式一、一、设计设计思想思想对分查找是计算机科学中的一个基础算法。对于一个基础算法的学习,同样可以让学生在一定的情境下,经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场,同时激活学生的思维,引导学生去探索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程,本课分解了问题动作,找出问题的全部可能情况,在对全部可能情况总结归纳的情况下,得出对分查找的基础算法,最后在程序中得到实现,从而使学生
2、建立起对分查找算法形成的科学逻辑结构。二、教材分析二、教材分析本本课课的的课课程程标标准内容:准内容:(一)计算机解决问题的基本过程(1)结合实例,经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程,认识算法和程序设计在其中的地位和作用。(三)算法与问题解决例举 C 查找、排序与问题解决(2)通过实例,掌握使用数据查找算法设计程序解决问题的方法。本本课课的的 学科教学指学科教学指导导意意见见 内容:内容:基本要求:1.初步掌握对分查找算法。2.初步掌握对分查找算法的程序实现。教材内容教材内容:第二章 算法实例 2.4.3 对分查找和第五章 5.4 查找算法的程序实现,课题定为对分查找
3、算法及程序实现,安排两个课时,第一课时着重是对分查找算法的形成和初步程序实现,第二课时利用对分查找算法解决一些实际问题的程序实现,本教学设计为第一课时。从课程标准和学科教学指导意见对本课教学内容的要求来看,要求学生能从问题出发,通过相应的科学步骤形成对分查找的算法。对学生来说,要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象,明确对分查找算法结构和对分查找的意义。三、学情分析三、学情分析学生应该已经掌握程序设计的基本思想,掌握赋值语句、选择语句、循环语句的基本用法和 VB 基本操作,这节课学生可能会遇到的最大问题是:如何归纳总结对分查找解决不同情况问题的一般规律,鉴于此
4、,在教学中要积极引导学生采取分解动作、比较迁移等学习策略。四、教学目四、教学目标标知知识识与技能与技能:理解理解对分查找的概念和特点,通过分步解析获获取取对分查找的解题结构,初步掌握对分查找算法的程序实现。过过程与方法程与方法:通过分析分析多种不同的可能情况,逐步归纳归纳对分查找的基本思想和方法,确定确定解题步骤。情感情感态态度与价度与价值观值观: :通过实践体体验验科学解题的重要性,增增强强效率意识和全局观念,感受感受对分查找算法的魅力,养成养成始终坚持、不断积累才能获得成功的意志品质。五、重点五、重点难难点点教学重点和难点:分解并理解对分查找的过程。六、教学策略与手段六、教学策略与手段1、
5、教学线索:游戏引领-提出对分查找原理- 解析对分查找的算法特征-实践解决问题。2、学习线索:分解问题-归纳问题-实践提升,在三个阶段的不断推进中明确对分查找算法,总结规律。七、教学七、教学过过程程1、新、新课导课导入入( (1) )热热身身:游戏(2 分钟)教师展示一件特色物品,让一个学生来猜这个物品的价格,其他学生只需要根据这个学生猜出的价格提示“高了”或是“低了”,如果学生能在五次内猜对这个物品的价格,就把这件物品“赠送”给他。( (2) )讨论讨论: :你觉得怎么样猜可以猜的快一点呢?有什么技巧吗?你从这个游戏当中得到什么启示?(3 分钟)( (3)教)教师师引引导导: :这个世界不是缺
6、少问题,而是缺少发现,其实在这个游戏的背后,含有一个非常经典的算法。引出对分查找的的概念。2、新、新课课: :教学步教学步骤骤一:分析一:分析对对分分查查找的原理和思想。找的原理和思想。(3 分钟)(1)对分查找是效率很高的查找方法,但被查找的数据必须是有序的。(2)首先将查找的数与有序数组内处于中间位置的数据比较,如果中间位置上的数与查找的数不同,根据有序性,就可确定应该在数组的前半部分还是后半部分继续查找。(3)在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。教学步教学步骤骤二:分解二:分解对对分分查查找算法找算法(5 分钟)假假设设: :用一个数组 d(1 to 10)来存放
7、升序的元素序列,用 i 表示查找范围的起始位置的下标,j 表示终止位置的下标,mid 表示中间位置元素的下标。(1(第一种情况:要找的第一种情况:要找的值值在后半部分;在后半部分;以查找键 KEY=48 为例分析第一次比较:范围 d(1)d(10),mid= (1+10)2, d(mid)key then j=mid-1用分支结构实现。18171510ijmi dd(4)d(3)d(2)d(1)1817d(4)d(3)ijmid18d(4)i,j,mid52484535272218171510d(10)d(9)d(8)d(7)d(6)d(5)d(4)d(3)d(2)d(1)ijmi d(2)继
8、续进行重复查找的条件: ij,用循环结构实现。教学步教学步骤骤五:构建五:构建对对分分查查找的流程找的流程图图教学步教学步骤骤六:六:对对分分查查找算法的初步程序找算法的初步程序实现实现。 。教师事先设计好 Vb 窗体,学生只需要在相应的程序体输入代表算法思想的关键语句。附主要程序体:Private Sub Command2_Click()Dim key As Integer, mid As Integer, i As Integer, j As Integerkey = Val(Text1.Text)i = 1: j = 10Do While i d(mid),那么 i=mid+1 否则 j
9、=mid+15、重复上述的 3,4 步,直到 i 超出 j(或者理解为 i=j 不成立,所以不能用 for next,而要用 do while 语句)6、如果有找到 key,那执行第 4 步(1)步后应该输出找到的位置后退出程序,如果不退出,说明 key 没有找到,所以在相应位置要输出“找不到”。教学步教学步骤骤七:七:评评价。价。评价学生的程序实现情况,并讨论或实践问题:如果是降序序列,该怎么样改动程序?如果序列元素不是 10 个,而是 100 个或更多呢?教学步教学步骤骤八:八:总结总结提升。提升。(1)由于对分查找过程中的每次比较都能使得搜索空间减半,对分查找将不会使用超过 log2n
10、次比较来找到目标值。(2)提升对分查找算法的实际意义:同学们可能还没有意识到二分查找是多么高效,那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字,二分查找可以让你不超过 21 次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序,那么你可以在 35 步以内找到任何人。八、作八、作业业: :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,-92、设计一个能用对分查找算法思想解决的实际问题。【参考资料参考资料】网网络络文章文章类类http:/