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

枚举法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

结束


相关文章:
[第3讲]小升初计数_尝试性探索思维(枚举法)
[第3讲]小升初计数_尝试性探索思维(枚举法)_从业资格考试_资格考试/认证_...小升初计数重点考查内容——— 尝试性探索思维 (★★)(2010 年 101 中学小...
奥数解题方法:关于枚举法
举报文档 zyfeii贡献于2010-07-23 0.0分 (0人评价)暂无用户评价 我要评价...二年级奥数:枚举法专题解... 3页 1财富值 二年级奥数:枚举法专题解... 2...
枚举与贪心算法例题
} 4 枚举与贪心算法例题 袁辉勇整理 2010 年 1 月 例 3:Dual Palindromes ...但思路 1 用筛法用素数要开 O(n)的数组,在 n=1e8 是就是 90M,超出了...
2016年国家公务员考试备考:数学运算解题方法之枚举归纳法
湛江中公教育 2016 年国家公务员考试备考:数学运算解题方法之枚举归纳 法 在国家...3页 免费 2010年国家公务员考试数... 5页 免费 2010年国家公务员考试数.....
图形综合实验报告(三)(2010)
2010 实验报告3 2页 1下载券 c++语言综合性设计性实验... 17页 免费 实验报告...枚举 全局功能模式 modeType 枚举 曲线模式 addType 枚举 添加节点模式 moving ...
枚举类型及Enum方法
3) VS2010 中对于同一个枚举成员同时出现在两个或两个以上的枚举类型定义 中时不报错。如: enum Days { Sunday, Monday, Tuesday, Wednesday, Thursday, ...
21六年级奥数专题二十一:枚举法
分析与解:枚举法通常是对有限种情况进行枚举,但是本题讨论的对象是所有自然数, 自然数有无限多个,那么能否用枚举法呢?我们将自然数按照除以 3 的余数分类,有...
C语言枚举类型详解
3 #define THU 4 #define FRI 5 #define SAT 6...文档贡献者 herohaomiao 贡献于2010-10-10 ...C语言枚举类型详解经典法... 10页 免费 C语言...
2010秋行测答案
3.B【解析】本题属于实词与成语相结合的辨析题。根据固定搭配可知,第二个空处...37.B【解析】本题可采用不等式和枚举法。原始两边同时乘以B,则有4B/15=B/A...
2010-3-18前的教案
(5)Var u:array[0..2] of integer=(1,-3,2); 这种数组类型属于枚举...单域宽的用法: (1) 对于实数(real) ,用科学记数法输出。 (2)对于整型数(...
更多相关标签: