4.3 非数值计算（二分查找）课件 -2023—2024学年高中信息技术教科版（2019）必修1

高中信息技术 必修1 数据与计算 4.3 非数值计算 第一课时 二分查找 1 学习目标 01 02 了解算法中的分治思想； 掌握运用二分查找解决实际问题； 03 在python中用二分法解决问题。 4.3 非数值计算 2 游戏导入 【寻找假币游戏】 ——在100个硬币中找出伪币 有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。 请同学们思考并讨论“如何快速找出假币”？ 3 游戏导入 【寻找假币游戏】 ——在100个硬币中找出伪币 以重量判断为例 重量轻的是假币 首先是将100个硬币分成两个50，使用天平进行衡量，然后确定伪币在比较轻的那50个里，接着再将50分成2个25，将25分成两个12和1个1，将12分成2个6，将6分成2个3，将3分成3个1，这样6次就可以找到伪币，比50次少很多。 4 游戏导入 【寻找假币游戏】 ——在100个硬币中找出伪币 以重量判断为例 重量轻的是假币 首先是将100个硬币分成两个50，使用天平进行衡量，然后确定伪币在比较轻的那50个里，接着再将50分成2个25，将25分成两个12和1个1，将12分成2个6，将6分成2个3，将3分成3个1，这样6次就可以找到伪币，比50次少很多。 算法：分治 5 项目内容 本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。 项目任务 任务一：巧翻字典 任务二：玩转“汉诺塔”游戏 本节任务 6 任务：巧翻字典 活动：统计查字典次数 查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本字典大约1000页，目标信息在第328页。请记录你翻页过程，和同学们比比，看谁翻的次数最少。 次数 翻至页码 下一步决策 第一次 第二次 第三次 第四次 第五次 …… 有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门技术， 更是一种能力，是算法思想的体现。 7 任务：巧翻字典 活动：统计查字典次数 次数 翻至页码 下一步决策 第1次 500 往前 1-499 第2次 250 往后 251-499 第3次 375 往前 251-374 第4次 312 往后 313-374 第5次 343 往前 313-342 第6次 327 往后 328-342 第7次 335 往前 328-334 第8次 331 往前 328-330 第9次 329 往前 328-328 第10次 328 策略 1 找到区间的中位数 策略 2 根据情况确定更精确的区间 8 知识探究：二分查找/折半查找 二分思想：将数列有序排列，采用跳跃的方式查找数据。 分治策略 将难以直接解决的大问题，分割成较小的同类问题 方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。 找一半 按照顺序找一半， 一比较，舍一半。 继续找一半， 一半又一半， 快速找答案！ 9 知识探究：二分查找/折半查找 左边界 flag1 右边界 flag2 目标数x 中间数 mid ！！！若中间数mid比目标数x大，则区间变为左半区间，右边界更新 左边界 flag1 右边界 flag2 目标数x 中间数 mid ！！！若中间数mid比目标数x小，则区间变为右半区间，左边界更新 10 知识探究：二分查找/折半查找 在有n个元素的有序序列中，利用二分查找大约需要log2n次。 n = 1000 需要10次 二分思想：将数列有序排列，采用跳跃的方式查找数据。 11 任务：巧翻字典 程序编写——补充程序 x = int(input('请输入要查找的数据：')) step = 0 #查找次数 flag1 = 1 #目标区域左边界 flag2 = 1000 #目标区域右边界 while flag1 <= flag2 : #区间左边界不大于右边界则执行 mid = (flag1 + flag2)//2 #表示区间中间值 //为整除 step = step + 1 #查找次数加1 if mid > x: #区域中间值大于目标数 flag2 = mid - 1 #范围往左侧区域找 = 右边界前移 elif mid < x: #区域中间值大于目标数 flag1 = mid + 1 #范围往右侧区域找 = 左边界后移 else: break print('查找次数为：',step) 12 任务：巧翻字典 x = int(in