noip普及组复赛辅导-枚举专题.docx

枚举法专题
(穷举法 暴力求解)
一、枚举法的基本思想
枚举法的基本思想是根据提出的问题枚举所有可能状态, 并用问题给定的
条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。
枚举结构:循环 +判断语句。
二、枚举法的条件 :
虽然枚举法本质上属于搜索策略, 但是它与后面讲的回溯法有所不同。 因
为适用枚举法求解的问题必须满足
两个条件:
⑴可预先确定每个状态的元素个数 n;
⑵状态元素 a1,a2, …,an 的可能值为一个连续的值域。
三、枚举法的框架结构
设 ai1—状态元素 ai 的最小值; aik— 状态元素 ai 的最大值 (1≤i ≤n),即
a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ ai≤aik,
…… ,an1≤an≤ank
for a1← a11 to a1k do
for a2←a21 to a2k do
……………………
for ai← ai1 to aik do
……………………
for an← an1 to ank do
if 状态 (a1, … ,ai ,… ,an)满足检验条件
then 输出问题的
解;
四、枚举法的优缺点
枚举法的优点
⑴由于枚举算法一般是现实生活中问题的 “直译 ”,因此比较直观, 易于理
解;
⑵由于枚举算法建立在考察大量状态、 甚至是穷举所有状态的基础上, 所
以算法的正确性比较容易证明。
枚举法的缺点
枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价, 因此效
率比较低。
枚举法使用注意点
“直译 ”枚举:直接根据题意设定枚举对象、范围和约束条件。
注意认真审题,不要疏漏任何条件
1
例题 1:砝码称重 (noip1996)
【问题描述】 设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚 (其总重 <=1000),
求用这些砝码能称出不同的重量个数。
【文件输入】 输入 1g、 2g、3g、5g、 10g、20g 的砝码个数。
【文件输出】 输出能称出不同重量的个数。
【样例输入】 1 1 0 0 0 0
【样例输出】 3
【分析】 根据输入的砝码信息,每种砝码可用的最大个数是确定的,而且每
种砝码的个数是连续的,能取 0 到最大个数,所以符合枚举法的两个条件,
可以使用枚举法。枚举时,重量可以由 1g,2g,,, ,20g 砝码中的任何一个或
者多个构成, 枚举对象可以确定为 6 种重量的砝码, 范围为每种砝码的个数。
判定时,只需判断这次得到的重量是新得到的,还是前一次已经得到的,即
判重。由于重量 <=1000g,所以,可以开一个 a[1001]的数组来判重。
【参考源程序】
var b:array[0..1000]of boolean;
c:array[0..6]of longint;
i,j,k,l,m,n,sum,ans:longint;
begin
assign(input,'');
reset(input);
assign(output,'');
rewrite(output);
fillchar(b,sizeof(b),false);
readln(c[1],c[2],c[3