山东省枣庄市第八中学东校区高中信息技术教科版（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在阅览室读到了有趣的故事：国王有12枚金币，其中掺进去一枚较轻的假币，要求数学家使用一个没有砝码的天平三次找到假币。如果你是数学家，如何按照要求找到假币。 不限次数的方法：（提示）数学二分法也经常用到金币的故事，不过大多数不限制次数，学生可以采用二分法来称量。先平均分成两份，假币在较轻的一份中，然后再把较轻的一份平分称量，以此类推。这一版本由于限制次数，难度更高，更能体现分治策略。 解决方案：先将18枚金币分成三组，标记好编号A123456、B123456、C123456.选出其中ab两组进行第一次称量。称量结果有三种情况：a组重、一样重、b组重。如果两组一般重，则假币在c组中，如果a组重，则假币在b组，反之则在a组。总之经过第一次称量我们就可以确定假币所在的分组。假设是c组，第二次称量可以将c1c2c3和c4c5c6分别放在天平的两边。假币在轻的一侧。第三次称量在三枚重选择任意