浙教版信息技术选修1 5.1 枚举算法的程序实现 课件(共14张PPT)

枚举算法的程序实现
枚举算法
???
定义：按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，就采纳这个解，否则就抛弃它。
例一
怎样在一大串没有标明的钥匙中找到我们教室的钥匙呢？
一一列举，尝试
1）不遗漏
2）不重复
枚举算法应用
例二
一张单据上有一个4位数的编号，其十位数处已变的模糊不清,如图所示。但是知道这个4位数是16的倍数或23的倍数。你能恢复这个编号吗？
假设这个数为n=25i6
则i可能为0-9
n=2500+i*10+6
For 语句
n=2506+i*10
if n mod 16=0 or n mod 23=0 then
print n
endif
For i=0 to 9

Next i
例三
一张单据上有一个4位数的编号，其中有两位数字已变的模糊不清,如图所示。但是知道这个4位数是16的倍数或23的倍数。你能恢复这个编号吗？
假设这个数为n=j5i6
则j可能为1-9，i可能为0-9
n=1000*j+500+i*10+6
1
0
1
2
……
9
千位j
十位i
四位数
vb代码
综合代码
j=1
For i=0 to 9

Next i
n=j*1000+506+i*10
if n mod 16=0 or n mod 23=0 then
print n
endif
15i6
2
0
1
2
……
9
9
0
1
2
……
9
25i6
95i6
j=2
For i=0 to 9

Next i
j=9
For i=0 to 9

Next i
For j=1 to 9

Next j
For i=0 to 9

Next i
n=j*1000+506+i*10
if n mod 16=0 or n mod 23=0 then
print n
endif
For 语句
For j=1 to 9
For i=0 to 9
n=506+i*10+j*1000
if n mod 16=0 or n mod 23=0 then
print n
endif
Next i
Next j
双重循环
百钱百鸡问题
　 中国古代算书《张丘建算经》中有一道著名的百鸡问题：
公鸡每只值5文钱，母鸡每只值3文钱，而3只小鸡值1文钱。现在用100文钱买100只鸡，问：这100只鸡中，公鸡、母鸡和小鸡各有多少只？
练习
可以采用枚举法将所有可能的情况一一列出。
g
m
x
1
1
1
2
1
3
则公鸡g在1至100/5只之间，
母鸡m在1至100/3之间，
小鸡x为100-g-m。
练习
for g = 0 to 33
for m = 0 to 50
if g*5+m*3+(100-m-g)/3=100 then
print g, m ,100-m-g
endif
next m
next g
小结
枚举算法：按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，就采纳这个解，否则就抛弃它。
枚举算法：一一列举；不遗漏；不重复。
谢 谢