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

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

结束


相关文章:
枚举法
这条题目很显然需要用枚举法来解答,枚举对象即为公鸡、母鸡、小鸡,将它们 分别设为 a、b、c,以三种鸡的总数 a+b+c 和买鸡用去的钱 3a+2b+(c÷3) , ...
计数01讲_三上10_枚举法
7. 【11007】 (题解议,王坤,上第 10 讲枚举法,计数问题第 1 讲★)从 1,2,3,4,5, 6,7,8,9 中取出 3 个数,使其和为 9,一共有几种取法? ...
容斥原理和枚举法的矛盾?
2010 30 ?4 所以结果应为 1005+670+402-670-402-268+268=1005 最后亮着的灯盏数为:2010-1005=1005 当然,也可以利用枚举法:设 30 盏灯(2、3、5 的最小...
第二章第二讲 枚举法与容斥原理
解析:根据题目的特点,先用排列法把题中的条件问题列出来,再用枚举法完成题目要求。 排好队的人依次是 1,2,3,4,5,...28,29,30 次数 第一次 第二次 第...
第四讲运用枚举法解应用题
第2页 共6页 奥数(二) 第四讲 运用枚举法解应用题 八. 用 0,1,2,4 可组成多少个不同的三位数? 解: 答: 九. 现有 1 克、3 克、9 克的砝码各...
高思3年级·3枚举法(一)(计数问题第1讲)·答案
高思3年级·3枚举法(一)(计数问题第1讲)·答案_三年级数学_数学_小学教育_教育专区。答案 答案 第 3 讲 枚举法(一) (计数问题第 1 讲) 【1】1~20 ...
三年级第27讲《枚举法解题》课后练习
请你将每种方法 用枚举法列在下面。 (☆☆) AB C 0 开始:003、012、021、030 1 开始:102、111、120 2 开始:201、210 3 开始:300 一共 10 种 6、...
计数枚举法经典例题讲解1
计数枚举法经典例题讲解1 来源:奥数网原创 文章作者:奥数网 2010-09-01 13:...第1章经典例题详解 暂无评价 3页 免费 计数之标数法经典例题讲... 暂无评价...
标数法和枚举法
标数法和枚举法_司法考试_资格考试/认证_教育专区。计数方法的讲义广州...A 1 1 1 1 2 3 1 3 6 B 方法:1.先确定大方向,即向右和向下 2.标...
三年级数学思维训练导引(奥数)第04讲 枚举法一
年级数学思维训练导引(奥数)第04讲 枚举法一_三年级数学_数学_小学教育_教育...11.(1)有 2 个相同的白球和 1 个红球.如果把这 3 个小球排成一排,有...
更多相关标签:
vs2010 枚举 | 枚举类型enum用法 | java枚举类型的用法 | c 枚举用法 | java枚举类型enum用法 | 枚举法 | c 枚举类型enum用法 | 枚举类型的用法 |