(共14张PPT)
2.4.2基于枚举算法的问题解决
票据上有一个4位数字组成的编号：
甲说：数字编号的前两位数字相同，但都不是零；
乙说：数字编号的后两位数字是相同的，但与前
两位不同；
丙说：数字编号是一个整数的平方。
根据以上线索推断出编号。
票据中模糊数字推断问题：
已知条件
:
四个数字应是AABB，其中A≠0，A≠B,且AABB是一个整数的二次方
求解目标
:
票据中的数字
分析问题：
已知与未知的关系
:
要求解的4位数字的编号必须同时满足所有的已知条件
设计算法：
根据问题分析，只要一一列举出4位数字AABB中A与B的所有可能组合，保证A≠B?且A≠0.再验证二次方问题，就可以得到同题的解。因此，该问题可使用枚举算法求解完成
编程实现与调试:
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)
枚举算法：
依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可能情况的方法。
设计算法
编程实现与调试
分析问题
保存文件
适合解决求解的答案数量有限，并且可能的答案是能按照某种规则列举出来的问题。例如，用枚举法解决一些数学问题(“韩信点兵”“鸡兔同笼”等)、益智游戏和逻辑推理等。
分组探究：输出1000以内所有素数
素数是在大于1的自然数中，除了1和它本身以外不再有其他因数的数，如2,3,5,7,11,…
分析问题：
已知条件
求解目标
n<1000
素数的定义
（只有1和它本身两个因数的数）
输出1000以内所有的素数
设计算法：
开始
K=1
结束
k=1
for
n
in
range(2,1000):
for
j
in
range(2,n):
if
n%j==0:
k=0
if
k==1:
print(n)
k=1
import
math
k=1
for
n
in
range(2,1000):
m=math.ceil(math.sqrt(n))+1
if
n==2:
print(n)
for
j
in
range(2,n):
if
n%j==0:
k=0
break
if
k==1:
print(n)
k=1
方案1
方案2
枚举对象
枚举范围
验证条件
2～1
000
2～1
000
2～n
2～(√
n的整数部分
+
1)
逐一验证是否能整除n
逐一验证是否能整除n
讨论归纳：
课堂总结：
枚举算法思想在生活中解决问题的适用情况及特点：
1.求解的答案数量有限。
2.所有的可能情况都符合一定的规则。
算法效率：
算法的效率实际上指的是执行算法时所需要的时间与空间，分为算法的时间复杂度(即时间效率)和空间复杂度(即空间效率)。
时间复杂度可以通过测量算法步骤的执行次数来计算。
空间复杂度主要指算法在执行时所需要的最大存储空间的大小。
课后思考：
1.能不能运用今天所学知识任意破解别人的密码？
2.如何保护自己的密码安全？(
装
订
线
)课
题
2.4.2基于枚举算法的问题解决
课型
新授课
课时安排
1
教
学
过
程
(
授课教师
：
授课班级
：
)教学目标
理解枚举算法的基本原理和求解问题的基本过程，能够完善程序代码实现算法。
掌握枚举算法解决问题的基本过程，学会使用枚举算法解决生活中的实际问题，提高信息安全意识。
体验枚举算法的执行效率，认识优化算法的必要性。
一、情景导入：数字解密问题
票据上有一个4位数字组成的编号：
甲说：数字编号的前两位数字相同，但都不是零；
乙说：数字编号的后两位数字是相同的，但与前两位不同；
丙说：数字编号是一个整数的平方。
根据以上线索推断出编号。
学生思考：你怎样应用学过的知识进行推断？
二、新知探索：
1.
数字解密问题：
分析问题：
教师引导学生思考并回答
分析出已知条件、求解目标、已知和未知之间的关系
已知条件
:
四个数字应是AABB，其中A≠0，A≠B,且AABB是一个整数的二次方
求解目标
:
票据中的数字
已知与未知的关系
:
要求解的4位数字的编号必须同时满足所有的已知条件
设计算法：
根据问题分析，只要一一列举出4位数字AABB中A与B的所有可能组合，保证A≠B?且A≠0.再验证二次方问题，就可以得到同题的解。因此，该问题可使用枚举算法求解完成
学生将老师展示的流程图半成品补充完整：
编程实现与调试：
学生在Python中
将下面程序补充完整并调试运行：
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)
教学难点
教学重点
重点：理解枚举算法的基本思想，能够结合实际问题完善程序代码并调试运行，解决问题。
难点：体验枚举算法的执行效率，认识优化算法的必要性。
教学
方法
讲授法、任务驱动法、合作探究法、体验法、云课堂演示等
板书设计
2.4.1基于解析算法的问题解决
枚举算法：依据已知条件，确定答案的大致范围，在此范围内列举出所有的可能的方法。
注意：不能遗漏，不能重复
优化算法：缩小枚举范围，提高解决问题的效率
教学反思
本节课是在学生已经学习了解析算法的基础上学习的，因此课堂效率较高。首先通过“数字解密问题”的求解让学生理解枚举算法的基本原理和提高信息安全的意识，再以“输出1000以内的素数”为例，让学生感受算法的效率，认识到优化算法的必要性，达到了预期的教学计划。
教师讲授枚举算法的基本原理，强调该算法的基本特征：枚举对象、枚举范围和验证条件
三、探究：输出1000以内所有素数
分析问题：
已知条件：
n<1000
素数的定义（只有1和它本身两个因数的数）
求解目标：输出1000以内所有的素数
设计算法：学生完善教师在白板上的流程图半成品
编程实现与调试：
（1）种
k=1
for
n
in
range(2,1000):
for
j
in
range(2,n):
if
n%j==0:
k=0
if
k==1:
print(n)
k=1
（2）种
import
math
k=1
for
n
in
range(2,1000):
m=math.ceil(math.sqrt(n))+1
if
n==2:
print(n)
for
j
in
range(2,n):
if
n%j==0:
k=0
break
if
k==1:
print(n)
k=1
四、讨论归纳：
1.
学生体验完运行调试程序后，填写下表：
方案1方案2枚举对象枚举范围验证条件
2.师生共同总结：
方案2的运算速度更快，效率更高，原因是方案2的程序缩小了枚举范围，进而减少了逐一验证的次数，提高了程序的运算效率，因此在以后求解问题过程中对代码优化很有必要的。
3.教师讲授：
算法效率：
通常，算法的效率主要指算法执行时间的高效以及努力降低对存储空间的需求。这既是算法设计追求的目标，也是衡量一个算法优劣的重要标准。算法的效率实际上指的是执行算法时所需要的时间与空间，分为算法的时间复杂度(即时间效率)和空间复杂度(即空间效率)。算法的时间复杂度主要指算法在运行时花费的时间，但这里的“运行”是抽象的运行，并不是在具体计算机上的运行。时间复杂度可以通过测量算法步骤的执行次数来计算。对于同一个问题，如果有多个算法可以解决，那么步骤操作次数少、执行时间短的算法显然效率较高。空间复杂度主要指算法在执行时所需要的最大存储空间的大小。在计算机发展的早期，计算机的存储容量很小，所以人们很重视空间复杂度。但随着计算机技术的迅速发展，目前计算机的存储容量已经实现了很大的提升，许多时候也就不再关注算法的空间复杂度。因此，现在当我们评价一个算法效率的时候，更多的是在研究它的时间复杂度。
五、作业：
1.能不能运用今天所学知识任意破解别人的密码？
2.如何保护自己的密码安全？
