4.3非数值计算学案（第1课时）学案 2021-2022学年高中信息技术教科版（2019）必修1

4.3 《非数值计算—二分查找》任务单 学习目标： 1.了解算法设计中的分治思想。 2.运用二分查找解决实际问题。 3.体验二分查找算法解决实际问题的过程。 任务一 :课本P100. 活动1.假设一本字典有1000页，老师藏了一条秘密信息在其中一页。现在通过运行“找神秘信息.py”文件，找到相应页码中的这条信息！并告诉我你用几次找到的？ 活动2.假设信息在第328页。如何去找到该页的信息呢？请在表4.3.1中记录你的翻页过程。 知识点：二分查找法 二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半。 二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。 在一个有n个元素的有序序列中，利用二分查找大约需要_____次，但是，二分法查找的前提条件是被查找的数据必须是_________。 活动3.补充代码，调试运行。P102 任务二：巧查监控寻找失主。 小I和小T在阅览室角落里捡到了一本无名的读书笔记，如何在一个小时3600秒的监控录像中快速找到失主？ 活动1：完成二分法的流程图。 1. ______________________ 2. ______________________ 3. ______________________ 4. ______________________ 活动2：根据流程图补充代码并调试运行程序。 x=int(input("请输入要查找的3600以内的整数:")) step=0 flag1=1 flag2=3600 while(flag1<=flag2): mid=(flag1+flag2)//2 step=step+1 if___________: flag2=__________ elif mid<x: flag1=__________ else: break print("查找次数为：",step) input("运行完毕，请按回车键退出...") 拓展练习： 1.若提示还是高了，则第三次猜12，依次类推；……。这种每次缩小一