浙教版信息技术选修1 2.1 枚举算法 课件(共21张PPT)

枚举算法
生活中的枚举算法实例
找钥匙
警察审案
挑烂苹果
·
·
·
·
·
·
老师这个QQ的密码太简单了，为了防止被盗，于是我设置了一个复杂点的密码，结果将密码忘记了，请大家帮忙将我的密码找回来。我零星记得密码信息是：
（1）密码是八位整数，前面六位是198308；
（2）该密码能被7整除；
（3）该密码是偶数。
1、如何列举所有可能的密码
2、如何检验
问题：
？
寻找QQ密码
？
找密码的过程
2.可能密码值是19830801， 是否是偶数且是7的倍数；
1.最小密码值是19830800， 是否是偶数且是7的倍数；
3.可能密码值是19830802， 是否是偶数且是7的倍数；
10.最大密码值是19830899， 是否是偶数且是7的倍数。
······
列举
检验
枚举法
找密码的流程图
循环结构
一一列举
分支结构
逐一验证
枚举法的关键就是“列举和检验” 。
在列举的过程中，我们“既不能遗漏，也不应重复”。
枚举算法的概念
一一列举出所有可能的解
（列举范围）
逐个检验每个可能的解是否是真正的解
（检验条件）
重复模式
（循环结构）
选择模式
（分支结构）
循环嵌套分支
数7游戏
在联欢会上，小明提议大家来玩数7的游戏。
游戏规则：
从1开始数起，每个人数一个数，凡是遇到7的倍数就要喊“过”,这样一直数到100为止。
任务：
帮小明找出1——100所有要喊“过”的数
!
数7游戏
分析：
列举
检验
用变量i表示要列举的自然数。
列举范围：
1——100
检验条件：
i能否被7整除。
在列举过程中要既不遗漏，又不重复。
注意：
数7游戏
开始
结束
N
N
Y
Y
i<=100
i mod 7=0
i=i+1
i=1
输出i
列举范围：
1——100
检验条件：
i能否被7整除。
用变量i表示要列举的自然数。
数7游戏
开始
结束
N
N
Y
Y
i<=100
i mod 7=0
i=i+1
i=1
输出i
一一列举
逐个检验
（循环结构）
（分支结构）
循环中嵌套分支
数7游戏
程序代码：
i=1
Do while i<=100
if i mod 7=0 then
print i
end if
i=i+1
loop
开始
结束
N
N
Y
Y
i<=100
i mod 7=0
i=i+1
i=1
输出i
枚举算法的设计步骤
确定列举范围
明确检验条件
确定循环控制方式和列举方式
枚举算法只适用于可能解的个数不太多的情况。
注意：
一张单据上有一个5位数的编号，万位数是1，千位数是4，百位数是7，个位数是8，十位数已经模糊不清，只知道该5位数是7或11的倍数，找出所有满足这些条件的5位数并输出。
数据还原
NO. 147 ? 8
列举范围：
0——9
检验条件：
n能被5或者11整除。
即：(n mod 7=0) or (n mod 11=0)
分析：
用变量i表示十位上的数；变量n表示这个5位数。
数据还原
开始
i=0
i<10
(n mod 7=0) or
(n mod 11=0)
输出n
i=i+1
结束
N
N
Y
Y
程序代码：
i=0
Do while i<10
n=14708+i*10
if n mod 7=0 or n mod 11=0 then
Print n
end if
i=i+1
Loop
n=14708+i*10
练一练
用10元和50元两种纸币组成240元，共有几种组合方式？试用枚举算法列出所有不同的取法。
10x+50y=240
输出x,y
Y
x←1
Y
Start
N
End
y ← 1
Y
N
N
练一练
用10元和50元两种纸币组成240元，共有几种组合方式？试用枚举算法列出所有不同的取法。
小结：
1.枚举算法的概念
2.枚举算法的结构特征
一一列举；逐个检验
循环结构中嵌套分支结构
列举，由____________实现
检验，由____________实现
因此，枚举算法的一般特点是：
循环结构
分支结构
思考：
一张单据上有一个5位数的编号，千位数是1，百位数是7，个位数是8，万位数和十位数已经模糊不清，只知道该5位数是7或11的倍数，找出所有满足这些条件的5位数并输出。
NO. ? 17 ? 8
该题要列举的对象有两个，分别是万位数和个位数。用循环的嵌套。
提示：
谢 谢