资源简介

(共20张PPT)
第8课 算法的多样性
年 级：六年级
学 科：小学信息科技（浙教版）
目标数：15
游戏内容：
20个盲盒分别装有范围在1—20的数字，每个数字都是唯一的，不重复。若你每次只能打开一个盲盒，比一比谁用最少的次数找到目标数！思考：用什么方法找到目标数的？
游戏体验
解决同一个问题，可能存在多种算法！
游戏体验
一个一个查找，是怎样找到目标数的？
一个大问题是怎样分解成小问题，从而找到目标数？
01
02
请你用自然语言描述在1—100范围内查找目标数37，一个一个查找的过程。
1 2 3 …… 36 38 …… 99 100
目标数：37
2.形成策略：按顺序依次查找
37
37
37
37
37
查找成功！
37
活动一：顺序查找算法设计验证
1.请你用自然语言描述在1—100范围内查找目标数37，一个一个查找的过程。
顺序查找算法设计
采用“按顺序依次查找”的策略，在1-100范围内查找数37，一共需比较多少次呢？
37次
完成学习任务单中的顺序查找流程图设计，在右侧3个备选项中选择合适的语句，将流程图补充完整。
开始
da←37
cai←1
cai←cai+1
cai=da
cai<101
找到，输出信息
未找到，输出信息
结束
否
是
是
否
cai<101
cai=da
cai←cai+1
活动一：顺序查找算法设计验证
顺序查找算法设计
1.打开“顺序查找算法.py”文件，同桌讨论并完善程序。
①
②
③
2.运行程序，在学习任务单上完成表1。
目标数 预测程序运行结果 验证结果
37
137
找到
找到
未找到
未显示
活动一：顺序查找算法设计验证
表1：顺序查找算法验证结果
顺序查找算法验证
1.为什么要加break语句？break语句在循环语句中起到了什么作用？
2.若变量da的值为137，则程序运行结果是什么？若要显示对应提示，应如何修改程序？
1
101
cai+1
break语句的作用是终止所在的循环。
活动一：顺序查找算法设计验证
顺序查找算法验证
1 2 3 …… 49 50 51 …… 99 100
怎样把大问题分解成小问题？
活动二：二分查找算法设计验证
怎么取中间数？
二分查找算法设计
目标数：37
取中间数查找
1 2 3 …… 49 50 51 …… 99 100
第一次比较：37<50
范围调整为1-49
1 2 3 …… 24 25 26 …… 48 49
第二次比较：37>25
范围调整为26-49
26 27 28 …… 36 37 38 …… 48 49
第三次比较：37＝37
查找成功！
活动二：二分查找算法设计验证
二分查找算法设计
根据取中间数查找的策略，小组合作完成学习任务单上的表2。
目标数 初值 终值 中间值 比较结果 策略 变化后的情况 初值 终值
50 1 100 50 等于中间数 查找结束 1 100
25 1 100 50 小于中间数 缩小问题规模，查找中间数左边 1 49
75
1 49 25 等于中间数 查找结束 1 49
51 100 75 等于中间数 查找结束 51 100
1 100 50 大于中间数 缩小问题规模，查找中间数右边 51 100
中间数计算模型：
中间数=（范围初值+范围终值）/2 取整数部分
活动二：二分查找算法设计验证
表2：取中间数查找
根据取中间数查找策略，小组合作完成任务单上的流程图设计。
要求：在右侧6个备选项中选择合适的语句，将流程图补充完整。
计算中间值cai
cz≤zz？
cai=da？
dazz←cai-1
cz←cai+1
cz≤zz？
计算中间值cai
dazz←cai-1
cz←cai+1
cai=da？
活动二：二分查找算法设计验证
二分查找算法设计
根据二分查找算法流程图，查找目标数37，在学习任务单上填写表3验证算法。
循环次数 cz zz cz≤zz 中间值cai cai==da da1 1 100 是 50 否 是
是
25
25
否
3
2
1
49
25
49
是
37
是
我的发现：通过（ ）次循环，输出结果为（ ）
3
找到
活动二：二分查找算法设计验证
二分查找算法验证
表3：目标数37二分查找算法表格验证
试一试：若变量da的值为137，填写表4验证算法。
我的发现：通过（ ）次循环，输出结果为（ ）
7
未找到
活动二：二分查找算法设计验证
二分查找算法验证
表4：目标数137二分查找算法表格验证
2 51 100 是 75 否 否
3 76 100 是 88 否 否
4 89 100 是 94 否 否
5 95 100 是 97 否 否
6 98 100 是 99 否 否
7 100 100 是 100 否 否
101 100 否 未进循环，不计次数
打开“二分查找算法.py”文件，运行程序，体验二分查找算法。
解决同一个问题，可能存在多种算法。通过（ ）和（ ）算法解决了生活中猜数字游戏问题。
顺序查找
二分查找
活动二：二分查找算法设计验证
有15个学生排成一排，其中只有1个学生是“班级小达人”，你要通过问他们“班级小达人在哪里”来找到真正的“班级小达人”。想一想：根据算法的多样性，你将采用哪些策略快速找到“班级小达人”？请在表格中填写策略，并小组内交流。
策略一 策略二
迁移应用
1.思考：哪些关键数据发生了变化？程序中那些语句需要修改？ 2.打开”顺序查找算法.py”文件，修改并运行调试。
在顺序查找算法中，若变量cai的取值依次为100,99，……2,1，则相应的算法和程序如何修改？
作业练习
算法的多样性
顺序查找
二分查找
大问题分解为规模更小、类似的子问题
课堂总结
谢谢观看！
Thanks!
https://www.21cnjy.com/recruitment/home/fine

展开更多......

收起↑