haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

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

发布时间:2013-10-19 14:39:27  

枚举法专题

(穷举法 暴力求解)

一、枚举法的基本思想

? 枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。 ? 枚举结构:循环+判断语句。

二、枚举法的条件:

? 虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足

? 两个条件:

? ⑴可预先确定每个状态的元素个数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,'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.

2

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

l,r:1..10000;

i,j,h,c:longint;

s:string;

begin

assign(input,'medic.in');

assign(output,'medic.out');

reset(input);

rewrite(output);

readln(l,r);

c:=0;

for i:=l to r do

begin

str(i,s);

h:=length(s);

for j:=1 to h do

if s[j]='2'

then c:=c+1;

end;

writeln(c);

close(input);

close(output);

end.

3

枚举法总结:

枚举法是一种比较笨拙的算法,因为它需要列举出许多个可能解来一一验证,程序往往需要运行很长时间,效率较低。

针对枚举法效率较低的缺点,在设计枚举算法时,我们必须注意以下二点:

①减少枚举变量:充分挖掘各解元素之间的联系,将一些非枚举不可的解元素列为枚举变量,然后在此基础上直接计算出其它解元素的可能值。

②减少枚举变量的值域:枚举前要尽可能多地将不符合条件的情况预先排除。

练习题1:设有下列的除法算式:

请根据上述算式中的信息求出被除数和除数。

提示分析:

其它信息:

设除数为x,被除数为y,则10<=x<=99,1000<=y<=9999,且8*x<=99,9*x>=100。

练习题2:数字分组

将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数。 例如:三个三位数192,384,576满足以上条件。

分析:

确定最小的三位数i为枚举变量,枚举范围是123<=i<=329,则另外二个三位数为2*i和3*i。接着分别求出组成这三个三位数的9个数字进行验证,如果这9个数字刚好是1到9的9个数字,则i,2*i,3*i即为解。

4

附知识点:

1、 关联文件操作

assign(input,’文件名.in’);

assign(output,’文件名.out’);

reset(input);

rewrite(output);

close(input);

close(output);

注意:主程序中exit前、全程序中halt前务必加close!!!

2、数据类型

整形:integer:-32768?32767

longint:-2147483648?2147483647

qword:0?18446744073709551615

int64:-9223372036854775808?9223372036854775807(较少用,可作为循环变量)

实型:real

布尔型:boolean(true、false)

字符型:char

字符串:string(255位)、ansistring

3、赋初值

置为0: fillchar(a,sizeof(a),0); (arrtype为任意类型)

置为maxint: fillword(a,sizeof(a)div 2,maxint); (arrtype为integer) 置为maxlongint: filldword(a,sizeof(a) (arrtype为longint)

注意:后两语句不要漏写“div 2”、“div 4”!

5

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com