《noip普级组枚举专题》由会员分享，可在线阅读，更多相关《noip普级组枚举专题（18页珍藏版）》请在金锄头文库上搜索。
1、NOIP基础算法综合 枚举法,江苏省南通市通州区金郊初中 信息技术教研组,关联文件操作,assign(input,文件名.in); assign(output,文件名.out); reset(input); rewrite(output); close(input); close(output); 注意：主程序中exit前、全程序中halt前务必加close！,2018年9月12日星期三,衡阳市第一中学计算机代表队DX8080,2,数据类型,整形：integer：-3276832767 longint：-21474836482147483647 qword：018446744073709551
2、615 int64：-92233720368547758089223372036854775807（较少用，不可作为循环变量） 实型：real 布尔型：boolean（true、false） 字符型：char 字符串：string（255位）、ansistring,2018年9月12日星期三,衡阳市第一中学计算机代表队DX8080,3,一、枚举法的基本思想,枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。 枚举结构：循环+判断语句。,二、枚举法的条件:,虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因
3、为适用枚举法求解的问题必须满足两个条件： 可预先确定每个状态的元素个数n； 状态元素a1，a2，an的可能值为一个连续的值域。,三、枚举法的框架结构,设ai1状态元素ai的最小值；aik状态元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aiaik， ，an1anank for a1a11 to a1k do for a2a21 to a2k do for aiai1 to aik do for anan1 to ank do if 状态(a1，ai，an)满足检验条件 then 输出问题的解；,枚举法的优点 由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，
4、易于理解； 由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。,枚举法的缺点 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。,四、枚举法的优缺点,“直译”枚举：直接根据题意设定枚举对象、范围和约束条件。 注意认真审题，不要疏漏任何条件,例题1：砝码称重(noip1996),【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），求用这些砝码能称出不同的重量个数。 【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。 【文件输出】输出能称出不同重量的个数。 【样例输入】1 1 0
5、0 0 0 【样例输出】3,【分析】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g,20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量=1000g，所以，可以开一个a1001的数组来判重。,核心参考代码：,fillchar(b,sizeof(b),false); readln(c1,c2,c3,c4,c5,c6); for i:=0 to c1 do f
6、or j:=0 to c2 do for k:=0 to c3 do for l:=0 to c4 do for m:=0 to c5 do for n:=0 to c6 do begin sum:=1*i+2*j+3*k+5*l+10*m+20*n; bsum:=true; end; ans:=0; for i:=1 to 1000 do if bi then ans:=ans+1; writeln(ans);,【问题描述】给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示： 注
7、意： 1. 加号与等号各自需要两根火柴棍 2. 如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C0） 3. n根火柴棍必须全部用上 【输入】输入文件matches.in共一行，又一个整数n（n24）。 【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。,例题2：火柴棒等式（NOIP2008）,例题2：火柴棒等式（NOIP2008）,【问题简述】给你n(n=24)根火柴棒,叫你拼出 “A + B = C”这样的等式,求方案数。,【思路点拨】本题主要考查对枚举法的掌握，可以枚举A和B的取值，考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范围有所要求，必须要
8、仔细分析A和B的取值。,例题2：火柴棒等式（NOIP2008）,本题最多24根火柴，等号和加号共用4根火柴，所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能：09这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6，很明显数字1用的火柴棒最少只要2根,为了加快速度，可以将0到2000的所有整数需要的火柴棒数目提前算好保存在数组中。,解题思路：,n=24，数据范围很小， 首先用两个循环枚举两个加数的每种情况。 然后把两加数相加，算出和，后用三个数所使用的火柴棒数相加(可以用一个函数计算)，判断所得的和是否等于(n-4)【符号】。 如果相等，就把记录答案的计数器变
9、量自加1，重复步骤直到循环结束。 下面看代码。,const inp=medic.in; oup=medic.out; num:array09 of integer=(6,2,5,5,4,5,6,3,7,6);/09火柴棒数 maxn=1000; var f:array0maxn*2 of longint; i,j,k,n,ans:longint; s:string; procedure init;/02000每个数需要的火柴棒数 var i,j,k:longint; s:string; begin for i:= 0 to maxn*2 do begin str(i,s); fi:=0; fo
10、r j:= 1 to length(s) do inc(fi,numsj); end; end;,begin assign(input,inp); reset(input); assign(output,oup);rewrite(output); readln(n); init; ans:=0; n:=n-4;/总火柴棒数减去+和=所需的火柴棒数 for i:= 0 to maxn do/枚举A begin if fi=n then continue;/剪枝 for j:= 0 to maxn do/枚举B begin if fi+fj=n then continue;/剪枝 k:=i+j;
11、if fi+fj+fk=n then inc(ans);/符合条件,总数加一 end; end; write(ans); close(input); close(output); end.,program matches; var n:longint; begin assign(input,matches.in); reset(input); assign(output,matches.out); rewrite(output); read(n); n:=n-4; if n9 then begin writeln(0); close(output); exit; end;,case n of 9:writeln(1); 10:writeln(2); 11:writeln(8); 12:writeln(9); 13:writeln(6); 14:writeln(9); 15:writeln(29); 16:writeln(39); 17:writeln(38); 18:writeln(65); 19:writeln(88); 20:writeln(128); end; close(output); end.,骗分法,五、枚举算法的优化,枚举算法的时间复杂度：状态总数*单个状态的耗时。,提取有效信息； 减少重复计算； 将原问题化为更小的问题； 根据问题的性质进行截枝； 引进其他算法,
