当前位置:首页 >> 高中教育 >>

枚举法2010-3


枚举法

2010年3月8日-12日

什么是枚举算法
? 有一类问题可以采用一种盲目的搜索方法, 在搜索结果的过程中,把各种可能的情况 都考虑到,并对所得的结果逐一进行判断, 过滤掉那些不合要求的,保留那些合乎要 求的结果,这种方法叫做枚举法--------(enumerative algorithm)。 ? 枚举算法就是按照

问题本身的性质,一一 列举出该问题所有可能的解,并在逐一列 举的过程中,检验每个可能解是否是问题 的真正解。若是,我们采纳这个解,否则 抛弃它。在列举的过程中,既不能遗漏也 不应重复。

例题:
? 枚举算法的步骤 ? 枚举算法的特点

? 初步确定一个范围, ? 逐一进行判断; ? 再对它逐一进行判断, ? 找到结果。 ? 不遗漏,不重复

枚举的结构特点:
关键
列举 检验 为了保证对所有的可能情 况逐一列举和检验,势必 要重复进行这两个操作, 直到所有情况都检验完为 止。因此一般采用循环结 构实现。 N 检验就是对某一给定的 条件进行判断,根据判 断的不同结果执行不同 的操作,左图的“检验” 可以用分支结构表示。

是否继续列举? Y

是否继续列举? Y

列举 条件 Y …… N

……

练习3:百鸡百钱问题,公鸡每只5元,母鸡每只3元,小鸡1元3 只,现在用100元钱买100只鸡,每种鸡至少买1只,求公鸡、母 鸡、小鸡各买几只?
满足题意。

本例中,公鸡、母鸡、小鸡的数量都不定的,使用枚举 分析问题: 时,对可能的公鸡、母鸡、小鸡的数一一列举,然后判断是否

输入: 本例没有输入。 处理: (1)确定列举范围:
设公鸡买了x只,母鸡买了y只,小鸡买了z只。 X取值范围:[0,20) Y取值范围:[0,33] z取值范围:100-x-y

(2)明确检验的条件:
分别对x,y,z进行检验,判断是否满足 5*x+3*y+z/3=100, 满足的话就输出x,y,z的值。

(3)确定循环控制方式和列举方式:
双重循环的嵌套来完成列举。外循环用于列举公鸡数x,内 循环用于列举母鸡数y。 输出:

满足题意的公鸡、母鸡、小鸡数。

判断一下右图的流程图 对吗?

开始 x←0 ;y←0

出题意思:可以用列举 变量值的办法让学生加 深对循环变量的值的理 解。
分析:列举x和y的值。
X Y

N x<20且y<=33 Y z←100-x-y N 5*x+3*y+z/3=100 Y 输出x,y,z x←x+1 ;y←y+1

0
1 2 3 ?

0
1 2 3 ? 结束

将流程图填写完整。

开始 x←0

N
x<20? Y y←0 N

Y z←100-x-y
N Y 输出x,y,z y←y+1

x←x+1 结束

参考答案

开始 x←0

N
x<20? Y y←0 N y<=33?

Y z←100-x-y
5*x+3*y+z/3=100 Y 输出x,y,z y←y+1 N

x←x+1 结束

1.(x初始化) x←1。 2.(x变化完?) 若 x>293 则 算法终止。 3.(y初始化) y←1。 4.(y变化完?) 若 y>118 则转到 12。 5.(z初始化) z←1。 6.(z变化完?)若 z>74 则转到 10。 7.(检验一组可能解) 若 2x+5y+8z=600 则输出x、y、z。 8.(下一个可能的z) z←z+1。 9.(继续) 转到6。 10.(下一个可能的y) y←y+1。 11.(继续) 转到4。 12.(下一个可能的x) x←x+1。 13.(继续) 转到2。

若一个三位数x=100a+10b+c(a、b、c都是个位数),满足 a3+b3+c3=x,则x称为水仙花数。找出所有的水仙花数。
开始 X=100 x <= 999? Y 取百位数字: 取十位数字: 取个位数字: N

分析问题:
输入:

本例没有输入。
(1)确定列举范围:
所有三位正整数100-999之间, 可以用变量x表示

处理:

(2)明确检验的条件:
N 取出三位数字上的数字a,b,c,进行检 验判断a3+b3+c3=x,成立则输出x

Y 输出x

