版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、折半查找算法及程序实现一、教材分析教学重点:以图示法方式,演示折半查找算法的基本思想。教学难点:由折半查找算法的思想到程序代码编写的转换,尤其是其中关键性语句的编写是教学中的难点。二、学情分析学生应该已经掌握程序设计的基本思想,掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作,这节课学生可能会遇到的最大问题是:如何归纳总结对分查找解决不同情况问题的一般规律,鉴于此,在教学中要积极引导学生采取分解动作、比较迁移等学习策略。三、教学目标知识与技能:理解对分查找的概念和特点,通过分步解析获取对分查找的解题结构,初步掌握对分查找算法的程序实现。过程与方法:通过分析多种不同的可能情况,逐步归纳对
2、分查找的基本思想和方法,确定解题步骤。情感态度与价值观:通过实践体验科学解题的重要性,增强效率意识和全局观念,感受对分查找算法的魅力,养成始终坚持、不断积累才能获得成功的意志品质。四、教学策略与手段1、教学线索:游戏引领-提出对分查找原理- 解析对分查找的算法特征-实践解决问题。2、学习线索:分解问题-归纳问题-实践提升,在三个阶段的不断推进中明确对分查找算法,总结规律。五、教学过程1、新课导入(1)热身:游戏(2分钟)找同学上来找一本上千页电话册里面的一个名字。(课程导入我写的不是很详细,自己设计哦)(2)教师引导:所以我不希望只有他一个人体验这种方便,我们教室里还有一大帮人,其实这种什么不
3、止用于查找电话铺,还可以运用到实际生活中,教室里有这么多人,坦白说,按学校的老方法一个人一个人的数,对所有老师来说都及其费力,那我们想想,是不是数数2368,这样好点对吗?。不要小看这种想法,他其实是非常棒的,他能把解决问题的时间缩短一半,因此我们提出了这种算法2、新课:首先我们一起来看一看折半查询算法中的“折半”的含义。师:何为折半呢?生:减半;打一半的折扣。例如,我手里拿着一根绳子,现在我们来进行折半试验,首先拿住绳子的两个端点,然后从中点的位置进行对折,这样绳子就缩短为原来长度一半,然后将一半的绳子继续执行与刚才相同的操作,使得绳子的长度逐渐的缩短,直到绳子长度短得不能再进行折半了。师:
4、那什么时候就不能再折半了呢?生:即绳子的两个端点合二为一为止。折半查找算法的思想与绳子折半的过程基本相同。下面我们先通过图示来看看折半查找算法究竟是什么?教学步骤二:分解对分查找算法(5分钟)假设一个从小到大排列的数据存放在一个数组中Data(10),而查找数据存放在变量x中。如图1所示,橙色方框的代表的是查询数据x,每个浅兰色方框代表的是数组中的每个元素,框内显示的数据是每个数组元素对应的下标(序号),整排的浅兰色方框就可以看成整个数组,即待查数据表(数组元素表)。x012345678910LowHigh图一第一步:就像抓住绳子的两端一样,首先设立两个标记Low、High分别来标识查询区间的
5、低端和高端,即数组元素的下标,如图1所示。师:对于初始查询区间,它们是多少呢?生:Low=0 , High=10第二步:取区间的中点标记Mid,如图2所示。师:查询区间的中点为多少?(这个地方,有的学生可能直接说出下标值,所以要提醒学生让中点和两个端点相联系,即用端点表示中点)生:Mid=(Low+High)/2师:中点位置上的数据为什么?(提醒学生数据是放在数组Data中的) 生:Data( Mid) 012345678910MidLowHigh第三步:判断中点位置上的数据Data( Mid)与要查找数x是否相等,如何相等,则找到,并结束查找;如果不相等,就执行第四步。师:这个判断语句如何写
6、呢?生:if Data( Mid)=x thenprint “x找到”结束查找end if第四步:如果不相等,那么对查询区间进行折半操作。师:那如何折半是从中点处向左侧折半还是向右侧折半?(这是整个折半查询进行下去的关键所在,所以一定要让学生自己学会判断)由于待找数据表是从小到大排列的,而且区间中点位置上的数据Date(Mid)也知道,所以,通过Data(Mid)与x的比较,看一看,x比Data(Mid)大还是小,就可以判断出x落在中间数Data(Mid)的左侧还是右侧,从而判断出向左还是向右折半。师:那么,判断语句如何写呢?生:if Data(Mid)High,停止折半查询。01234567
7、8910LowHigh教学步骤四:对各种情况进行归纳总结。(1)x与data(mid)的大小比较影响i,j的取值的规律:i的取值规律:if data(mid)x then high=mid-1用分支结构实现。(2)继续进行重复查找的条件: lowhigh,用循环结构实现。教学步骤五:构建对分查找的流程图教学步骤六:对分查找算法的初步程序实现。YYN开始low1,high10计算middata(mid)=x?Nlowmid+1highmid-1N继续查?输出“未找到”Y输出找到的信息结束lowhighmid=(low+high)2 data(mid)x?教师事先设计好Vb窗体,学生只需要在相应的
8、程序体输入代表算法思想的关键语句。附主要程序体:Private Sub Command2_Click()Dim x As Integer, mid As Integer, low As Integer, high As Integerx = Val(Text1.Text)low = 0: high = 10Do While low = highmid = (low + high) 2If data(mid) = x ThenText2.Text = 找到了,是第 & mid & 个Exit SubEnd IfIf data(mid) data(mid),那么low=mid+1 否则 high=
9、mid+15、重复上述的3,4步,直到low超出j(或者理解为low=high不成立,所以不能用for next,而要用do while语句)6、如果有找到x,那执行第4步(1)步后应该输出找到的位置后退出程序,如果不退出,说明x没有找到,所以在相应位置要输出“找不到”。折半查找算法基本思想总结(2分钟)对一有序数据表,首先从初始查找区间开始,取出区间中点位置上的数据与要查询数据进行比较,若相等,则查找成功,并结束查询;否则,将当前查找区间缩小一半。在新的查询区间内,同样取出区间中点位置上的数据与要查询数据进行比较,若相等,则查询成功,并结束查询,否则将新的查询区间再次缩小一半。然后继续采用相同的方法,直到查找数据成功或者查询区间不能再折半(即查询失败)为止教学步骤七:评价。评价学生的程序实现情况,并讨论或实践问题:如果是降序序列,该怎么样改动程序?如果序列元素不是10个,而是100个或更多呢?教学步骤八:总结提升。(1)由于对分查找过程中的每次比较都能使得搜索空间减半,对分查找将不会使用超过log2n次比较来找到目标值。(2)提升对分查找算法的实际意义:同学们可能还没有意识到二分查找是多么高效,那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字,二分查找可以让你不超过21次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序,那
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 外研版小学三年级上学期期中英语试题与参考答案
- 人教版英语初三上学期期中试卷及答案指导(2024年)
- 2024年住房城乡建委质监站事业单位招聘招考31人真题题库附参考答案
- 《犹太人的教育》课件
- 《齿轮齿条气动执行器》征求意见稿
- 《广告招贴设计》课件
- 《用友渠道政策》课件
- 对公开型劫持人质案件处置战术课件
- 《物业催费宝典》课件
- 《店长心态培训》课件
- 匠心筑梦勇闯生涯-大学生职业生涯规划智慧树知到期末考试答案2024年
- 树立正确就业观课件
- 车间统计员培训课件
- 心理问题学生包保制度
- 西门子变频器技术入门及实践 课件全套 第1-11章 绪论、交流异步电动机- 变频器操作实践
- 尔雅(中华诗词之美)课后章节测试答案+期末考试
- 酒店行业法律法规培训课件
- 稽查安全工作总结
- 校园餐饮的行业分析
- 甘薯缺素症状与施肥技术
- 全国一级学会、协会目录
评论
0/150
提交评论