资源简介

第三课：精准的查找算法
教学内容：
查找算法是我们日常生活中经常使用的一种算法。本课选取了其中最常用顺序查找法和二分查找法。通过运用所学的两种查找算法解决问题，学生不仅能强化对这些算法的理解，还能提升自身的逻辑思维能力。
教学目标：
掌握顺序查找法和二分查找法的算法原理。
选择合适的算法解决简单问题,
教学重点：
(1)顺序查找法的原理。
(2)二分查找法的原理。
教学难点：
选择合适的算法解决简单问题
教学过程：
情境导入
师：同学们，在上课之前我们来玩个游戏吧，猜整数游戏，我们来找几个个同学，分别来扮演出题人、证明人和竞猜人，有没有同学想主动参与的？请举手。
生：……
师：好，大家都很积极踊跃的参与，角色已经选好了，接下来我们来看一下游戏规则，请看大屏幕：出题人从 1~100中选择一个整数，并告诉证明人，而竞猜人则尝试猜出选定的整数。谁能用最少的次数猜中该数，谁就是赢家。
生：……
师：游戏中猜整数的过程就是查找的过程，查找的次数与查找算法直接相关。查找算法是在数据中查找特定元素或满足特定条件的算法，其目标是高效地找到数据中的位置或确认数据是否存在，主要包括顺序查找法、二分查找法等。
二：顺序查找法
师：猜整数游戏设定了从 1~100整数的数据序列，出题人从中随机选取一个数字作为目标。对于竞猜人而言，为了确保能够排查每一个可能的数字直至找到正确答案，最直接且直观的策略是从数字1开始逐一猜测，持续进行直到成功猜中目标整数。我们来看一下这个游戏的算法，请看大屏幕。
师：接下来请大家根据这个流程图，补全顺序查找法猜整数游戏的程序，并且调试运行。
师：巡视指导
师：在理想情况下，运用顺序查找法猜整数游戏需要几次可以猜中 在最差情况下，需要几次可以猜中
生：……
师：大家的想法很好，除了从开头的数字开始查找之外，顺序查找法也可以从末尾的数字开始，请同学们修改程序，实现从数字100开始自动查找的功能。
生：
师：顺序查找法以简单直观和通用性强而著称。但在数据量较大时，查找效率相对较低。
三、二分查找法
师：在猜整数游戏中，为了确保能够快速猜中整数，竞猜人需要从序列的-端开始逐个猜测。为了提高该游戏的趣味性，将游戏规则修改为:每当竞猜人报出一个数字后，证明人会提供反馈，告诉竞猜人所猜的整数是比目标数高了还是低了。那么，竞猜人又该如何以最少的次数猜中目标数呢 接下来，请同学们通过小试身手来研究这个问题。
师：在1~100整数范围内，若目标数是59，最快多少次能猜中
竞猜人说出1~100之间的中间整数____。证明人回答“猜小了”猜数人舍弃所有比中间数小的数字。
2、竞猜人在剩下的数字中继续说出中间整数____。证明人回答“猜大了”，竞猜人再次舍弃所有比中间数大的数字。
3、继续重复以上步骤,直至找到目标数，总共猜了几次。
生：做题中……
师：由此可以看出，每次猜整数时都会舍弃一半的数据，这种算法被称为二分查找法。二分查找法，也称折半查找法，是一种在有序数据集中查找特定元素的算法。它通过不断缩小查找范围来提高效率，在计算机科学和数学领域都有广泛的应用。
师：同桌两人相互使用二分查找法尝试猜整数游戏，体会二分查找法的含义。接下来补全人机猜整数游戏的程序。我们从数字1~100范围内选择一个整数，让计算机来猜。补全下列程序，并调试运行。然后回答下面这个问题：二分查找法猜整数游戏在理想情况下，最少几次可以猜中 最差情况下，最多几次可以猜中
生：编写程序。
师：巡视指导。
师：与顺序查找算法不同，二分查找法要求待查找的数据必须是已经排序的序列，如1~100的整数序列，就是一个有序序列，因此可以应用二分查找法进行快速查找。
师：二分查找法因其高效性和出色的稳定性，在多个领域得到广泛应用。其核心思想就是一分为二。在实际操作中，我们经常利用这一思想，将复杂的大问题分解成一系列结构相似但规模更小的子问题，这些子问题相对简单，更易于解决。最终，将这些子问题的解整合起来，就能得到原问题的解。这种分解与整合的过程不仅降低了问题的复杂性，也提高了解决问题的效率。
四、查找算法的应用
师：某工厂生产了一批螺母，共计1000个。其中有一个螺母存在质量超标的情况。由于这批螺母的形状和大小完全一致，工厂需要寻找一个有效的方法来精准识别出这个质量异常的螺母。组内讨论是否可以利用一架天平找出质量异常的螺母？我们左边这部分同学使用顺序查找法，右边使用二分查找法，然后分别填写在最好和最坏情况下，两种算法找到质量异常的螺母分别比较了多少次
五、总结
无论是顺序查找法还是二分查找法，它们并无绝对的优劣之分，不应片面认为哪一种绝对优于另一种，这与排序算法的选择原则存在显著差异。排序算法的目标单一且明确，即实现数据的排序，因此必须根据任务的具体规模和需求选择最合适的算法不同算法间的性能差异往往十分显著。今天的课就到这里了，请大家做一下这两道题来巩固一下。
六、挑战自我
1、小睿有10张数字卡片，他想快速找出最小的一张，应用排序方法的一项是(）
A.顺序查找法
C.枚举算法
B.二分查找法
D.选择排序
2、在找出超重螺母的场景中，我们可以使用“三分法”的算法:先拿出一个螺母，将剩下的螺母平均分为3份，任取两份进行称量，可以大幅减少比较次数。根据以上说明，绘制出相应算法的流程图。

展开更多......

收起↑