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

PAGE  PAGE 6 枚举法专题 （穷举法 暴力求解） 一、枚举法的基本思想 枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。 枚举结构：循环+判断语句。 二、枚举法的条件: 虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足 两个条件： ⑴可预先确定每个状态的元素个数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：砝码称重(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,medic.in); reset(input); assign(output,medic.out); 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 c[3] do for l:=0 to c[4] do for m:=0 to c[5] do for n:=0 to c[6] do begin sum:=1*i+2*j+3*k+5*l+10*m+20*n; b[sum]:=true; end; ans:=0; for i:=1 to 1000 do if b[i] then ans:=ans+1; writeln(ans); end. close(input); close(output); end. 例题2：数字统计(noip2010) (two.pas/c/cpp) 【问题描述】 请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。 比如给定范围[2, 22]，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次。 【算法思路】 枚举法，依次将L至R转化为字符串，查找当中有多少个”2”. 【参考源程序】 program two; var