(共18张PPT)
枚举算法及其优化
山东省济南第一中学
焦学仕
枚举法
(又称穷举法)
是指一一列举出所有与问题相关的情况，然后根据问题设定的条件，逐个加以检查判断，找到满足条件的解的方法。
枚举算法的概念
枚举算法的实现过程
二、在一定的范围内进行列举
一、对枚举的每一组数据进行检验
在不遗漏正确解的前提下，枚举范围尽可能的缩小以提高效率
如果结果唯一，数据一旦检验成功则结束枚举，输出答案、提前结束程序；如果结果不唯一，则一定要检验可能范围内的所有数据，并输出答案。
枚举算法及其优化
例题
百钱买百鸡
设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱。现用100钱来买100只鸡。
问：公鸡、母鸡、小鸡各买多少只？（公鸡、母鸡、小鸡每种最少一只）
【分析】
公鸡的数量x：最少1只，不超过
只
母鸡的数量y：最少1只，不超过
只
小鸡的数量z：最少1只，不超过
只
①5
x
+
3
y
+
z
/
3
=
100
②x
+
y
+
z
=
100
满足条件：
20
33
100
程序实现
import
time
cishu=0
#初始循环次数为0
starttime
=
time.perf_counter()
#枚举开始时读取系统当前时间
for
x
in
range(1,20):
for
y
in
range(1,33):
for
z
in
range(1,100):
cishu+=1
#每循环一次，次数加1
if
x
5+y
3+z/3==100
and
x+y+z==100:
print(x,y,z)
endtime
=
time.perf_counter()
#枚举完成时读取系统当前时间
totaltime=endtime-starttime
print('共循环%.f次'%cishu)
print('总共耗时：%.6f秒'%totaltime)
用三重循环来枚举所有的情况
优化策略之一：剪枝法
缩小枚举范围来提高解决问题的效率。同时也要避免重复枚举。
优化分析
百钱买百鸡
设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱。现用100钱来买100只鸡。
问：公鸡、母鸡、小鸡各买多少只？（公鸡、母鸡、小鸡每种最少一只）
【分析】
公鸡的数量x：最少1只，不超过
只
母鸡的数量y：最少1只，不超过
只
小鸡的数量z：
只
100-x-y
20
33
（提示：小鸡的数量可不可以用x,y来表示？）
import
time
cishu=0
#初始循环次数为0
starttime
=
time.perf_counter()
#枚举开始前读取系统当前时间
for
x
in
range(1,20):
for
y
in
range(1,33):
z=100-x-y
cishu+=1
#每循环一次，次数加1
if
x
5+y
3+z/3==100:
print(x,y,z)
endtime
=
time.perf_counter()
#枚举完成时读取系统当前时间
totaltime=endtime-starttime
print('共循环%.f次'%cishu)
print('总共耗时：%.6f秒'%totaltime)
优化后的程序
优化后由三重循环变成两重循环
import
time
cishu=0
starttime
=
time.perf_counter()
for
x
in
range(1,20):
for
y
in
range(1,33):
z=100-x-y
cishu+=1
if
x
5+y
3+z/3==100:
print(x,y,z)
endtime
=
time.perf_counter()
total=endtime-starttime
print('共循环%.f次'%cishu)
print('总共耗时：%.6f秒'%total)
优化前后程序对比
import
time
cishu=0
starttime
=
time.perf_counter()
for
x
in
range(1,20):
for
y
in
range(1,33):
for
z
in
range(1,100):
cishu+=1
if
x
5+y
3+z/3==100
and
x+y+z==100:
print(x,y,z)
endtime
=
time.perf_counter()
totaltime=endtime-starttime
print('共循环%.f次'%cishu)
print('总共耗时：%.6f秒'%totaltime)
循环由三重变为两重，判断条件少了x+y+z=100（思考:为什么可以去掉？）
借助数学知识继续优化：
第一步：
使用加减消元的方法消掉一元，比如z，然后用x来表示y和z
第二步：
令x=4k，则有
第三步：
根据题目中x,y,z的范围，列出不等式组：
第四步：求出，
for
k
in
range(1,4):
x=4
k
y=25-7
k
z=3
k+75
print(x,y,z)
终极优化
终极优化之后，只有3次循环！
至此，可以明确，只要求出k值，公鸡、母鸡、小鸡的数目就确定了,而0充分运用数学工具，通过计算，在约束条件下，找出目标函数的最优解,大大提高了运行效率！
优化策略之二：数学优化
形如a
3
=
b
3
+
c
3
+
d
3
的等式被称为完美立方等式。例如12
3
=
6
3
+
8
3
+
10
3
。编写一个程序，输出100以内的完美立方组合，其中a,b,c,d
大于
1,
小于100，且bfor
a
in
range(2,100):
for
b
in
range(1,100):
for
c
in
range(1,100):
for
d
in
range(1,100):
if
a
3==b
3+c
3+d
3:
print(a,b,c,d)
完美立方
枚举优化练习
形如a
3
=
b
3
+
c
3
+
d
3
的等式被称为完美立方等式。例如12
3
=
6
3
+
8
3
+
10
3
。编写一个程序，输出100以内的完美立方，其中a,b,c,d
大于
1,
小于100，且bfor
a
in
range(2,100):
for
b
in
range(1,
):
for
c
in
range(
):
for
d
in
range(
):
if
a
3==b
3+c
3+d
3:
print(a,b,c,d)
完美立方程序优化
a
b,a
c,a
思考：a和b、c、d的大小关系
a>d>c>b
1
100
b
c
d
a
总结
枚举法又叫穷举法，是指把所有可能的组合都列出来一个一个取分析，找出所有的正确结果。
枚举法算法简单，但是效率不高，一般在解得数量不多，并且解是可以计算、固定不变的情况下才可以使用。
枚举法可以使用剪枝法、数学计算法进行优化，以提高运行效率。
课后练习
五位数
假定一个五位数abcde满足条件abcde×a=eeeeee，求出该五位数。
课后思考：如何优化？广东教育出版社必修一第四章《程序设计基础》4.4.3枚举算法及其优化评测练习
形如的等式被称为完美立方等式。例如
。编写一个程序，输出100以内的完美立方组合，其中a,b,c,d
大于
1,
小于100，且b1、数轴上标出a、b、c、d的大小关系：
2、a、b、c、d的取值范围：
a：
b：
c：
d：
3、填写完美立方程序
import
time
starttime
=
time.perf_counter()
zuhe=0
cishu=0
for
a
in
range(2,
):
for
b
in
range(
,
):
for
c
in
range(
,
):
for
d
in
range(
,
):
cishu+=1
if
:
print(a,b,c,d)
zuhe+=1
endtime=
time.perf_counter()
totaltime=endtime-starttime
print('总共有%.f种组合'%zuhe)
print('共循环%.f次'%cishu)
print('总共耗时：%.2f秒'%totaltime)
1
1004.4.3
枚举算计及其优化
一、学科核心素养
（1）
针对给定的任务进行需求分析，明确需要解决的关键问题。
（2）
能提取问题的基本特征，进行抽象处理，并用形式化的方法表述问题。
（3）
运用基本算法设计解决问题的方案，能使用编程语言或其他数字化工具实现这一方案。
（4）
针对不同模块，设计或者选择合适的算法，利用编程语言或其他数字化工具实现各模块功能。
二、内容要求
必修课程模块1:
1.7掌握一种程序设计语言的基本知识，使用程序设计语言解决实际问题，体验程序设计的基本流程，感受算法的效率，掌握程序运行和调试的方法。
三、学业要求
【信息意识】
能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息
【计算思维】
1、能够采用计算机科学领域的思想方法界定问题、抽象特征、建立结构模型。
2、依据解决问题的需要，设计和表示简单算法；掌握一种程序设计语言的基本知识，利用程序设计语言实现简单算法，解决实际问题。
【数字化学习与创新】
适应数字化学习环境，养成数字化学习与创新的习惯，握数字化学习工具的操作技能，
四、学习目标
1、
通过实例进一步理解枚举算法
2、
掌握枚举算法的两种优化方法，剪枝优化法与数学优化法。
五、学习重难点：
重点：枚举法的两种优化方法
难点：枚举算法中的数学优化法。
六、教学素材准备：
纸质学习任务单、网络共享在线excel文档、压缩后的作业文件、python程序。
七、教学过程
环节一：情景导入
引导学生按照组别分别下载本组作业，并尝试解压缩
思考：
1、
文件是否能成功解压缩？
2、
如何破解密码？靠猜密码是否行的通？
3、
这是一个四位数组成的密码，如果编写程序，可以使用什么样的算法？
4、
尝试使用python程序暴力破解密码，注意修改被破解的文件名
5、
每组组长填写在线共享excel文档，记录破解后的密码及破解时间
6、
各组破解的时间相同吗？为什么？
7、
从暴力破解所用的时间上来看，我们设定密码应该注意什么？
环节二：百钱买百鸡的优化
一、枚举法的概念
枚举法又称穷举法，是指一一列举出所有与问题相关的情况，然后根据问题设定的条件，逐个加以检查判断，找到满足条件的解的方法。
二、枚举算法的实现过程
1、对枚举的每一组数据进行检验
如果结果唯一，数据一旦检验成功则结束枚举，输出答案、提前结束程序；如果结果不唯一，则一定要检验可能范围内的所有数据，并输出答案。
2、在一定的范围内进行列举
在不遗漏正确解的前提下，枚举范围尽可能的缩小以提高效率
三、百钱买百鸡及优化
问题：百钱买百鸡
设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱。现用100钱来买100只鸡。问：公鸡、母鸡、小鸡各买多少只？（公鸡、母鸡、小鸡每种最少一只）
【分析】
公鸡的数量x：最少1只，不超过
只
母鸡的数量y：最少1只，不超过
只
小鸡的数量z：最少1只，不超过
只
满足条件：
①5
x
+
3
y
+
z
/
3
=
100
②x
+
y
+
z
=
100
【程序实现】用三重循环来枚举所有的情况
import
time
cishu=0
#初始循环次数为0
starttime
=
time.perf_counter()
#枚举开始时读取系统当前时间
for
x
in
range(1,
):
for
y
in
range(1,
):
for
z
in
range(1,
):
cishu+=1
#每循环一次，次数加1
if
x
5+y
3+z/3==100
and
x+y+z==100:
print(x,y,z)
endtime
=
time.perf_counter()
#枚举完成时读取系统当前时间
totaltime=endtime-starttime
print('共循环%.f次'%cishu)
print('总共耗时：%.6f秒'%totaltime)
【优化策略之一】剪枝法
缩小枚举范围来提高解决问题的效率。同时也要避免重复枚举。
【优化分析】
进一步分析百钱买百鸡暗含的条件范围：
设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱。现用100钱来买100只鸡。
问：公鸡、母鸡、小鸡各买多少只？（公鸡、母鸡、小鸡每种最少一只）
【分析】
公鸡的数量x：最少1只，不超过
只
母鸡的数量y：最少1只，不超过
只
小鸡的数量z：
只
提示：小鸡的数量可不可以用x,y来表示？
【优化后的程序】优化后由三重循环变成两重循环
import
time
cishu=0
#初始循环次数为0
starttime
=
time.perf_counter()
#枚举开始前读取系统当前时间
for
x
in
range(1,
):
for
y
in
range(1,
):
z=
cishu+=1
#每循环一次，次数加1
if
x
5+y
3+z/3==100:
print(x,y,z)
endtime
=
time.perf_counter()
#枚举完成时读取系统当前时间
totaltime=endtime-starttime
print('共循环%.f次'%cishu)
print('总共耗时：%.6f秒'%totaltime)
环节三：学以致用
枚举优化练习
完美立方
形如a
3
=
b
3
+
c
3
+
d
3
的等式被称为完美立方等式。例如12
3
=
6
3
+
8
3
+
10
3
。编写一个程序，输出100以内的完美立方组合，其中a,b,c,d
大于
1,
小于100，且b分析并填写：
1、数轴上标出a、b、c、d的大小关系：
2、a、b、c、d的取值范围：
a：
b：
c：
d：
3、完善程序并调试，填写下表
for
a
in
range(2,100):
for
b
in
range(1,
):
for
c
in
range(
):
for
d
in
range(
):
if
a
3==b
3+c
3+d
3:
print(a,b,c,d)
4、调试程序填写下表
100内完美立方共有（组）
循环次数（次）
耗时（秒）
环节四：总结
枚举法又叫穷举法，是指把所有可能的组合都列出来一个一个取分析，找出所有的正确结果。枚举法算法简单，但是效率不高，一般在解得数量不多，并且解是可以计算、固定不变的情况下才可以使用。
枚举法可以使用剪枝法、数学计算法进行优化，以提高运行效率。
环节五、课后练习
编写程序，得出答案，并使用本节所学优化方法进行优化。
求解五位数
假定一个大于0的五位数abcde满足条件abcde×a=eeeeee，求出该五位数。
1
100
3
