NOIP普及组复赛辅导-枚举专题.doc

1 枚举法专题(穷举法暴力求解) 一、枚举法的基本思想枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。枚举结构: 循环+判断语句。二、枚举法的条件: 虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件: ⑴可预先确定每个状态的元素个数 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 输出问题的解; 四、枚举法的优缺点枚举法的优点⑴由于枚举算法一般是现实生活中问题的“直译”,因此比较直观,易于理解; ⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。枚举法的缺点枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。枚举法使用注意点“直译”枚举:直接根据题意设定枚举对象、范围和约束条件。注意认真审题,不要疏漏任何条件 2 例题 1 :砝码称重(noip1996) 【问题描述】设有 1g、 2g、 3g、 5g、 10g 、 20g 的砝码各若干枚(其总重<=1000 ), 求用这些砝码能称出不同的重量个数。【文件输入】输入 1g、 2g、 3g、 5g、 10g 、 20g 的砝码个数。【文件输出】输出能称出不同重量的个数。【样例输入】 110000 【样例输出】 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],c[4],c[5],c[6]); for i:=0 to c[1] do for j:=0 to c[2] do for k:=0 to