（2021新教科版）高中信息技术必修一 4.3非数值计算（第1课时）ppt课件.pptx

1、非 数 值 计 二分查找二分查找 算 教学目标：教学目标： 1.1.了解算法设计中的分治思想。了解算法设计中的分治思想。 2.2.运用二分查找解决实际问题。运用二分查找解决实际问题。 3.3.体验二分查找算法解决实际问题的过程。体验二分查找算法解决实际问题的过程。 教学重点教学重点: : 二分查找的适用条件，教学难点是代码的实现部分。二分查找的适用条件，教学难点是代码的实现部分。 任务一、生活中的分治问题任务二、巧查监控寻找失主 项目：生活中的算法 目标任务 活动1：查找漏扫图书 活动2：查找英文单词 活动3：查找假币 任务一、生活中的分治问题 为了更好地学习英语，小为了更好地学习英语，小I

2、I和小和小T T去阅览室借去阅览室借 了了2020本英文原著，由于扫码时有一本漏扫引起了本英文原著，由于扫码时有一本漏扫引起了 警报声。警报声。 活动1：查找漏扫图书 方法一：一本本的查找显然效率低下。方法一：一本本的查找显然效率低下。 方法二：将方法二：将2020本书分成了两份，第一份经过警报器没响，又本书分成了两份，第一份经过警报器没响，又 把剩下的一份分成两份，拿出一份接着测试把剩下的一份分成两份，拿出一份接着测试这样就可以这样就可以 快速找到漏扫图书。快速找到漏扫图书。 活动1：查找漏扫图书 活动2：查找英文单词 小小I I和小和小T T在阅读在阅读老人与海老人与海 小小I I：“A

3、A man can be destroyed but not man can be destroyed but not defeateddefeated”你知道你知道defeatdefeat是什么意思吗？是什么意思吗？ 小小T T：我刚买了一本新字典有：我刚买了一本新字典有23462346页呢，我来帮页呢，我来帮 你查一下。你查一下。 方法：方法：根据根据首字母首字母D D大概确定第一次先翻到字典的六分之一处，再根据大概确定第一次先翻到字典的六分之一处，再根据 看到的首字母确定下一个位置，如果首字母相同，则查看第二个字看到的首字母确定下一个位置，如果首字母相同，则查看第二个字 母母，依此类推，

4、直到查出单词。，依此类推，直到查出单词。 活动2：查找英文单词 活动3：查找假币 小小I I在阅览室读到了有趣的故事：国王有在阅览室读到了有趣的故事：国王有1818枚金币，其枚金币，其 中掺进去一枚较轻的假币，要求数学家使用一个没有砝码中掺进去一枚较轻的假币，要求数学家使用一个没有砝码 的天平三次找到假币。的天平三次找到假币。 第二次： 3 3 第三次： 1 1 1 18 第一次：6 6 6 方法：方法：先先将将1818枚金币分成三组，标记好编号枚金币分成三组，标记好编号A123456A123456、B123456B123456、C123456.C123456.选出其选出其 中中abab两组进

5、行第一次称量。称量结果有三种情况：两组进行第一次称量。称量结果有三种情况：a a组重、一样重、组重、一样重、b b组重。如果组重。如果 两组一般重，则假币在两组一般重，则假币在c c组中，如果组中，如果a a组重，则假币在组重，则假币在b b组，反之则在组，反之则在a a组。总之经组。总之经 过第一次称量我们就可以确定假币所在的分组。假设是过第一次称量我们就可以确定假币所在的分组。假设是c c组，第二次称量可以将组，第二次称量可以将 c1c2c3c1c2c3和和c4c5c6c4c5c6分别放在天平的两边。假币在轻的一侧。第三次称量在三枚重选分别放在天平的两边。假币在轻的一侧。第三次称量在三枚重

6、选 择任意两枚放置在天平两侧，一样重则剩余的是假币，不一样重则较轻的是假币。择任意两枚放置在天平两侧，一样重则剩余的是假币，不一样重则较轻的是假币。 活动3：查找假币 二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数 列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点 元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可 以将查找区间缩小一半。以将查找

7、区间缩小一半。 二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效 率。率。 二分法 凡治众如治寡，分数是也。凡治众如治寡，分数是也。 孙子兵法孙子兵法 分治策略 快递送达过程、营销策略、上传下载中的断点续传、通信原理中的分组交换快递送达过程、营销策略、上传下载中的断点续传、通信原理中的分组交换 小小I I和小和小T T在阅览室角落里捡到了一本无名的在阅览室角落里捡到了一本无名的 读书笔记，如何在一个小时读书笔记，如何在一个小时36003600秒的监控录像中秒的监控录像中 快速找到失主？快速找到失主？ 任务二、巧

8、查监控寻找失主 二分查找（折半查找） 区间区间1360013600，假设目标值是，假设目标值是18661866，二分查找的次数，二分查找的次数? ?边界值的变化规律？边界值的变化规律？ 次数次数左边界左边界右边界右边界中间值中间值比较结果比较结果 11360018001800180018661800186627001866 3180126992699225022502250186622501866 4180122492249202520252025186620251866 5180120242024191219121912186619121866 61801191119111856185618

9、5618661856186618841866 8185718831883187018701870186618701866 9185718691869186318631863186618631866 10186418641869186618661866=18661866=1866 活动1：分析问题 数据量大、有序数列 0101 次数：log2n 0202 二分查找（折半查找） 活动2：完成二分法流程图 请根据数据分析补充二分法流程图 次数次数左边界左边界右边界右边界中间值中间值比较结果比较结果 11360018001800180018661800186627001866 318012699269

10、9225022502250186622501866 4180122492249202520252025186620251866 5180120242024191219121912186619121866 618011911191118561856185618661856186618841866 8185718831883187018701870186618701866 9185718691869186318631863186618631e-6:while abs(b-a)1e-6: x0=( x0=(a+ba+b)/2 )/2 if f(a) if f(a)* *f(x0)0:f(x0)0: b=x0 b=x0 if f(b) if f(b)* *f(x0)0:f(x0)0: a=x0 a=x0 if f(x0)=0: if f(x0)=0: break break print(print(解为解为:,x0):,x0) input(input(运行完毕，请按回车键退出运行完毕，请按回车键退出.).) 课后，请利用今天所学的分治策略以及二分 查找算法解决生活中的问题