教科版高中信息技术选修1 3.2 用穷举法解决问题 课件(共24张PPT)

情景导入
暑假我带着一个有三位数字的密码行李箱去旅行，旅行途中发现自己忘记了开锁的密码，但我还记得第一位密码是"7"，后面两位数字已经不记得，我该怎么办？
模 拟
§3.2 用穷举法解决问题
什么是穷举法
穷举法：也叫枚举法，列举法，它将求解对象一一列举出来，然后逐一加以分析、处理、并验证结果是否满足给定的条件，枚举完所有对象，问题将最终得以解决。
用穷举法解决问题的步骤
Step1：分析问题
Step2：确定要枚举的求解对象，同时确定求解对象的枚举范围
Step3：一一枚举，然后加以分析、处理、验证
举例：水仙花数
已知水仙花数满足以下两个条件
水仙花数是一个三位正整数
这个三位数刚好等于各个位上的数字立方和
例如：153就是一个水仙花数
编程输出所有的水仙花数。
举例：水仙花数
分析问题：假设这个三位数为m，那么
百位上的数字a为：
十位上的数字b为：
个位上的数字c为：
m满足的条件为:
m为三位数
m=a^3+b^3+c^3
a=m\100
b=(m-a*100)\10
c=m mod 10
举例：水仙花数
确定枚举的求解对象：
每一个三位数m
确定求解对象的枚举范围
100≤m≤999
验证的条件
m=a^3+b^3+c^3
开始
m=100
m<=999?
m=a3+b3+c3?
输出m
是
m=m+1
否
求出百位数字a
求出十位数字b
求出个位数字c
是
结束
否
举例：水仙花数
Private Sub Command1_Click()
Dim m As Integer
Dim a, b, c As Integer
For m = _____ To _____ '枚举三位数m
a = m \ 100 '计算百位数字a
b = (m - 100 * a) \ 10 '计算十位数字b
c = m Mod 10 '计算个位数字c
If m = __________________ Then '验证条件
Print m & "是水仙花数"
End If
Next m
End Sub
运行程序
100
999
a ^ 3 + b ^ 3 + c ^ 3
举例：水仙花数
分析问题：假设这个三位数m的百位上数字为a，十位上数字为b，个位上数字为c，则：
这个三位数m=
a，b，c满足的条件为:
1≤a≤9
0≤b≤9
0≤c≤9
m=a^3+b^3+c^3
a*100+b*10+c
举例：水仙花数
确定枚举的求解对象：
百位数字a
十位数字b
个位数字c
验证的条件
a*100+b*10+c=a^3+b^3+c^3
确定求解对象的范围
1≤a≤9
0≤b≤9
0≤c≤9
Private Sub Command1_Click()
Dim m As Integer
Dim a, b, c As Integer
For a = _____ To _____ '枚举百位数字a
For b=______ To ______ '枚举十位数字b
For c=______ To ______ '枚举个位数字c
m=a*100+b*10+c
If m = __________________ Then '验证条件
Print m & "是水仙花数"
End If
Next c
Next b
Next a
End Sub
1
9
a ^ 3 + b ^ 3 + c ^ 3
0
9
0
9
探究任务：百钱百鸡
用100元钱买100只鸡，公鸡，母鸡，小鸡都要有。公鸡5元1只，母鸡3元1只，小鸡1元3只。请问公鸡，母鸡，小鸡各应该买多少只？
编程输出每一种方案。
探究任务：百钱百鸡
分析问题：假设公鸡有a只，母鸡有b只，小鸡有c只，则a，b，c满足的条件为：
a,b,c均大于0
a+b+c=100
5*a+3*b+c/3=100
探究任务：百钱百鸡
确定枚举的求解对象
公鸡只数a
母鸡只数b
小鸡只数c
确定求解对象的范围
1≤a≤20
1≤b≤33
1≤c≤100
验证条件
a+b+c=100
5*a+3*b+c/3=100
Private Sub Command1_Click()
Dim a, b, c As Integer
For a = ____ To ____ '枚举公鸡只数
For b = ____ To ____ '枚举母鸡只数
For c = ____ To _____ '枚举小鸡只数
If (a + b + c = 100 And 5 * a + 3 * b + c \ 3 = 100) Then
Print "公鸡："; a; "只",
Print "母鸡："; b; "只",
Print "小鸡："; c; "只"
End If
Next c
Next b
Next a
End Sub
运行程序
/
'此行有一处错误
1
20
1
33
1
100
实践探究，深化思维
学校科技文化节之英语演讲大赛就要开始了，高二年级共有M=328名学生参赛。比赛规则规定先进行小组比赛，然后取小组前三名进行决赛。因此，组委会需要对参赛选手进行分组。请按下面的分组规则设计算法，求解可能的分组方案供组委会参考。
每组最少10人，最多30人
如果不能平均分组，则各小组间人数之差不得多于1人
实践探究，深化思维
假设将M=328人进行分组，其中小组人数为15，则分组方案有______种，分别为：
___组____人/组，____组____人/组
___组____人/组，____组____人/组
___组____人/组，____组____人/组
假设将M=328人进行分组，分的组数为15组，则分组方案有______种，分别为：
___组____人/组，____组____人/组
3
2
14
20
15
17
14
6
15
8
15
13
16
1
2
21
13
22
演讲比赛分组
确定枚举的求解对象：
小组的人数X
或
小组的组数N
确定求解对象的枚举范围
≤N≤
11
32
√
演讲比赛分组
进行分组：
M=328分成N组
设X=M \ N，R=M mod N，如果R=0说明能平均分配；否则，将余数R人就要平均分配到R个组中，每组多分1个人，这样：
R=0时，分成N组，每组X个人；
R≠0时，分成N组，其中有 ______ 组X人，有 R 组 X+1人
N-R
Private Sub Command1_Click()
Dim M, N,X, R As Integer
M = 328
For N = ____ To _____ '枚举分得的组数
R = M Mod N
X= M \ N
If R = 0 Then
Print "分成" & N; "组：平均每组" & X & "人。"
Else
Print "分成" & N; "组：其中有" & N - R & "组每组" & X; "人，有" & R & "组每组" & X+1 & "人。"
End If
Next N
End Sub
运行程序
11
32
归纳总结
用穷举法解决问题的关键：
①确定需要枚举的所有求解对象
②找出求解对象的枚举范围
③分析出满足问题所需的条件
具体方法：
针对关键①，可以确定循环层数；
针对关键②，可以确定循环初值和终值；
针对关键③，可以确定循环体内的选择语句。
归纳总结
提出问题：我们使用信用卡在柜员机上取钱时，为什么系统要限制输入密码的次数？
Thanks