1、4.3非数值计算非数值计算 教学目标：教学目标： 1.了解算法设计中的分治思想。 2.运用二分查找解决实际问题。 3.体验二分查找算法解决实际问题的过程。 教学重点教学重点: : 二分查找的适用条件，教学难点是代码的实现部分。 教学过程教学过程: : 一、引入：一、引入： 任务一任务一 : :生活中的分治问题， 目的是帮助学生理解分治思想，并使用其解 决生活中的复杂问题。 任务一是生活中的分治问题，设置了三个活动分别是: 活动活动 1 1：查找漏扫图书。：查找漏扫图书。 为了更好地学习英语，小 I 和小 T 去阅览室借了 20 本英文原著，由于扫码 时有一本漏扫引起了警报声。如果你是管理员如何
2、快速找到漏扫图书？ 分析分析： （也可小组讨论）（也可小组讨论） 方法一：方法一：一本本的查找显然效率低下。 方法二：方法二：将 20 本书分成了两份，第一份经过警报器没响，又把剩下的一份 分成两份，拿出一份接着测试这样就可以快速找到漏扫图书。 活动活动 2 2：查找英文单词：查找英文单词。 （小组讨论后，找同学说出方法）（小组讨论后，找同学说出方法） 小 I 和小 T 在阅读老人与海 。小 I：“A man can be destroyed but not defeated”你知道 defeat 是什么意思吗？小 T：我刚买了一本新字典有 2346 页 呢，我来帮你查一下。如果你是小 T，如
3、何快速找到单词。 分析：分析： （组间讨论后找代表发言）（组间讨论后找代表发言） 方法方法：根据首字母 D 大概确定第一次先翻到字典的六分之一处，再根据看到 的首字母确定下一个位置， 如果首字母相同， 则查看第二个字母， 依此类推， 直到查出单词。 活动活动 3 3：查找假币。：查找假币。 小 I 在阅览室读到了有趣的故事：国王有 12 枚金币，其中掺进去一枚较轻 的假币，要求数学家使用一个没有砝码的天平三次找到假币。如果你是数学家， 如何按照要求找到假币。 不限次数的方法不限次数的方法： （提示）（提示）数学二分法也经常用到金币的故事，不过大多数 不限制次数，学生可以采用二分法来称量。先平均
4、分成两份，假币在较轻的一份 中，然后再把较轻的一份平分称量，以此类推。这一版本由于限制次数，难度 更高，更能体现分治策略。 解决方案解决方案： 先将18枚金币分成三组， 标记好编号A123456、 B123456、 C123456. 选出其中 ab 两组进行第一次称量。称量结果有三种情况：a 组重、一样重、b 组重。如果两组一般重，则假币在 c 组中，如果 a 组重，则假币在 b 组，反之则 在 a 组。总之经过第一次称量我们就可以确定假币所在的分组。假设是 c 组，第 二次称量可以将 c1c2c3 和 c4c5c6 分别放在天平的两边。假币在轻的一侧。第 三次称量在三枚重选择任意两枚放置在天
5、平两侧，一样重则剩余的是假币，不一 样重则较轻的是假币。 可以用图示表示为： 对分治策略进行总结对分治策略进行总结： 所谓分治就是分而治之， 将难以解决的原始问题划分 为若干子问题，对子问题进行求解，然后合并达成对原始问题的解决。正如孙子 兵法中所说：凡治众如治寡，分数是也。 二分查找法实际上就是分治策略的一种典型运用。二分查找法实际上就是分治策略的一种典型运用。 二、二分查找法：二、二分查找法： 二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数 列为例， 先以中点位置的元素作为比较对象， 如果要找的元素值小于该中点元素， 则将待查序列缩小为左半部分，否则为右半部分；每一次比
6、较后都可以将查找区 间缩小一半。 二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效 率。 在一个有在一个有 n n 个元素的有序序列中，利用二分查找大约需要个元素的有序序列中，利用二分查找大约需要 loglog2 2n n 次，但是次，但是， 二分法查找的前提条件是被查找的数据必须是有序的。二分法查找的前提条件是被查找的数据必须是有序的。 任务二：巧查监控寻找失主。任务二：巧查监控寻找失主。 小 I 和小 T 在阅览室角落里捡到了一本无名的读书笔记，如何在一个小时 3600 秒的监控录像中快速找到失主？ 方法：是先在一半的位置看看书是不是在那里，如果在将区间锁定在前半个 小时
7、，如果不在将区间锁定在后半个小时，然后继续选择中间位置排查，直到找 到失主。这时 候教师再引出这种查找的方式就是二分查找也叫折半查找。二分 查找的学习就是以查监控为主题任务展开。 活动 1：分析问题。查找区间为 13600 秒，假设目标值为 1866 秒，使 用二分查找的方法， 经过几次能完成查找？计算并记录每一步的边界值和中间值， 然后分析边界变化的规律。 分析如下：第一次左边界为 1、右边界 3600，中间值 1800，中间值小于目 标值，所以左边界移至中间值的右侧也就是 1801，右边界保持不变为 3600，这 时的中间值为 2700，中间值的计算方法两边界值相加整除二，如果学生对此有
8、疑惑，可以用十以内的数字加以说明。第 2 次的中间值大于目标值，所以右边界 移至中间值的左侧也就是 2699， 而左边界保持 1801 不变。 把所有的数据算下来， 直至得到结果。 规律总结：规律总结：中间值目标值，右边界移至中间值前一个值。中间值目标 值，左边界移至中间值后一个值。当然当中间值=目标值时查找就结束了。 次次 数数 左边界左边界右边界右边界中间值中间值比较结果比较结果 11360018001800180018661800186627001866 3180126992699225022502250186622501866 41801224922492025202520251866
9、20251866 5180120242024191219121912186619121866 6180 11911191118561856185618661856186618841866 81857188318831870187018701861870186 6 6 9185718691869186318631863186618631866 来源来源: :学科网学科网 ZXXKZXXK 10186418641869186618661866=18661866=1866 活动活动 2 2：完成二分法的流程图。：完成二分法的流程图。 活活 动动 3 3：根据流程图补充代码并调试运行程序。：根据流程图补充代码并调试运行程序。 程序代码：程序代码： x=int(input(请输入要查找的请输入要查找的 3600 以内的整数以内的整数:) step=0 flag1=1 flag2=3600 while(flag1x: flag2=mid-1 elif mid1e-6: x0=(a+b)/2 if f(a)*f(x0)0: b=x0 if f(b)*f(x0)0: a=x0 if f(x0)=0:来源:Zxxk.Com break print(解为:,x0) input(运行完毕，请按回车键退出.)
