山东省枣庄市第八中学东校区高中信息技术教科版（2019）必修一 4.3非数值计算学案（第1课时）

4.3 非数值计算 学习目标： 1.了解算法设计中的分治思想。 2.运用二分查找解决实际问题。 3.体验二分查找算法解决实际问题的过程。 教学重点: 二分查找的适用条件，教学难点是代码的实现部分。 教学过程: 一、案例分析： 任务一 :生活中的分治问题，目的是帮助学生理解分治思想，并使用其解决生活中的复杂问题。 活动1：查找漏扫图书。 为了更好地学习英语，小I和小T去阅览室借了20本英文原著，由于扫码时有一本漏扫引起了警报声。如果你是管理员如何快速找到漏扫图书？ 方法：将20本书分成了两份，第一份经过警报器没响，又把剩下的一份分成两份，拿出一份接着测试……这样就可以快速找到漏扫图书。 活动2：查找英文单词。（小组讨论后，找同学说出方法） 小I和小T在阅读《老人与海》。小I：“A man can be destroyed but not defeated”你知道defeat是什么意思吗？小T：我刚买了一本新字典有2346页呢，我来帮你查一下。如果你是小T，如何快速找到单词。 方法：根据首字母D大概确定第一次先翻到字典的六分之一处，再根据看到的首字母确定下一个位置，如果首字母相同，则查看第二个字母……，依此类推，直到查出单词。 活动3：查找假币。 小I在阅览室读到了有趣的故事：国王有18枚金币，其中掺进去一枚较轻的假币，要求数学家使用一个没有砝码的天平三次找到假币。如果你是数学家，如何按照要求找到假币。 解决方案：先将18枚金币分成三组，标记好编号A123456、B123456、C123456.选出其中ab两组进行第一次称量。称量结果有三种情况：a组重、一样重、b组重。如果两组一般重，则假币在c组中，如果a组重，则假币在b组，反之则在a组。总之经过第一次称量我们就可以确定假币所在的分组。假设是c组，第二次称量可以将c1c2c3和c4c5c6分别放在天平的两边。假币在轻的一侧。第三次称量在三枚重选择任意两枚放置在天平两侧，一样重则剩余的是假币，不一样重则较轻的是假币。 二、二分查找法： 二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半。 二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找