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

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

结束


相关文章:
三年级奥数.计数综合.枚举法.学生版
】 【巩固】 从 l~9 这 9 个数码中取出 3 个,使它们的和是 3 的倍数,则不同取法有___种。年级奥数.计数综合.枚举法(一) 级).学生版 (A Page ...
计数01讲_三上10_枚举法
7. 【11007】 (题解议,王坤,上第 10 讲枚举法,计数问题第 1 讲★)从 1,2,3,4,5, 6,7,8,9 中取出 3 个数,使其和为 9,一共有几种取法? ...
★《枚举法》教学设计
(一)教学目标 知识与技能: 1.能复述枚举法的基本概念及基本特征; 2.能理解枚举法的适用情况; 3.能描述枚举法的基本实现方法(循环嵌套分支)并能使用枚举法解决...
高思3年级·3枚举法(一)(计数问题第1讲)·答案_图文
高思3年级·3枚举法(一)(计数问题第1讲)·答案_三年级数学_数学_小学教育_教育专区。答案 答案 第 3 讲 枚举法(一) (计数问题第 1 讲) 【1】1~20 ...
标数法和枚举法
标数法和枚举法_司法考试_资格考试/认证_教育专区。计数方法的讲义广州...A 1 1 1 1 2 3 1 3 6 B 方法:1.先确定大方向,即向右和向下 2.标...
用枚举法解题
枚举法解题_学科竞赛_初中教育_教育专区。初中数学竞赛辅导资料( 13) 用枚举...X2 YZ, Y2 ZX, Z2 XY 解法三:还可按 3 个字母,2 个字母,1 个字母的...
小学奥数专题-枚举法通用版
小学奥数专题-枚举法通用版_学科竞赛_小学教育_教育专区。2015 年小学奥数计数专题——枚举法 1.如图,有 8 张卡片,上面分别写着自然数 l 至 8.从中取出 3 ...
三年级数学思维训练导引(奥数)第12讲 枚举法二
年级数学思维训练导引(奥数)第12讲 枚举法二_三年级数学_数学_小学教育_教育...10.老师拿来三块木板,上面分别写着数字 1、2、3.小悦可以用这些木板拼 出...
第二章第二讲 枚举法与容斥原理
解析:根据题目的特点,先用排列法把题中的条件问题列出来,再用枚举法完成题目要求。 排好队的人依次是 1,2,3,4,5,...28,29,30 次数 第一次 第二次 第...
简单枚举法习题
简单枚举法习题_四年级数学_数学_小学教育_教育专区。简单枚举 练习一 1,从甲地到乙地,有 3 条公路直达,从乙地到丙地有 2 条铁路 直达。从甲地到丙地有多少...
更多相关标签:
司法考试2010 3 56 | 枚举类型enum用法 | java枚举类型的用法 | c 枚举类型enum用法 | c 枚举用法 | 枚举法 | java枚举类型enum用法 | 枚举类型的用法 |