第三课：精准的查找算法 教学内容： 查找算法是我们日常生活中经常使用的一种算法。本课选取了其中最常用顺序查找法和二分查找法。通过运用所学的两种查找算法解决问题，学生不仅能强化对这些算法的理解，还能提升自身的逻辑思维能力。 教学目标： 掌握顺序查找法和二分查找法的算法原理。 选择合适的算法解决简单问题, 教学重点： (1)顺序查找法的原理。 (2)二分查找法的原理。 教学难点： 选择合适的算法解决简单问题 教学过程： 情境导入 师：同学们，在上课之前我们来玩个游戏吧，猜整数游戏，我们来找几个个同学，分别来扮演出题人、证明人和竞猜人，有没有同学想主动参与的？请举手。 生：…… 师：好，大家都很积极踊跃的参与，角色已经选好了，接下来我们来看一下游戏规则，请看大屏幕：出题人从 1~100中选择一个整数，并告诉证明人，而竞猜人则尝试猜出选定的整数。谁能用最少的次数猜中该数，谁就是赢家。 生：…… 师：游戏中猜整数的过程就是查找的过程，查找的次数与查找算法直接相关。查找算法是在数据中查找特定元素或满足特定条件的算法，其目标是高效地找到数据中的位置或确认数据是否存在，主要包括顺序查找法、二分查找法等。 二：顺序查找法 师：猜整数游戏设定了从 1~100整数的数据序列，出题人从中随机选取一个数字作为目标。对于竞猜人而言，为了确保能够排查每一个可能的数字直至找到正确答案，最直接且直观的策略是从数字1开始逐一猜测，持续进行直到成功猜中目标整数。我们来看一下这个游戏的算法，请看大屏幕。 师：接下来请大家根据这个流程图，补全顺序查找法猜整数游戏的程序，并且调试运行。 师：巡视指导 师：在理想情况下，运用顺序查找法猜整数游戏需要几次可以猜中 在最差情况下，需要几次可以猜中 生：…… 师：大家的想法很好，除了从开头的数字开始查找之外，顺序查找法也可以从末尾的数字开始，请同学们修改程序，实现从数字100开始自动查找的功能。 生： 师：顺序查找法以简单直观和通用性强而著称。但在数据量较大时，查找效率相对较低。 三、二分查找法 师：在猜整数游戏中，为了确保能够快速猜中整数，竞猜人需要从序列的-端开始逐个猜测。为了提高该游戏的趣味性，将游戏规则修改为:每当竞猜人报出一个数字后，证明人会提供反馈，告诉竞猜人所猜的整数是比目标数高了还是低了。那么，竞猜人又该如何以最少的次数猜中目标数呢 接下来，请同学们通过小试身手来研究这个问题。 师：在1~100整数范围内，若目标数是59，最快多少次能猜中 竞猜人说出1~100之间的中间整数____。证明人回答“猜小了”猜数人舍弃所有比中间数小的数字。 2、竞猜人在剩下的数字中继续说出中间整数____。证明人回答“猜大了”，竞猜人再次舍弃所有比中间数大的数字。 3、继续重复以上步骤,直至找到目标数，总共猜了几次。 生：做题中…… 师：由此可以看出，每次猜整数时都会舍弃一半的数据，这种算法被称为二分查找法。二分查找法，也称折半查找法，是一种在有序数据集中查找特定元素的算法。它通过不断缩小查找范围来提高效率，在计算机科学和数学领域都有广泛的应用。 师：同桌两人相互使用二分查找法尝试猜整数游戏，体会二分查找法的含义。接下来补全人机猜整数游戏的程序。我们从数字1~100范围内选择一个整数，让计算机来猜。补全下列程序，并调试运行。然后回答下面这个问题：二分查找法猜整数游戏在理想情况下，最少几次可以猜中 最差情况下，最多几次可以猜中 生：编写程序。 师：巡视指导。 师：与顺序查找算法不同，二分查找法要求待查找的数据必须是已经排序的序列，如1~100的整数序列，就是一个有序序列，因此可以应用二分查找法进行快速查找。 师：二分查找法因其高效性和出色的稳定性，在多个 ... ...
~~ 已预览到文档结尾了 ~~
