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

枚举法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-4第3讲枚举法讲义
3-4第3枚举法讲义_数学_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 3-4第3枚举法讲义_数学_小学教育_教育专区。...
(星级三年级)枚举法
(星级年级)枚举法_学科竞赛_小学教育_教育专区。星级强化训练(三年级) 简单计数 【A】★ 1. 小明决定去香山、颐和园、圆明园这三个景点旅游,要走遍这三个景点...
高思3年级·3枚举法(一)(计数问题第1讲)·答案_图文
高思3年级·3枚举法(一)(计数问题第1讲)·答案_三年级数学_数学_小学教育_教育专区。答案 答案 第 3 讲 枚举法(一) (计数问题第 1 讲) 【1】1~20 ...
用枚举法解题
枚举法解题_学科竞赛_初中教育_教育专区。初中数学竞赛辅导资料( 13) 用枚举...X2 YZ, Y2 ZX, Z2 XY 解法三:还可按 3 个字母,2 个字母,1 个字母的...
枚举法求概率评价作业
枚举法求概率评价作业_学科竞赛_小学教育_教育专区。枚举法求概率评价作业一、...三、拓展延伸(共 10 分) 7.(10 分)足球比赛前,由裁判员掷两枚硬币,若...
计数01讲_三上10_枚举法
年级上学期 第十讲,计数问题第 01 讲枚举法 【内容概述】 掌握枚举的一般方法,解决整数的分柝、数字的排列与选取、几何图形剪拚等相关计数问题.注 意到有序...
★《枚举法》教学设计
经过第二环节对枚举法基本概念,基本特征以及枚举法的适用情况的内化, 在第三环节中, 要求学生利用所学枚举法的知识例举生活实例,对学生自学知识 运用能力情况进行...
第二章第二讲 枚举法与容斥原理
解析:根据题目的特点,先用排列法把题中的条件问题列出来,再用枚举法完成题目要求。 排好队的人依次是 1,2,3,4,5,...28,29,30 次数 第一次 第二次 第...
简单枚举法习题
简单枚举法习题_四年级数学_数学_小学教育_教育专区。简单枚举 练习一 1,从甲地到乙地,有 3 条公路直达,从乙地到丙地有 2 条铁路 直达。从甲地到丙地有多少...
四年级枚举法
四年级枚举法_学科竞赛_小学教育_教育专区。枚举法解题例 1、营业员有 1 个 ...练习 2、新华书店有 3 种不同的英语书,4 种不同的数学读物,卡卡想买一种...
更多相关标签:
2010年司法考试卷3 | 枚举类型enum用法 | java枚举类型的用法 | 枚举法 | c 枚举用法 | c 枚举类型enum用法 | java枚举类型enum用法 | 枚举的用法 |