《2022年折半查找算法及程序实现教案》由会员分享，可在线阅读，更多相关《2022年折半查找算法及程序实现教案（8页珍藏版）》请在金锄头文库上搜索。
1、学习必备欢迎下载折半查找算法及程序实现一、教材分析教学重点：以图示法方式，演示折半查找算法的基本思想。教学难点：由折半查找算法的思想到程序代码编写的转换，尤其是其中关键性语句的编写是教学中的难点。二、学情分析学生应该已经掌握程序设计的基本思想，掌握赋值语句、 选择语句、 循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。三、教学目标知识与技能：理解对分查找的概念和特点， 通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现。过程与方法：通过分析多种不同
2、的可能情况，逐步归纳对分查找的基本思想和方法，确定解题步骤。情感态度与价值观： 通过实践体验科学解题的重要性，增强效率意识和全局观念，感受对分查找算法的魅力，养成始终坚持、不断积累才能获得成功的意志品质。四、教学策略与手段1、教学线索：游戏引领 - 提出对分查找原理 - 解析对分查找的算法特征- 实践解决问题。2、学习线索：分解问题 - 归纳问题 - 实践提升，在三个阶段的不断推进中明确对分查找算法，总结规律。五、教学过程精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页学习必备欢迎下载1、新课导入（1）热身：游戏（ 2 分钟）找同
3、学上来找一本上千页电话册里面的一个名字。( 课程导入我写的不是很详细，自己设计哦 ) （2）教师引导：所以我不希望只有他一个人体验这种方便，我们教室里还有一大帮人，其实这种什么不止用于查找电话铺，还可以运用到实际生活中，教室里有这么多人，坦白说，按学校的老方法一个人一个人的数，对所有老师来说都及其费力，那我们想想，是不是数数2368，这样好点对吗？。不要小看这种想法，他其实是非常棒的，他能把解决问题的时间缩短一半，因此我们提出了这种算法2、新课：首先我们一起来看一看折半查询算法中的“折半”的含义。师：何为折半呢？生：减半；打一半的折扣。例如，我手里拿着一根绳子， 现在我们来进行折半试验， 首先
4、拿住绳子的两个端点，然后从中点的位置进行对折， 这样绳子就缩短为原来长度一半，然后将一半的绳子继续执行与刚才相同的操作，使得绳子的长度逐渐的缩短，直到绳子长度短得不能再进行折半了。师：那什么时候就不能再折半了呢？生：即绳子的两个端点合二为一为止。折半查找算法的思想与绳子折半的过程基本相同。下面我们先通过图示来看看折半查找算法究竟是什么？教学步骤二：分解对分查找算法（5 分钟）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页学习必备欢迎下载假设一个从小到大排列的数据存放在一个数组中Data(10) ，而查找数据存放在变量 x 中。如
5、图 1 所示，橙色方框的代表的是查询数据x，每个浅兰色方框代表的是数组中的每个元素，框内显示的数据是每个数组元素对应的下标（序号），整排的浅兰色方框就可以看成整个数组，即待查数据表（数组元素表）。图一第一步：就像抓住绳子的两端一样， 首先设立两个标记Low、High 分别来标识查询区间的低端和高端，即数组元素的下标，如图1 所示。师：对于初始查询区间，它们是多少呢？生：Low=0 ， High=10 第二步：取区间的中点标记Mid，如图 2 所示。师：查询区间的中点为多少？（这个地方，有的学生可能直接说出下标值，所以要提醒学生让中点和两个端点相联系，即用端点表示中点）生：Mid=(Low+Hi
6、gh)/2 师：中点位置上的数据为什么？( 提醒学生数据是放在数组Data 中的) 生：Data( Mid) x 0 1 2 3 4 5 6 7 8 9 10 Low High 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页学习必备欢迎下载第三步：判断中点位置上的数据Data( Mid) 与要查找数x 是否相等，如何相等，则找到，并结束查找；如果不相等，就执行第四步。师：这个判断语句如何写呢？生：if Data( Mid)=x then print “x 找到”结束查找end if 第四步：如果不相等，那么对查询区间进行折半操作
7、。师：那如何折半是从中点处向左侧折半还是向右侧折半？（这是整个折半查询进行下去的关键所在，所以一定要让学生自己学会判断）由于待找数据表是从小到大排列的，而且区间中点位置上的数据Date(Mid)也知道，所以，通过 Data(Mid) 与 x 的比较，看一看， x 比 Data(Mid) 大还是小，就可以判断出 x 落在中间数 Data(Mid) 的左侧还是右侧， 从而判断出向左还是向右折半。师：那么，判断语句如何写呢？生：if Data(Mid)High，停止折半查询。教学步骤四：对各种情况进行归纳总结。（1）x 与 data(mid) 的大小比较影响 i,j的取值的规律：i 的取值规律： i
8、f data(mid)x then high=mid-1 用分支结构实现。(2) 继续进行重复查找的条件： low high ，用循环结构实现。教学步骤五：构建对分查找的流程图0 1 2 3 4 5 6 7 8 9 10 Low High 0 1 2 3 4 5 6 7 8 9 10 Low High 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页学习必备欢迎下载教学步骤六：对分查找算法的初步程序实现。教师事先设计好 Vb窗体，学生只需要在相应的程序体输入代表算法思想的关键语句。附主要程序体：Private Sub Comman
9、d2_Click() Dim x As Integer, mid As Integer, low As Integer, high As Integer x = Val(Text1.Text) low = 0: high = 10 Do While low = high mid = (low + high) 2 If data(mid) = x Then Text2.Text = 找到了，是第 & mid & 个 Exit Sub End If If data(mid) x Then low = mid + 1 Else high = mid - 1 End If Loop Text2.Tex
10、t = 找不到 Y Y N 开始low1,high10 计算 mid data(mid)=x? N lowmid+1 highmid-1 N 继续查？输出 “ 未找到 ”Y 输出找到的信息结束lowhigh mid=(low+high)2 data(mid)data(mid),那么 low=mid+1 否则 high=mid+1 5、重复上述的 3,4 步，直到 low 超出 j( 或者理解为 low=high 不成立，所以不能用 for next,而要用 do while语句）6、如果有找到 x, 那执行第 4 步（1）步后应该输出找到的位置后退出程序，如果不退出，说明x 没有找到，所以在相
11、应位置要输出“找不到”。折半查找算法基本思想总结（2 分钟）对一有序数据表， 首先从初始查找区间开始， 取出区间中点位置上的数据与要查询数据进行比较，若相等，则查找成功，并结束查询；否则，将当前查找区间缩小一半。在新的查询区间内，同样取出区间中点位置上的数据与要查询数据进行比较，若相等，则查询成功，并结束查询，否则将新的查询区间再次缩小一半。然后继续采用相同的方法，直到查找数据成功或者查询区间不能再折半（即查询失败）为止教学步骤七：评价。评价学生的程序实现情况， 并讨论或实践问题： 如果是降序序列， 该怎么样改动程序？如果序列元素不是10 个，而是 100个或更多呢？教学步骤八：总结提升。（1
12、）由于对分查找过程中的每次比较都能使得搜索空间减半，对分查找将不会使用超过 log2n 次比较来找到目标值。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页学习必备欢迎下载（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，-9 2、设计一个能用对分查找算法思想解决的实际问题。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页
