资源简介

教学设计
课例名称
2.4.2
基于枚举算法的问题解决
学段学科
高一
信息技术
教材版本
人教中图版
章节
必修
第二章
第四节
授课学校
核心素养
目标
进一步体验算法思想，通过实例了解用枚举法解决问题的基本方法。（信息意识）
理解枚举法的核心思想，抽取数学模型（计算思维）。
3、体验枚举算法的执行效率，认识优化算法的必要性（数字化学习与创新）。
教学重难点
1、教学重点:
建立正确的数学模型，确定枚举方案。
2、教学难点:
恰当安排枚举方式，感受不同算法的执行效率，体验算法优化在解决中的价值。
教材分析
在应用计算机求解问题时，枚举是一个很常用的思想方法，一个严密的枚举方案可以训练思维的严密性和条理性。枚举算法的基本思想是在列举过程中，所有可能一个不漏地逐一判断，从中得到符合要求的答案。
通过本节内容的学习，学生对设计算法求解问题有了进一步的认识，思考问题更加严密，程序编制和调试更有经验。
教学策略
注重教学过程中核心素养的培养，以“优化为营”项目任务入手，引导学生关注枚举法在社会生活中的应用，培养学生的逻辑思维能力、解决问题的能力。
采用以学生的学习和发展为中心的自主、合作、探究等学习方法；强调信息技术与生活实际的联系，以及创新意识等；设置多元化的评价方式，让学生掌握学习内容的同时，形成交流与评价的能力。
2.4.2基于枚举算法的问题解决
教学环节
教师活动
学生活动
设计理念
提出问题
引发思考
提出问题：
1、开展凑24游戏，数字1到10，随机抽出四个数，任意作“加、减、乘、除”四则运算，找出一种运算结果等于24的方法。（比如“5，4，6，2”四个数，方法为：5
4+(6-2)=24。）
2、某羽毛球赛共有23支队伍报名参赛，赛事安排23支队伍抽签两两争夺下一轮的出线权，没有抽到对手的队伍轮空，直接进入下一轮，那么，本次羽毛球赛最后共会遇到多少次轮空的情况？（公务员考试题）
3、如图
某同学要从甲地到乙地和丙地游玩，其中从甲地到乙地有2条路线可走，从乙地到丙地有3条路线可走，从甲地到丙地共有4条不同的路线可走，问从甲地到丙地共有多少种不同的走法？
1、学生参与游戏，积极思考，在游戏过程中体会解题的基本思路。
2、分析思考问题，并尝试用数学方法解决问题。
3、学生小组探究
以上问题的是否有相同规律？尝试进行归纳总结。
进行推理，请说出相关的解决方法。
1、贴近生活，体现生活里的程序，程序里的生活。
2、拓展视角，促使学生积极思考，进行归纳推理，提高解决问题的能力。
核心学习
枚举算法
通过演示文稿介绍：
枚举算法的定义
枚举算法的基本思路
枚举算法流程图
引领学生归纳总结枚举法的基本思路及枚举策略。
1、将手动枚举和计算机枚举进行对比。
2、读流程图，理解枚举算法的工作流程
思考、交流与讨论，体验计算机枚举在解决现实生活问题中的作用与优势。
引导学生发现知识的规律、方法，提高信息意识，形成严谨的逻辑思维习惯。
学以至用
解决问题
1、布置探究任务
模糊数字推断问题：
票据上有一个4位数字组成的编号：
甲说：数字编号的前两位数字相同，但都不是零；
乙说：数字编号的后两位数字是相同的，但与前两位不同；
丙说：数字编号是一个整数的平方。
　　根据以上线索推断出编号。
2、巡视学生学习情况，指导和帮助学生自主、协作学习。
3、调控课堂气氛。
1、根据任务需求，学生应用枚举法，找出已知条件，求解问题以及隐含关系。
2、确定枚举对象、范围和判定条件。
3、编写程序，解决问题。
import
math
for
A
in
range(1,
10):
for
B
in
range
(0,
10):
if
A
!=
B:
k
=
A
1000
+
A
100
+
B
10
+
B
c
=
int(math.sqrt(k))
#
if
c
c
==
k:
print("票据编号是：",
k)
1、学生体验枚举法解决问题的全过程。
2、引导学生
提炼枚举法的技术思想，使学生解决问题的能力可迁移，提高计算思维。
项目实战
优化为营
项目：寻找1000以内的所有素数
旧例推新，重在优化
通过素数定理1（从2开始到自身开平方的数中找到一个能整除的）。和学生完成程序基本写法。
引导学生优化算法程序
这种基本写法是否有待改进？
探究完成：
1、第一层循环的i取值时，是否可以排除偶数？
2、第二层循环j取值时，从2开始到i开平方取值，思考函数range()
的使用，是否可减少一半的数？
读下列程序，
n
=
1000
for
i
in
range(2,
n):
for
j
in
range(2,
i):
if
i
%
j
==
0:
break
else:
print(i,
end='
')
优化1，完成探究活动：
1、第一层循环的i取值时，因为偶数确定不是素数，所以排除偶数，使用range()函数排除偶数，range(3,
n,
2)这样就减少了一半的数。
2、第二层循环j取值时，考虑从2开始到i开平方取值，同时也把偶数排除range(3,
int(i
0.5)+1,
2)这样也可减少一半的数。2就是素数，单独打印。
1、解决问题并不难，让学生感受到难的是选择最优的枚举策略。
提高学生对利用程序解决实际问题过程的系统化梳理的能力。
2、小组合作探究，通过对比实验，认识算法优劣在解决问题中的意义，促进数字化学习与创新。
项目实战
优化为营
1、素数定理2
一个合数一定可以分解成几个素数的乘积，也就是说，一个数如果能被一个素数整除就是合数。(使用列表保存素数）。
2、代领学生使用定理2，完成程序，使之更有python语言的特色。
3、引导学生优化算法程序
探究：
（1）上述写法的效率是否有待提高
？
（2）读程序，第一层循环的i与列表中的元素进行了怎样的操作？
（3）请进一步优化。
优化2：
使用定理2，用列表保存上一次的运算结果：
n
=
100
L
=
[2]
for
i
in
range(3,
n,
2):
for
j
in
L:
if
i
%
j
==
0:
break
else:
L.append(i)
print(L)
优化3，完成探究活动：
此种写法的效率不高，第一层循环的i没必要与列表中的每一个元素取余，与从2开始到i的开平方处之间的数取余即可。
设计一题多解、多次优化的任务，体验枚举算法的执行效率，认识优化算法的必要性。
提高规划设计能力，计算思维，鼓励学生勇于探索。
归纳总结
知识内化
1、通过演示文稿总结本节知识内容，帮助学生归纳知识。
2、总结同学们在解决问题过程中所遇到的困难。
3、略述枚举法的局限性。
1、知识总结，系统归纳。
2、回忆课堂学习过程，提高对枚举算法的认识。
3、学生自我反思，加深对所学知识的认识与理解，学会评价各种枚举方案的优劣。
促使学生将知识内化、系统化，并进行能力迁移。
阅读拓展
网络探索
鼓励有兴趣的学生自主学习相关知识，进行更深入的探索。
利用网上搜索算法的基本设计方法，了解递归法，排序法、回溯法、
动态规划法等解决问题的方向。
通过知识的延伸，拓展学生的思路，提升信息意识，鼓励数字化学习与创新，加强核心素养的培养。
附优化1及优化3程序代码：
优化1程序代码：
n
=
100
print(2)
for
i
in
range(3,
n,
2):
for
j
in
range(3,
int(i
0.5)+1,
2):
if
i
%
j
==
0:
break
else:
print(i,
end='
')
优化2程序代码：
n
=100
L
=
[2]
for
i
in
range(3,
n,
2):
flag
=
False
for
j
in
L:
if
i
%
j
==
0:
flag
=
True
break
if
j
>
int(i
0.5):
break
if
not
flag:
L.append(i)
print(L)2.4.2基于枚举算法的问题解决
练
习
题
一、选择题
1、(单选)下列问题中适合使用枚举算法解决的是（）
A
在一串不相同的钥匙中寻找云教室的钥匙
B
已知a,b,c，求一元二次方程ax2+bx+c=0的解
C
超市的促销方案
D
利用“割圆术”求圆周率的近似值
2、（单选）枚举算法的适用范围是（）
A
一切问题
B
所求问题的解无限多
C
所求问题解的个数有限且有明确的条件
D
所求问题解的个数有限且无明确的条件。
3、(单选)下列问题中适合使用枚举算法解决的是（）
A
已知5个电阻阻值，求它们并联后的阻值
B银行贷款买房后每月还货金额的计算
C
查找100以内所有能被6整除的数
D
已知某同学的身高和体重，判断体重指数的等级
4、（多选）枚举算法思想在生活中解决问题的适用情况及特点
A
运算量大
B
求解数量有限
C
所有的可能情况都符合一定的规则，
D
计算表达式来实现问题的解
5、下列说法符合枚举算法的是（），
A逐一判断，强调不遗漏且不重复地验证条件。
B根据条件判断是否合适，保留合适的，舍弃不合适的.
C
为了提高解决问题的效率，使可能解的范围将至最小，
D可作为某类问题时间性能的底线，用来引出同样问题的更高效率的算法。
二、简析题
1、小刘负责甲、乙、丙三个机房的巡检工作，甲、乙和丙机房分别需要每隔2天、4天和7天巡检一次，3月1日，小刘巡检了3个机房，问他在整个3月有几天不用做机房的巡检工作？
2、把若干个大小相同的立方体摆成如图形状，从上向下数，摆1层有一个立方体，摆2层共有4个立方体，摆3层共有10个立方体，问摆了7层共有多少个立方体？
答案：
一、A
C
C
ABC
ABCD
二、
14天
84个(共25张PPT)
第二章
算法与程序实现
2.4.2基于枚举算法的问题解决
目
录CONTENTS
01
提出问题
引发思考
02
核心学习
枚举算法
03
学以至用
解决问题
04
项目实战
优化为营
05
阅读拓展
网络探索
提
出
问
01
题
提出问题
1、开展凑24游戏，1到10，10个数，随机抽出四个数，任意作“加、减、乘、除”四则运算，找出一种运算结果等于24的方法。（比如“5，4，6，2”四个数，那么方法为：5
4+(6-2)=24。）
2、某羽毛球赛共有23支队伍报名参赛，赛事安排23支队伍抽签两两争夺下一轮的出线权，没有抽到对手的队伍轮空，直接进入下一轮，那么，本次羽毛球赛最后共会遇到多少次轮空的情况？（公务员考试题）
3、
如图
某同学要从甲地到乙地和丙地游玩，其中从甲地到乙地有2条路线
可走，从乙地到丙地有3条路线可走，从甲地到丙地共有4条不同的路线可走，
问从甲地到丙地共有多少种不同的走法？
思考下列问题：
1、以上问题的是否有相同规律？尝试进行归纳总结。
2、进行推理，请说出相关的解决方法。
小组探究：
提出问题
枚
举
算
02
法
核心学习
枚举算法
在进行归纳推理时，依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。
枚举算法的定义：
在列举过程中，既不能遗漏，也不能重复，通过逐一判断，验证哪些情况满足问题的条件，从而得到问题的答案。
核心概念
1、确定枚举对象、范围和判定条件。
2、逐一枚举可能的解，并验证每个解是否是问题的解。
枚举算法的基本思路：
枚举算法
枚举算法
开始
输出该枚举值
枚举值在给定的
范围中吗？
取下一个枚举值
结束
枚举值符合给定
的条件吗？
N
N
Y
Y
枚
举
算
法
流
程
图
列举，采用循环来实现；逐个检验，采用选择来实现。
枚举算法
1.模糊数字问题
例:一个五位数，万位和百位不知道，但是57和67的倍数，求所有的可能性。（直接枚举所有情况，判断即可）。
2、百钱买百鸡问题
公元6世纪，中国的《张丘建算经》有一道著名的百鸡问题：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，凡百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”
3、填写运算符问题
添加“+”、“-”，“
”，“/”,4个运算符，使得式子成立：
5
?5
?5
?5
?5=5?
枚举算法
主要解决的实例
学
以
至
03
用
学以至用
　　票据上有一个4位数字组成的编号：
甲说：数字编号的前两位数字相同，但都不是零；
乙说：数字编号的后两位数字是相同的，但与前两位不同；
丙说：数字编号是一个整数的平方。
　　
根据以上线索推断出编号。
提出问题
模糊数字推断问题：
学以至用
已知
问题
求解问题
分析
四个数字应是AABB，其中A≠
0，A≠B，
且AABB是一个整数的二次方
票据中的数字。
要求解的4位数字的编号必须同时满足所有的已知条件。
解题时尽量分析出问题隐含条件，缩小枚举的范围，提高算法效率。
隐含关系
学以至用
import
math
for
A
in
range(1,
10):
for
B
in
range
(0,
10):
if
A
!=
B:
k
=
A
1000
+
A
100
+
B
10
+
B
c
=
int(math.sqrt(k))
#
求票据中数字的平方根并取其整数部分
if
c
c
==
k:
#
若k是完全平方数，则找到该票据编号
print("票据编号是：",
k)
代码
调试程序：
项
目
实
04
战
项目实战
寻找1000以内的所有素数
欧几里德大约在公元前300年，征明了素数有无数个，从此人们开始了寻找素数的历程。
项目
项目实战
寻找1000以内的所有素数
确定范围：1和它本身之间的所有数。
满足条件：逐一验证除1和它本身以外的数能否整除。
分析
有关素数例题，前面曾讲引用过，本节课旧例推新。
项目实战
素数定理：
1、从2开始到自身的-1的数中找到一个能整除的（从2开始到自身开平方的数中找到一个能整除的）。
2、一个合数一定可以分解成几个质数的乘积，也就是说，一个数如果能被一个质数整除就是合数。(使用列表保存质数）
n
=
1000
for
i
in
range(2,
n):
for
j
in
range(2,
i):
if
i
%
j
==
0:
break
else:
print(i,
end='
')
使用定理1的基本写法：
项目实战
优化
这种基本写法是否有待改进？
1、第一层循环的i取值时，是否可以排除偶数？
2、第二层循环j取值时，从2开始到i开平方取值，思考函数range()
的使用，是否可减少一半的数？
小组探究：
使用定理2，用列表保存上一次的运算结果。
n
=
100
L
=
[2]
for
i
in
range(3,
n,
2):
for
j
in
L:
if
i
%
j
==
0:
break
else:
L.append(i)
print(L)
素数定理：
1、从2开始到自身的-1的数中找到一个能整除的（从2开始到自身开平方的数中找到一个能整除的）。
2、一个合数一定可以分解成几个素数的乘积，也就是说，一个数如果能被一个素数整除就是合数。(使用列表保存素数）。
项目实战
1、上述写法的效率是否有待提高？
2、读程序，第一层循环的i与列表中的元素进行了怎样的操作？
3、请进一步优化。
优化
小组探究：
项目实战
项目实战
枚举的意义
1、枚举法是在分析问题时，通过循环、递归或选择，利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案。
2、枚举可作为某类问题时间性能的底线，用来引出同样问题的更高效率的算法。
???
阅
读
拓
05
展
阅读拓展
请到网上搜索算法的基本设计方法，了解递归法，排序法、回溯法、
动态规划法等解决问题的方向。
自主学习
谢
谢
聆
听

展开更多......

收起↑