第一节猜数“魔法”之线性查找 课件-2026-2027学年五年级上册信息科技川教版
|
20页
|
7人阅读
|
0人下载
精品
内容正文:
第二单元 算法“魔法”大赛
猜数“魔法”之线性查找
魔法学院·第一关:一张一张地找
川教版(2024)信息科技 · 五年级上册
2.1 猜数“魔法”之线性查找|猜数“魔法”之线性查找
教学提示:
本课路线:先会找,再会数
找到只是第一步,能说清“找了几次”才算真懂。
1. 说清过程
从第一个开始,逐个比较。
2. 数出次数
找到时一共比了几次。
3. 比较情况
最好、最坏分别几次。
4. 判断适用
什么样的数据适合这样找。
带着问题学:100个数里找最后一个,要比较多少次?
2.1 猜数“魔法”之线性查找|本课路线:先会找,再会数
教学提示:找到只是第一步,能说清“找了几次”才算真懂。;带着问题学:100个数里找最后一个,要比较多少次?
真实场景:在书架上找一本书
没有编号索引时,只能一排一排看过去。
图书馆书架前找书(示意图)
从第一本看起
一本一本看封面和书名。
逐本比较
和目标书名比,不一样就放下。
找到为止
找到就停,没找到就把这一排看完。
追问:这本书刚好是第一本,和刚好是最后一本,差别大吗?
2.1 猜数“魔法”之线性查找|真实场景:在书架上找一本书
教学提示:没有编号索引时,只能一排一排看过去。;追问:这本书刚好是第一本,和刚好是最后一本,差别大吗?
本课要解决的两个问题
从100张牌里找一张,怎样保证找得到,又数得清找了几次?
怎么找
从第一张开始,逐个与目标数比较,相等就停下。
怎么数
每比较一次记一次,找到时数到几就是几次。
怎么比
最好、最坏各要几次?数据变多会怎样?
先动手翻牌,再从翻牌的过程里总结方法。
2.1 猜数“魔法”之线性查找|本课要解决的两个问题
教学提示:从100张牌里找一张,怎样保证找得到,又数得清找了几次?;先动手翻牌,再从翻牌的过程里总结方法。
情境:100张牌里只有一张是目标数
不许看牌背的提示,只能一张一张翻——你打算怎么翻?
从第一张开始
按摆放顺序逐张比较,不跳、不乱、不回翻。
找到就停
相等就是找到了,继续翻只是浪费时间。
查完为止
翻到最后一张仍不等,说明没有这个数。
追问:翻到第2张就找到,还要不要把100张全翻完?
2.1 猜数“魔法”之线性查找|情境:100张牌里只有一张是目标数
教学提示:不许看牌背的提示,只能一张一张翻——你打算怎么翻?;追问:翻到第2张就找到,还要不要把100张全翻完?
线性查找的四个步骤
把“翻牌”写成别人也能照着做的步骤。
1
从第一张开始
把当前位置定在第一张牌,准备比较。
2
与目标数比较
看当前牌上的数是不是目标数。
3
相等就结束
是目标:找到,停止;不是:取下一张。
4
重复到查完
一直比较到最后一张,仍不等就是没有。
两个停止条件:找到、查完。少写一个,步骤就不完整。
2.1 猜数“魔法”之线性查找|线性查找的四个步骤
教学提示:把“翻牌”写成别人也能照着做的步骤。;两个停止条件:找到、查完。少写一个,步骤就不完整。
找 7:一张一张翻,数一数用了几次
每翻一张画一个“√”,找到时数到几,就是比较了几次。
顺序
翻到的数
比较结果
累计次数
第1张
3
3≠7,继续
1次
第2张
7
7=7,找到
2次
目标恰在第2张,比较2次;若在最后一张,要比较10次。
2.1 猜数“魔法”之线性查找|找 7:一张一张翻,数一数用了几次
教学提示:每翻一张画一个“√”,找到时数到几,就是比较了几次。;目标恰在第2张,比较2次;若在最后一张,要比较10次。
同样的10张牌,为什么次数不一样?
次数不由牌决定,而由目标数藏在第几张决定。
目标位置
比较次数
属于哪种情况
第1张
1次
最好情况
第2张
2次
较快
最后1张
10次
最坏情况
预设追问:目标在中间,大约要几次?(约一半,5次左右)
2.1 猜数“魔法”之线性查找|同样的10张牌,为什么次数不一样?
教学提示:次数不由牌决定,而由目标数藏在第几张决定。;预设追问:目标在中间,大约要几次?(约一半,5次左右)
数据变多,最坏要比较几次?
把次数算出来,才能比较“快”和“慢”。
数据个数 n
最坏比较次数
若每次比较用1秒
10
10次
10秒
100
100次
约1分40秒
1000
1000次
约16分钟
最坏次数等于数据个数:数据翻倍,最坏时间也翻倍。
2.1 猜数“魔法”之线性查找|数据变多,最坏要比较几次?
教学提示:把次数算出来,才能比较“快”和“慢”。;最坏次数等于数据个数:数据翻倍,最坏时间也翻倍。
线性查找的特点与适用场景
一种方法好不好,要看它用在什么数据上。
不要求有序
数据打乱也能查,这是它最大的优点。
逐个比较
从前往后,一个也不跳过。
数据少时够用
十几条数据,逐个找很快。
数据多时很慢
上千条数据,最坏要查上千次。
书包里找本子、抽屉里找笔,都是线性查找。
2.1 猜数“魔法”之线性查找|线性查找的特点与适用场景
教学提示:一种方法好不好,要看它用在什么数据上。;书包里找本子、抽屉里找笔,都是线性查找。
练一练:8个无序数中找5
按“从第一张开始”的顺序写,不要跳数。
数据:6、2、9、4、1、8、3、5
第1次比较:6 与 5,不等,继续
第5次比较:
找到时一共比较了几次:
再想一想:找最后一个数,最坏要几次?
同桌互查:比较顺序是否连续、次数是否数错。
2.1 猜数“魔法”之线性查找|练一练:8个无序数中找5
教学提示:按“从第一张开始”的顺序写,不要跳数。;同桌互查:比较顺序是否连续、次数是否数错。
本课要记住的三句话
怎么找
从第一张开始,逐个与目标数比较,不跳位。
何时停
相等就结束;查到最后一张也结束。
要几次
最好1次,最坏n次,n是数据个数。
一句话:数据无序、数量不大,逐个找就够用。
2.1 猜数“魔法”之线性查找|本课要记住的三句话
教学提示:一句话:数据无序、数量不大,逐个找就够用。
查找轨迹:在1—10中找7
把每一次比较写下来,次数与位置的关系就清楚了。
第几次
比较的数字
结果
1
1
不是,继续
2
2
不是,继续
…
…
…
7
7
是,找到,停止
结论:目标在第7位,就恰好比较7次——位置决定次数。
2.1 猜数“魔法”之线性查找|查找轨迹:在1—10中找7
教学提示:把每一次比较写下来,次数与位置的关系就清楚了。;结论:目标在第7位,就恰好比较7次——位置决定次数。
线性查找 vs 随手乱翻
看起来都在“找”,可靠程度完全不同。
线性查找
· 从第一个开始,按顺序推进
· 每个数都恰好比较一次
· 不重不漏,次数可算
· 有无序都能用
随手乱翻
· 想翻哪页翻哪页
· 可能重复看,也可能漏看
· 找不到时说不清找没找全
· 无法统计次数
所以查找算法要先约定“从哪开始、按什么顺序”。
2.1 猜数“魔法”之线性查找|线性查找 vs 随手乱翻
教学提示:看起来都在“找”,可靠程度完全不同。;所以查找算法要先约定“从哪开始、按什么顺序”。
三种情况的比较次数
同一个算法,运气不同,次数差很多。
1
最好情况
目标就在第1位:只比较1次。
2
最坏情况
目标在最后一位或不存在:比较n次(n为数据个数)。
3
平均情况
大体在中间:约n/2次。
4
用途
用最坏次数估计“最慢要等多久”。
追问:8个数最坏几次?100个数呢?(8次、100次)
2.1 猜数“魔法”之线性查找|三种情况的比较次数
教学提示:同一个算法,运气不同,次数差很多。;追问:8个数最坏几次?100个数呢?(8次、100次)
课堂练习:数一数、比一比
用发到手里的8张打乱数字卡完成。
任务一:找卡片上的最后一个数,边找边在记录表画勾
比较次数:______ 次
#任务二:换一张目标卡,再找一次
比较次数:______ 次
小结:两次次数不同,是因为目标位置不同
巡视:勾数必须与实际翻动次数一致,不能凭印象写。
2.1 猜数“魔法”之线性查找|课堂练习:数一数、比一比
教学提示:用发到手里的8张打乱数字卡完成。;巡视:勾数必须与实际翻动次数一致,不能凭印象写。
当堂检测:三道题
独立完成,当堂核对。
题目
参考答案
8个数找最后一个,最坏几次?
8次
找第1个呢?
1次
线性查找要求数据有序吗?
不要求,无序也能逐个比较
判据:能同时说出“次数”与“是否要求有序”两条。
2.1 猜数“魔法”之线性查找|当堂检测:三道题
教学提示:独立完成,当堂核对。;判据:能同时说出“次数”与“是否要求有序”两条。
分层作业与下节预告
今天逐个找,明天学“跳着找”。
基础·必做
用10个数完成一次线性查找,记录比较次数。
提升·选做
估算100个数最坏比较次数,写出你的推算过程。
下节预告
如果数据已经排好序,能不能不用一个个看?——二分查找。
思考题:为什么“排好序”会让查找变快?
2.1 猜数“魔法”之线性查找|分层作业与下节预告
教学提示:今天逐个找,明天学“跳着找”。;思考题:为什么“排好序”会让查找变快?
线性查找在学习生活里能干什么
凡是“按顺序逐个核对”的事,都是它的身影。
核对名单
从第一行往下核对,直到找到名字。
检查作业
一本一本翻,找到没交的那本。
查找设置
在菜单里逐条往下看,找到目标选项。
局限
数据越多越慢,且必须逐项看完。
记录一次真实“逐个找”的经历,算出你的比较次数。
2.1 猜数“魔法”之线性查找|线性查找在学习生活里能干什么
教学提示:凡是“按顺序逐个核对”的事,都是它的身影。;记录一次真实“逐个找”的经历,算出你的比较次数。
课后作业(分层任选)
把课堂里的“逐个找”带回生活。
A 基础·必做
记录一次逐个查找的经历:找什么、找了几次、第几次找到。
B 提升·选做
数一数书包里有多少本书,找最后一本最坏要翻几次。
C 拓展·挑战
想一想:如果书已按书名排好,能不能不一本本翻?
下节课带来你的记录,我们比较“找得快”和“找得慢”。
2.1 猜数“魔法”之线性查找|课后作业(分层任选)
教学提示:把课堂里的“逐个找”带回生活。;下节课带来你的记录,我们比较“找得快”和“找得慢”。
$