《对分查找算法及程序实现》由会员分享，可在线阅读，更多相关《对分查找算法及程序实现（7页珍藏版）》请在金锄头文库上搜索。
1、对分查找算法及程序实现设计者边楚女单位浙江省瑞安中学教材浙江教育出版社 算法与程序设计合用范畴选修模块学时一学时联系方式一、设计思想对分查找是计算机科学中的一种基本算法。对于一种基本算法的学习,同样可以让学生在一定的情境下,经历分析问题、拟定算法、编程求解等用计算机解决问题的基本过程。本堂课以一种游戏暖场,同步激活学生的思维,引导学生去摸索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的所有也许状况,在对所有也许状况总结归纳的状况下,得出对分查找的基本算法，最后在程序中得到实现,从而使学生建立起对分查找算法形成的科学逻辑构造。二、教材分
2、析本课的课程原则内容:（一)计算机解决问题的基本过程（1）结合实例，经历分析问题、拟定算法、编程求解等用计算机解决问题的基本过程,结识算法和程序设计在其中的地位和作用。（三）算法与问题解决例举C 查找、排序与问题解决（)通过实例，掌握使用数据查找算法设计程序解决问题的措施。本课的学科教学指引意见内容:基本规定：.初步掌握对分查找算法。2.初步掌握对分查找算法的程序实现。教材内容:第二章 算法实例 .4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个学时，第一学时着重是对分查找算法的形成和初步程序实现，第二学时运用对分查找算法解决某些实际问题的程序实现,本教
3、学设计为第一学时。从课程原则和学科教学指引意见对本课教学内容的规定来看，规定学生能从问题出发，通过相应的科学环节形成对分查找的算法。对学生来说，规定通过这一学时的学习能初步掌握或理解对分查找的前提条件、解决问题的对象,明确对分查找算法构造和对分查找的意义。三、学情分析学生应当已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生也许会遇到的最大问题是：如何归纳总结对分查找解决不同状况问题的一般规律，鉴于此,在教学中要积极引导学生采用分解动作、比较迁移等学习方略。四、教学目的知识与技能:理解对分查找的概念和特点,通过度步解析获取对分查找的解题构造,初步掌
4、握对分查找算法的程序实现。过程与措施:通过度析多种不同的也许状况,逐渐归纳对分查找的基本思想和措施,拟定解题环节。情感态度与价值观:通过实践体验科学解题的重要性,增强效率意识和全局观念,感受对分查找算法的魅力,养成始终坚持、不断积累才干获得成功的意志品质。五、重点难点教学重点和难点:分解并理解对分查找的过程。六、教学方略与手段、教学线索:游戏引领-提出对分查找原理- 解析对分查找的算法特性-实践解决问题。、学习线索：分解问题-归纳问题-实践提高,在三个阶段的不断推动中明确对分查找算法，总结规律。七、教学过程1、新课导入(1)热身：游戏（2分钟)教师展示一件特色物品，让一种学生来猜这个物品的价格
5、,其她学生只需要根据这个学生猜出的价格提示“高了”或是“低了”，如果学生能在五次内猜对这个物品的价格，就把这件物品“赠送”给她。（)讨论：你觉得怎么样猜可以猜的快一点呢?有什么技巧吗?你从这个游戏当中得到什么启示?(分钟)(3)教师引导:这个世界不是缺少问题，而是缺少发现,其实在这个游戏的背后，具有一种非常典型的算法。引出对分查找的的概念。2、新课：教学环节一：分析对分查找的原理和思想。（3分钟）(1)对分查找是效率很高的查找措施,但被查找的数据必须是有序的。（2)一方面将查找的数与有序数组内处在中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性,就可拟定应当在数组的前半部分还是
6、后半部分继续查找。（3)在新拟定的范畴内,继续按上述措施进行查找,直到获得最后成果。教学环节二:分解对分查找算法（分钟)假设:用一种数组d( t10）来寄存升序的元素序列,用表达查找范畴的起始位置的下标,j表达终结位置的下标,id表达中间位置元素的下标。52484535272218171510midi=jd(10)d(9)d(8)d(7)d(6)d(5)d(4)d(3)d(2)d(1)（1） 第一种状况：要找的值在后半部分；以查找键KEY=48为例分析第一次比较：范畴（1)d（10),md （1+10)2， d（mid)ey因此可以拟定接下来要找的范畴是后半部分。比较后i=mdmidij52d
7、(10)48d(9)45d(8)35d(7)27d(6)第二次比较：范畴d（)d（0),md(6+0)2，d(i)Key因此可以拟定接下来要找的范畴是后半部分。比较后:i=m+1midij52d(10)48d(9)第三次比较：范畴d(9)d（10)，id （910),d（mid)Ky ，找到了。思考:如果要找的是52? i,j，md分别是多少?这也阐明当ij的时候是查找的最后也许次数,这也是终结查找的一种核心条件。教学环节三:继续分解对分查找算法中涉及的其她状况。画一画:请仿照上面的画法，分别画出key=17和key=20的查找示意图。（2） 第二种状况：要找的值在前半部分；524845352
8、72218171510d(10）d(9)d(8)d(7)d(6)d(5)d(4)d(3)d(2)d(1)ijmid18171510jmidd(4)d(3)d(2)d(1)1718d (3)d(4)midji以查找键E=7为例分析:i成果分析：第一次比较后：j=mid-第二次比较后：i=m+1第三次比较后：找到了(3)第三种状况:要找的值找不到;以查找键KEY=为例分析：52484535272218171510d(10）d(9)d(8)d(7)d(6)d(5)d(4)d(3)d(2)d(1)ijmid18171510ijmidd(4)d(3)d(2)d(1)1817d(4)d(3)ijmid18
9、d(4)i,j,mid成果分析:第一次比较后:j=mid-1第二次比较后：i=mid+1第三次比较后:imid+第四次比较:i=j但是d（mid)ky,因此找不到。教学环节四：对多种状况进行归纳总结。(1）Key与d(mid)的大小比较影响i,j的取值的规律:的取值规律:i (mi）eyhen =md-用分支构造实现。（2)继续进行反复查找的条件:ij，用循环构造实现。教学环节五：构建对分查找的流程图YYN开始i1,j10计算midd(mid)=key?Nimid+1jmid-1N继续查找？输出“未找到”Y输出找到的信息结束ijmid=(i+j)2d(mid)key?教学环节六:对分查找算法的
10、初步程序实现。教师事先设计好Vb窗体，学生只需要在相应的程序体输入代表算法思想的核心语句。附重要程序体：Prvate Sb Command2_lik（) Dim key As Intege, mid ntegr, As tege, Integer ke Val(T1.Tt) = 1: j = 10 o Whie i j mi = (i + j) 2 Ifd(i) ky hen Tex2.Te = 找到了，是第 & mid& 个 Exit Sub End I f d(id) keyThen i d + Ee j= d - 1 Ed If Lo Txt.Text 找不到End Sb 程序阐明:1、
11、获得要查找的数据ky的值 ke= Vl(TextTet)2、i,j赋初值。 i = 1: 3、求id的值。id =(+) 2、分三种状况,（1）如果ky=d（mid),则如果d(mid） = ky那么Tx.Txt= 找到了，在第 + Str（md） + 个。(2）如果keyd(id)，那么i=md1 否则 j=mid+15、反复上述的3,4步，直到i超过j（或者理解为i不成立,因此不能用o ext,而要用do whe语句） 6、如果有找到ky,那执行第4步（)步后应当输出找到的位置后退出程序,如果不退出,阐明e没有找到,因此在相应位置要输出“找不到”。教学环节七：评价。评价学生的程序实现状况,
12、并讨论或实践问题：如果是降序序列，该怎么样改动程序?如果序列元素不是10个，而是00个或更多呢？教学环节八:总结提高。(1)由于对分查找过程中的每次比较都能使得搜索空间减半，对分查找将不会使用超过log2n次比较来找到目的值。()提高对分查找算法的实际意义:同窗们也许还没故意识到二分查找是多么高效，那不妨设想一下在一种涉及一百万个人名的电话簿中找一种名字,二分查找可以让你不超过2次就能找到指定的名字。如果你可以将世界上所有的人按照姓名排序,那么你可以在35步以内找到任何人。八、作业:、如下的三组元素序列能采用对分查找法来查找吗？(1) 1，3,3，53，5，7,7,99 (2)3,35,6,8,6，99，33，19()99,67，56，45,3,10,9,1，0，-2、设计一种能用对分查找算法思想解决的实际问题。【参照资料】网络文章类
