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

圻半查找算法及程序实现一、教材分析教学重点：以图示法方式，演示折半查找算法的范本思想。教学难点：由折半衣找算法的思悲到程序代码编写的转狭，尤其是其中关健性语句的编写是做学中的难点.二、学情分析学生应当巳经莺取程序设计的基本悬悬，驾取K值语句、逸舞语旬、循环语句的茶本用法和VB范本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同状况问题的一般规律.奘于此,在教学中要主动训导学生实行分解动作、比较迁移等学习策略.三、教学目标学问与技能：理*对分查找的概念和杵点，通过分步解析萩得对分杳找的解题结构，初步驾取对分杳找算法的程序实现.过程与方法：通过分析多料不同的可能状况，逐步归纳对分查找的井本愚虑和方法，确定解题步情居者法与价值观：通过实毁体验科学解题的篁要性，增加效率怠识和全局观念，感受对分支找算法的勉力，养成始终坚持、不断积累才能获得胜利的启志品质.四、教学策略与手段1、教学线索，弟戏引领提出对分叠找原理解析对分查找的算法转征一实晚解决问题.2、学习线索:分解问题归纳问题实我提升，在三个阶段的不断推动中明确对分叠找算法，总结规律.五、教学过程1、折课导入（1）热身：嬉戏（2分钟）找同学上来找一本上千页最里面的一个名字.（课程导入我写的不是很具体，自己设计*（2）老师引导：所以我不希望只有他一个人体&这种便利，我们教室里迁有一大精人，其实这种什么不止用于查找«,还可以运用到实际生活中，«室里有这么多人，坦白说，按学校的老方法一个人一个人的效，对全部老师来说都及其费劲，那我们想想，是不是敷数2368,这样好点对吗？不要小着这加意漆，他其实是转别棒的，他能把解决问题的时间缗短一半，因此我们提出了这种算法2、fr*t廿先我们一起来着一身折半查询算法中的“折半”的含义.卿：何为折半呢？生：半；打一半的折扣.例如，我手里拿着一根绳子，现在我们耒挑行圻半试黯.廿先拿住绳子的两个点，然后从中点的位置进行对折，这样绻子就缩短为原来长度一半，然后挣一半的绳子接并执行与刚才相同的操作，使得绳子的长度渐渐的维姐,直到绳子长度短得不能再进行圻半了.师I那什么时候就不能再折半了呢？生：即绻子的两个墙点合二为一为止.折半杳找算法的愿悬与绻子圻半的过桎蓄本相同。下面我们先通过图示来着身折半杳找算法原委是什么？敏学步夏二：分解对分去找算法（5分钟）假设一个从小到大排列的数据存放在一个数期中一Data（IO）,而查找数据存放在变量X中.如图1所示，糙色方根的代表的是查询数据X,每个浅兰包方根代表的是数姐中的每个元素，橇内显示的数据是每个数级元素对应的下标（序号），拄井的浅兰色方根就可以着或芸个数级，即待杳效帮表（数组元素*）tt1.owHigh图一第一步：就像抓住绻子的两端一样，首先设立两个标记1.。，、High分别来标识杳诗区问的低墙和南墙，即数Ia元素的下标，如图1所示.师：对于初始查询区间，它们是多少呢？生11.ow=OHigh=IO其次步：取区同的中点标记Mid,如图2所示.师：充询区网的中点为多少？（这个地方，有的学生可能干脆说出下标值,所以要提示学生让中点和两个端点相联系，即用墙点表示中点）生：Mid=（IxnH1.igh）/2中点位置上的数据为什么？（提示学生数据是放在数姐Data中的）生，Data（Mid）ttt1.owMidHigh第三步：推断中点位置上的数据Data(Mid)与要查找数X是否相等，如何相等，则找到，并结束有找；假如不相等，就执行第四步.师：这个推断语句如何写呢？生：ifData(Mid)=Xthenprint*x找到”结束查找endif第四步：假如不相等.那么对查询区间进行圻半操作.师，那如何折半一是从中点处向左倒圻半迁是向右倒折半？(这是蔓个折半查诗进行下去的关健所在，所以肯定要让学生自己学会推断)由于待找数据表是从小到大排列的，而且区向中点位量上的数据Date(Mid)也知道.所以，通过Data(Mid)与X的比较，着一着X比Data(Mid)大还是小,就可以推断出X落在中网数Data(Mid)的左倒还是右倒，从而推断出向左还是向右圻半.婶：那么，推断语句如何写呢？生：ifData(Mid)<xthen说同X比Data(Mid)大.且数据表是从小到大扑列的.从而推断出X落在右例.所以从中点处向右值折半.师：如图3所示，视察新充询区间，发觉商墙标记没有改变，而低*标记交了，那低标记1.OW为多少呢？生：我们来看图2,由于中点位量上的数据巳经被杳询过，所以，新查询区同内的数据就不能再包含它，1.oIr就得比Mid多1.即：1.ow=Mid+1.tt1.owHighIse说明X比Data(Mid)小，所以就向左侧圻半，如图4所示，视察新区间，发觉低电标记没有改变面商墙标记交了.同样道理，新交询区间内不能包含Mid对应的数据，全部High比Mid小1,即】High=Mid-1endif笫五步：执行其次、三、四步表.师：假如始终没有找到，那么什么时候不再进行折半查找呢？(提示学生意一想绳子圻半的状况)m11m11mhf-ifim11tt1.owHigh生：直至1.OW>High.停止折半杳询.教学步聚四，对各种状况进行归纳总结.(1)X与data(id)的大小比较影啕i,j的取值的视律：i的取值规律：ifdata(aid)<xthen1.ow=三id+1.j的取值规律：ifdata(aid)>xthenhigh=dd-1.用分支结构实现.(2)接着进行文查找的条件：IgWhigh,用循环结构实现.教学步及五：构建对分查找的流程图教学步豪六*对分左找算法的初步程序实现.I1起先老师率先设计好Vb曹休.学生只须要在相应的程序体输入代表算法思。的关笠语句.附主要程序体：PrivateSubCoamand2-C1.ick()DimXAsInteger,midAsInteger,1.owAsInteger,highAsIntegerx=Va1.(Text1.Text)1.ow=0:high=10DoWhi1.eIov<=highid=(1.ow+hi)2Ifdata(mid)=XThenText2Text=,找到了，是第'&mid&个ExitSubEndIfIfdata(nid)<XThen1.ow=aid+1E1.sehigh三aid-1EndIf1.oopTxt2.Text=找不到EndSub程序说明：1、获得要衣我的数据X的值X=Va1.(Text1.Text)2、i,jK初值.1S=1：high=103、求mid的值.mid=(1.ov+high)24、分三种状况.(D假如x=dataQid),X!1R如data(aid)=x那么Text2Text=找到了，在第+Str(aid)+个，(2)俵如x>data(aid).那么IOW=Iidd+1否则hi=11id+1.5、发上述的3.4步，直到IOW超出j(或者理解为15K=high不成立，所以不能用fornext,而要用dowhi1.e语句)6、假如有找到X,那执行第4步(D步后应当*出找到的位置后退出程序,假如不退出，说明X没有找到，所以在相应位*旻输出“找不到”.折半米找算法基本思熊总结(2分钟)对一有序数据衰，首先从初始杳找区间起先，取出区网中点位史上的数据与要查询数据进行比较，着相等，则查找胜利.并结束查询；否则，将当苜查找区间缩小一半.在新的左询区阿内，同样取出区向中点位置上的数据与旻杳询数据进行比较，着相等，则杳诗胜利，并结束左沟，否则将新的叠沟区间再次缩小一半.然后接并果纳相同的方法，直到查找数据胜利或者去询区间不能再圻半(即查询失败)为止敏学步堂七：评价.讦价学生的程序实现状况，并探讨或实践问题：假如是降序序列，该怎么样改动程序？假如序列元素不是10个，而是100个或更多呢？做学步八：总结提升.(1)由于对分查找过程中的每次比较都能使得搜寻空间我半，对分杳找将不会运用超过1.og2n次比较来找到目标值.(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、设计一个能用对分查找算法思蹲解决的实际问题.