(3)确定循环控制方式和列举 方式:
X的初始值为100,循环条件为x<=999, 递增值为1,同时也列举了所有的三位 数。每次循环就列举下一个三位数。

x=x+1

输出:
结束

输出符合条件的三位数。

参考答案

开始
X=100 N x <= 999? Y 取百位数字: a=int(x/100) 取十位数字: b=int((x mod 100)/10) 取个位数字: c=x mod 10 a3+b3+c3=x Y 输出x x=x+1 出题意图: 结束 此题为单重循环枚举的巩固练习,并在判断条件设定 中复习了一些特殊的运算符和函数如mod、div、取整 函数。有承前启后的作用。 N

a=x div 100 b=x div 10 mod 10

1. 已知:□3 * 6528 = 3□ * 8256 等式中方框内是同一个数字, 求该数字。 2. 找出乘积为399的两个相邻奇数。 3. 从键盘输入10个无序数,求平 均值。

起始
j?0 j<10
y n

练习1.解答
? ? ? ? ? ? ? ? ? Start For j=0 to 9 n1=(j*10+3)*6528 n2=(30+j)* 8256 if n1=n2 then print j endif Next j end

n1=(j*10+3)*6528 n2=(30+j)* 8256
y

n1=n2?
输出 j 的值 n

j?j+1
结束

找出乘积为399的两个相邻奇数。
起始
n?1
y n x (n+2)=399 n 输出 n,n+2 的值 ? ? 判断条件 n x (n+2)=399

n?n+2
结束

Print n , n+2

从键盘输入10个无序数,求平均值。
开始 i←1

Sum ← 0
Sum=sum/10 输出 sum

i ≤ 10 Y
输入n

N

输出sum/10

Sum=sum+n i=i+1

结束


相关文章:
三年级奥数.计数综合.枚举法(B级).学生版
年级奥数.计数综合.枚举法(B级).学生版_学科竞赛_小学教育_教育专区。小学奥数试题,小学奥数试题,奥数练习,奥数教案,奥数辅导 枚举法 课前预习 胖子的枚举法(...
三年级奥数.计数综合.枚举法(B级).学生版
年级奥数.计数综合.枚举法(B级).学生版_学科竞赛_小学教育_教育专区。小学奥数,小学奥数,初中奥数练习,小学奥数试题,奥数,奥数专题,奥数教案,奥数讲义 ...
小学奥数系列:第09讲 枚举法
奥数精品 第 09 讲 计数问题第 01 讲 枚举法 例 1 如图 9—1,有八张卡片,上面写着自然数 1 至 8.从中取出三张,要使三张卡片 上的数字之和为 9.问...
[第3讲]小升初计数_尝试性探索思维(枚举法)
[第3讲]小升初计数_尝试性探索思维(枚举法)_从业资格考试_资格考试/认证_...小升初计数重点考查内容——— 尝试性探索思维 (★★)(2010 年 101 中学小...
小学奥数系列:第十讲 枚举法
可知 1000 以内有 333 个数是 3 的倍数; 333-3=330,则知 10~1000 之内有 330 个数是 3 的倍数. 由上述这些例题可体会枚举法的优点和缺点及其适用范围....
你所不知的枚举法
你所不知的枚举法 题型评述:解题时,直接列举满足条件的所有情况,从而得到答案的...星期一 星期二 星期三 星期四 星期五 7.5√ 7.8× 7.15× 7.22× 7.29...
国家公务员考试:枚举法(二)
国家公务员考试:枚举法(二)_公务员考试_资格考试/...下面我们来看几道例题: 【例】 (2010-春季联考-7...在 100 以内,从 0 到 99,3 的倍数共有 34(...
2010-2013选择题解析
2010-2013选择题解析_公务员考试_资格考试/认证_教育专区。2010-2013 选择题及 ...2=1*2 +1*20+0+2-1+1*2-2=2+1+0+0.25=3.25 A、枚举法就是按...
2010年陕西省高考模拟联考试题(二) (3)_图文
2010年陕西省高考模拟联考试题(二) (3)。2010 年陕西省高考模拟联考试题(二)...采用枚举法计算古典概型的概率 四棱锥,线面垂直的证明,点到平面的距离 19 20...
2010秋行测答案
3.B【解析】本题属于实词与成语相结合的辨析题。根据固定搭配可知,第二个空处...37.B【解析】本题可采用不等式和枚举法。原始两边同时乘以B,则有4B/15=B/A...
更多相关标签: