资源简介

(共21张PPT)
微项目2
用枚举算法寻找问题多解
例1 逢7跳过游戏：
第1位同学从1开始数起，依次每人尽快数下一个数，凡是遇到7的倍数（如7、21等）或是数字中带7的数字(如17、71等)，就要喊“过”说错或卡住了即被淘汰，这样一直数到100为止。
用枚举算法寻找问题多解
算法分析
把问题所有的可能解一一列举出来， 并对每一个可能解进行判断，是真正解的时候输出“过”
例1 逢7跳过游戏：
第1位同学从1开始数起，依次每人尽快数下一个数，凡是遇到7的倍数（如7、21等）或是数字中带7的数字(如17、71等)，就要喊“过”说错或卡住了即被淘汰，这样一直数到100为止。
用枚举算法寻找问题多解
用枚举算法寻找问题多解
这种算法就叫做“枚举算法”，又称为“穷举法”
算法思想：把问题的所有的可能解一一列举出来，并对每一个可能解进行判断，以确定是否是问题的真正解。
逢7跳过游戏
一一列举：
1~100
逐个检验：
是7的倍数或包含7
7的倍数
个位为7
十位为7
for i in range(1,101):
i%7==0
i%10==7
i//10==7
用枚举算法寻找问题多解
用枚举算法寻找问题多解
利用枚举算法思想解决问题：
1、确定枚举范围
1~100
2、确定判断条件
是7的倍数或包含7
3、编程求解
用枚举算法寻找问题多解
例2、破解密码
1、确定枚举范围
812000~812990
求解密码，小明有一张藏宝图，上面有宝藏开启的密码，但是他不小心打翻了墨水，导致十位和百位模糊不清了，幸好藏宝图有提示：该密码是31或187的倍数，且十位是奇数。
2、确定判断条件
是31或187的倍数，且十位是奇数
for i in range(812000,812991,10):
if i%31==0 i%187==0 i//10%2!=0:
用枚举算法寻找问题多解
例2、破解密码
1、确定枚举范围
812000~812990
求解密码，小明有一张藏宝图，上面有宝藏开启的密码，但是他不小心打翻了墨水，导致十位和百位模糊不清了，幸好藏宝图有提示：该密码是31或187的倍数，且十位是奇数。
2、确定判断条件
是31或187的倍数，且十位是奇数
for i in range(812000,812991,10):
if i%31==0 i%187==0 i//10%2!=0:
or
(
)
and
用枚举算法寻找问题多解
例2、求解被墨水密码
结论：尽可能使罗列的范围最小，选择最优化的方法
100
991
用枚举算法寻找问题多解
例3、百钱买百鸡
用100元钱买100只鸡，公鸡，母鸡，小鸡都要有。公鸡5元1只，母鸡3元1只，小鸡1元3只。请问公鸡，母鸡，小鸡各应该买多少只？
确定枚举对象 确定枚举范围 确定判断条件
公鸡（5元） 0≤x≤20 ① x+y+z=100
② 5x+3y+ z=100
母鸡（3元） 0≤y≤33
小鸡（1/3元） 0≤z≤100
用枚举算法寻找问题多解
用枚举算法寻找问题多解
例4、水仙花数
1、确定枚举范围
100-1000
输出1000以内的所有水仙花数。水仙花数是指一个3位数，它的每个位上的数字的3次幂之和等于它本身。例如：1^3 + 5^3+ 3^3 = 153
2、确定判断条件
每个位上的数字的3次幂之和等于它本身：
a=i%10
for i in range(100,1000):
个位 十位 百位
b=i//10%10
c=i//100
if a**3+b**3+c**3==i:
用枚举算法寻找问题多解
用枚举算法寻找问题多解
例5、鸡兔同笼问题
1、确定枚举范围
heads=35
Legs=94
兔数量：1-heads-1
编程解决：今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？
2、确定判断条件
鸡和兔的总脚数之和等于94
leg=tu*4+(heads-tu)*2
for tu in range(1,heads):
if legs==leg:
1、求当前兔子数量下鸡和兔的总脚数
2、判断脚数是否相等
用枚举算法寻找问题多解
小结
1. 枚举算法的基本思想：一一 列举，逐个检验
2. 尽可能使罗列的范围最小，选择最优化的方法
3. 可以借助列表实现枚举算法
用枚举算法寻找问题多解
随堂练习
把问题的所有可能解都—一列举出来，并按照问题要求的条件逐个判断每个答案是否是正确的解，这就是（）
A.排序算法
B.递归算法
C.迭代算法
D.枚举算法
用枚举算法寻找问题多解
随堂练习
下列问题中，适合使用枚举法解决的是（）
A.计算1+2+3+.….+1000的值
B.计算学校所有同学的平均身高和平均体重
C.查找100以内所有能被6整除的数
D.超市的收银系统，结算顾客所购商品的费用
用枚举算法寻找问题多解
随堂练习
我们利用枚举的策略解决问题时，下列说法错误的是（）
A.要按一定的顺序枚举
B.枚举时只可列表，不可画图
D.做到不重复，不遗漏
C.要对结果进行比较，做出选择
用枚举算法寻找问题多解
随堂练习
利用枚举算法解决问题时，确定枚举范围可使用下列语句中的（）
A、If B、For
C、Elif C. import
用枚举算法寻找问题多解
随堂练习
实现枚举算法一般采用（)的算法结构模型。
A.分支套循环
B.循环套循环
C.循环套分支
D.分支套分支
用枚举算法寻找问题多解
随堂练习
登录密码安全对信息系统安全的作用至关重要，下列说法不恰当的是（）
A.密码越复杂，用枚举法破解的概率越低
B.要设置看起来杂乱无章，而对自己有特殊含义、容易记的密码
C.输入的密码不宜明文显示在终端屏幕上
D.不同的信息系统可设置相同的登录密码

展开更多......

收起↑