折半查找算法及程序实现教案.doc

羇对分查找算法及程序实现袄虿设计者芇 边楚女肇单位肁浙江省瑞安中学 蒁教材肆浙江教育出版社算法与程序设计***适用范围蒂 选修模块衿课时聿一 @薁一、设计思想袈对分查找是计算机科学中的一个基础算法。对于一个基础算法的学****同样可以让学生在一定的情境下,经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场,同时激活学生的思维,引导学生去探索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程,本课分解了问题动作,找出问题的全部可能情况,在对全部可能情况总结归纳的情况下,得出对分查找的基础算法,最后在程序中得到实现,从而使学生建立起对分查找算法形成的科学逻辑结构。芆二、教材分析芄本课的课程标准内容:聿(一)计算机解决问题的基本过程(1)结合实例,经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程,认识算法和程序设计在其中的地位和作用。蚇(三)算法与问题解决例举C查找、排序与问题解决莆(2)通过实例,掌握使用数据查找算法设计程序解决问题的方法。莁本课的《学科教学指导意见》内容:螁基本要求:。。蒆教材内容:,课题定为对分查找算法及程序实现,安排两个课时,第一课时着重是对分查找算法的形成和初步程序实现,第二课时利用对分查找算法解决一些实际问题的程序实现,本教学设计为第一课时。螂从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看,要求学生能从问题出发,通过相应的科学步骤形成对分查找的算法。对学生来说,要求通过这一课时的学****能初步掌握或了解对分查找的前提条件、解决问题的对象,明确对分查找算法结构和对分查找的意义。芈三、学情分析葿学生应该已经掌握程序设计的基本思想,掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作,这节课学生可能会遇到的最大问题是:如何归纳总结对分查找解决不同情况问题的一般规律,鉴于此,在教学中要积极引导学生采取分解动作、比较迁移等学****策略。薆四、教学目标膂知识与技能:理解对分查找的概念和特点,通过分步解析获取对分查找的解题结构,初步掌握对分查找算法的程序实现。羀过程与方法:通过分析多种不同的可能情况,逐步归纳对分查找的基本思想和方法,确定解题步骤。芇情感态度与价值观:通过实践体验科学解题的重要性,增强效率意识和全局观念,感受对分查找算法的魅力,养成始终坚持、不断积累才能获得成功的意志品质。肈五、重点难点肅教学重点和难点:分解并理解对分查找的过程。袀六、教学策略与手段蒈1、教学线索:游戏引领---提出对分查找原理---解析对分查找的算法特征---实践解决问题。膈2、学****线索:分解问题---归纳问题---实践提升,在三个阶段的不断推进中明确对分查找算法,总结规律。蒆七、教学过程薂1、新课导入蒁(1)热身:游戏(2分钟)芇教师展示一件特色物品,让一个学生来猜这个物品的价格,其他学生只需要根据这个学生猜出的价格提示“高了”或是“低了”,如果学生能在五次内猜对这个物品的价格,就把这件物品“赠送”给他……。薃(2)讨论:你觉得怎么样猜可以猜的快一点呢?有什么技巧吗?你从这个游戏当中得到什么启示?(3分钟)芄(3)教师引导:这个世界不是缺少问题,而是缺少发现,其实在这个游戏的背后,含有一个非常经典的算法。引出对分查找的的概念。芀2、新课:莇教学步骤一:分析对分查找的原理和思想。(3分钟)羄(1)对分查找是效率很高的查找方法,但被查找的数据必须是有序的。螂(2)首先将查找的数与有序数组内处于中间位置的数据比较,如果中间位置上的数与查找的数不同,根据有序性,就可确定应该在数组的前半部分还是后半部分继续查找。聿(3)在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。蒇教学步骤二:分解对分查找算法(5分钟)莅假设:用一个数组d(1to10)来存放升序的元素序列,用i表示查找范围的起始位置的下标,j表示终止位置的下标,mid表示中间位置元素的下标。蒄螈52薇48螆45羁35袁27蚇22羂18蚃17蕿15蚇10莃mid肁i=莈j螇d(10)螄d(9)螃d(8)莁d(7)袆d(6)膅d(5)芁d(4)膀d(3)羆d(2)薆d(1)第一种情况:要找的值在后半部分;羃以查找键KEY=48为例分析罿第一次比较:肆范围d(1)~d(10),mid=(1+10)\2,d(mid)<Key蚃所以可以确定接下来要找的范围是后半部分。蒁比较后i=mid+1蚈膆肄mid膃i螁j芆52蒅d(10)羆48羅d(9)蚁45芁d(8)螈35蚄d(7)螁27蚂d(6)第二次比较:膆范围d(6)~d(10),mid=(6+10)\2,d(mid)<Key螇所以可以确定接下来要