资源简介

(共36张PPT)
第5单元 第1课
图书的查找算法
（湘科版）五年级
下
1
核心素养目标
3
新知讲解
5
拓展延伸
7
板书设计
2
新知导入
4
课堂练习
6
课堂总结
课后作业
8
01
核心素养目标
信息意识
计算思维
数字化学习与创新
信息社会责任
分析算法效率对系统资源消耗的影响，理解“时间换空间”的优化思想，能通过高效算法快速处理海量数据。
能通过修改代码参数，验证二分查找中数据集有序性的必要性，会用调试工具观察查找过程中中间位置的变化规律。
会计算特定数据集下两种算法的最大/最小比较次数，掌握二分查找的"分治策略"，理解线性时间复杂度。
通过对比顺序查找与二分查找的特点，体会数据结构对算法效率的重要性，理解数据有序性对查找效率的影响。
02
新知导入
活动背景
生活中，我们经常会遇到一些查找问题。比如，在《新华字典》中查找生字，在班级花名册中查找某位同学的姓名，在手机通讯录中查找手机号等。在图书借阅系统中，输入书名、图书编码或作者姓名，计算机就会帮我们快速查找想要的图书。那么，计算机是如何实现查找的呢？
计算机的查找逻辑本质上是对人类智慧的延伸——用结构化存储 和数学规律 替代了手工翻找的低效过程。
02
新知导入
活动目标
1、了解查找的基本种类和方法。
2、理解顺序查找和二分查找算法的基本思想。
3、体验二分查找算法的程序实现。
02
新知导入
03
新知讲解
一、查找的基本种类
从被查找对象的角度来看，如果被查找对象是无序的，称为无序查找。如果被查找对象本身是有序的，称为有序查找。
03
新知讲解
下面两种查找，哪种是有序查找，哪种是无序查找？
开动脑筋
左侧的洗牌动作代表扑克牌处于随机无序状态，属于无序查找
右侧的小男孩旁边的对话框显示中英文单词的对应关系是有序查找。
03
新知讲解
二、查找的基本方法
查找的算法有很多种，生活中常见的有顺序查找算法和二分查找算法。
◆顺序查找
顺序查找算法是一种简单的查找算法，既可用于无序查找，也可用于有序查找，但查找效率比较低。其基本过程是：从第一个对象开始，逐一查找，直到找到符合条件的对象或找遍全部对象。
03
新知讲解
采用顺序查找法，从左至右逐一查找和比较，记录查找数据。
探究实践
03
新知讲解
查找编号为“6”的书，进行了 次比较。
查找编号为“5”的书，进行了 次比较。
查找编号为“2”的书，进行了 次比较。
从10本不同的书里找1本书，最少需要 次比较，最多需要 次比较。
探究实践
1
5
10
1
10
03
新知讲解
◆二分查找算法
对于有序对象，我们可以采用二分查找算法，通过逐步缩小查找范围的过程，大大提高了查找效率。
03
新知讲解
（1）用下式计算中间位置:中间位置=(首位置+尾位置)-2。如果计算结果为非整数，取整数部分。
（2）将编号“16”与中间位置6的编号“14”进行比较。16>14，将查找范围缩小到位置6的右侧。
（3）将编号“16”与中间位置9的编号“18”进行比较。16<18，将查找范围缩小到位置9的左侧。
（4）将“16”与中间位置7的编号“16”进行比较。两者相等，查找完成。
03
新知讲解
在以上的例子中，使用顺序查找和二分查找各需要比较多少次才能找到编号为“20”的这本书
开动脑筋
查找方法 比较次数
顺序查找（从左至右） 10次
二分查找 3次
03
新知讲解
开动脑筋
1. 顺序查找
查找过程：从位置1开始逐个比较编号，直到找到目标编号20。
依次比较：3→7→9→11→13→14→16→17→18→20 （第10次命中）
比较次数：10次 （编号20位于第10个位置）
2. 二分查找
前提条件：数据已按升序排列（满足二分查找要求）。
查找过程：
第1次比较：中间位置6（编号14），14 < 20 → 向右半部分继续查找。
第2次比较：中间位置9（编号18），18 < 20 → 向右半部分继续查找。
第3次比较：中间位置10（编号20），命中目标。
比较次数：3次
03
新知讲解
二分查找算法的基本思想是在一组有序的数据中，通过将目标数据与中间位置的数据进行比较，可将待查找的范围缩小为之前的一半，直到找到要查找的数据，或者查找范围被缩小为0(没有找到)。
重点
03
新知讲解
三、二分查找算法的程序实现
用程序实现猜幸运数字游戏。在猜幸运数字游戏的程序中，为了简化程序，数的大小与数的位置相关联，如数字“1”排在第一位。
03
新知讲解
1、两人一组玩猜幸运数字游戏，规则如下:甲同学在纸上写下1~100中间的任意数字作为幸运数字，让乙同学来猜这个数字。乙同学用二分查找的方法猜测幸运数字,甲同学提示乙同学猜测的数字比幸运数字大或小，直到猜中为止。
探究实践
03
新知讲解
2、运行猜幸运数字游戏程序，与计算机玩猜幸运数字游戏。
探究实践
03
新知讲解
03
新知讲解
3、修改查找范围，运行程序，记录不同查找范围下查找次数的变化。
查找范围大小（元素数量） 查找次数（比较次数） 关键操作说明
10 4 每次折半，最多需 log2(10)≈3.32 → 4次
20 5 log2(20)≈4.32 → 5次（向上取整）
50 6 log2(50)≈5.64 → 6次
100 7 log2(100)≈6.64 → 7次
200 8 log2(200)≈7.64 → 8次
500 9 log2(500)≈8.96 → 9次
04
课堂练习
一、选择题
1、二分查找算法的前提条件是什么？（ ）
A. 数据必须存储在链表中 B. 数据必须是无序的
C. 数据必须是有序的 D. 数据必须全部是数字
2、在一个包含10个元素的有序数组中，二分查找最多需要多少次比较？( )
3次 B. 4次 C. 5次 D. 10次
3、下列哪种场景最适合使用二分查找？( )
A. 在未排序的购物清单中找商品
B. 在按姓名排序的电话簿中查号码
C. 在随机洗牌的扑克牌中找特定花色
D. 在无序的班级名单中查找学生
C
B
B
04
课堂练习
4、图书馆有10本书按编号从小到大排列（1,3,5,7,9,11,13,15,17,19），用二分法找编号13的书，需要比较几次（ ）
A. 1次 B. 2次 C. 3次 D. 4次
5、小明在玩具箱里找红色乐高积木，他从第一个玩具开始一个一个检查，直到找到红色积木。这种查找方法叫什么？（ ）
A. 快速查找 B. 顺序查找 C. 密码查找 D. 魔法查找
二、判断题
1、顺序查找算法可以用于链表结构的数据，但二分查找不能直接用于链表。（ ）。
D
√
B
04
课堂练习
三、操作题
动手制作“有序魔法书
任务：剪下10张纸片，分别写上数字：6、2、9、15、4、12、7、1、10、5。
将这些数字按 从小到大排列 ，用胶水粘成一行，制作成“魔法书页”。用“二分查找小秘籍”找到数字7。
第1步：找到中间的数字（如果偶数个，选左边）。
第2步：如果中间数=7，成功！如果中间数<7，向右找；如果中间数>7，向左找。
重复直到找到7，记录比较次数。
05
拓展延伸
计算机的“烹饪步骤”
算法是解决问题的明确指令集合，如同菜谱指导烹饪。例如：导航软件中的路径规划算法（输入起点终点，输出最优路线）、短视频推荐算法（分析用户行为，输出个性化内容）。算法的五大特性：有穷性、确定性、可行性、输入、输出。
05
拓展延伸
分治算法
将大问题拆解为相似小问题，分别解决后合并结果。经典案例：归并排序（将数组拆分成单元素再合并排序）、快速排序（选基准值分左右区间）。应用场景：大规模数据排序、地图导航中的区域路径规划。
05
拓展延伸
自我复制的魔法
递归是函数调用自身的过程，依赖内存栈临时保存状态。例如：计算斐波那契数列（F(n)=F(n-1)+F(n-2)）、遍历文件夹目录树。注意：递归需设置终止条件，否则会导致栈溢出（如无限循环调用）。
05
拓展延伸
贪心策略的取舍
每一步选择局部最优解，期望达到全局最优。例如：零钱兑换（优先用最大面额硬币）、哈夫曼编码（构建最优前缀树）。局限性：贪心策略未必全局最优，如旅行商问题（TSP）中可能得到较差解。
05
拓展延伸
连接万物的纽带
图论算法处理节点与边的关系。经典算法：广度优先搜索（BFS）找最短步数、深度优先搜索（DFS）解决迷宫问题。现实应用：社交网络好友推荐（六度空间理论）、物流网络优化（最小生成树）。
05
拓展延伸
数字世界的守护者
加密算法保障信息安全。对称加密（AES：加密解密同一密钥）速度快，非对称加密（RSA：公钥加密私钥解密）更安全。应用场景：HTTPS通信、比特币交易中的SHA-256哈希算法。
06
课堂总结
1
引入新知内容
图书的查找算法
2
学习查找的基本种类
3
学习查找的基本方法
4
完成课题练习
5
进行相关知识拓展
1
2
3
4
5
07
板书设计
图书的查找算法
1、进行新知引入
2、学习查找的基本种类
3、学习查找的基本方法
4、完成课堂练习
5、进行知识拓展
课后作业。
1、二分查找算法的具体应用。
08
课后作业
1、采用二分查找算法，从“1、2、3、4、5、6、7、8、9、10”中查找一个数，最少比较次数为 ，最多比较次数为 。
在 1到10的有序数组 中使用二分查找：
最少比较次数：1次
（当目标值恰好是中间元素时，例如查找数字5或6，第一次比较即命中。）
最多比较次数：4次
（例如查找数字10：需比较5→8→9→10，共4次。）
08
课后作业
2、二分查找算法中的二分思想在生活中也有类似的应用。假如有 20枚相同的硬币，其中有一枚因质量不合格，比其他的硬币轻一些，想一想如何用一台天平快速地找出那枚不合格的硬币。
从 20枚硬币 中找出质量不合格的硬币，最少需要 3次称量。
第一次称量：将20枚硬币分为 7枚、7枚、6枚，称量前两组7枚。若两边平衡 ，不合格硬币在剩下的6枚中。若一边较轻/较重 ， 不合格硬币在该边的7枚中。
第二次称量：
如果剩余6枚 ， 分成 2枚、2枚、2枚，称量前两组2枚。如果剩余7枚 ， 分成 3枚、3枚、1枚，称量前两组3枚。
第三次称量：
对剩余2~3枚称量，直接比较单枚或两两对比，最终确定不合格硬币。
https://www.21cnjy.com/recruitment/home/fine

展开更多......

收起↑