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

NOIP普级组枚举专题

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

NOIP基础算法综合
--枚举法

江苏省南通市通州区金郊初中 信息技术教研组

关联文件操作
? ? ? ? assign(input,’文件名.in’); assign(output,’文件名.out’); reset(input); rewrite(output);

? close(input); ? close(output); ? 注意:主程序中exit前、全程序中halt前务 必加close!!!
衡阳市第一中学计算机代表队@DX8080

2

数据类型
? ? ? ? 整形:integer:-32768…32767 longint:-2147483648…2147483647 qword:0…18446744073709551615 int64:9223372036854775808…92233720368547 75807(较少用,不可作为循环变量) 实型:real 布尔型:boolean(true、false) 字符型:char 字符串:string(255位)、ansistring
衡阳市第一中学计算机代表队@DX8080

? ? ? ?

3

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

二、枚举法的条件:
? 虽然枚举法本质上属于搜索策略,但是它与后面 讲的回溯法有所不同。因为适用枚举法求解的问 题必须满足两个条件:
? ⑴可预先确定每个状态的元素个数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]的数组来判重。

核心参考代码:
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);

例题2:火柴棒等式(NOIP2008)
【问题描述】给你n根火柴棍,你可以拼出多少个形如“A+B=C” 的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零, 则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:

注意: 1. 加号与等号各自需要两根火柴棍 2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、 C≥0) 3. n根火柴棍必须全部用上 【输入】输入文件matches.in共一行,又一个整数n(n≤24)。 【输出】输出文件matches.out共一行,表示能拼成的不同等式 的数目。

例题2:火柴棒等式(NOIP2008)
【问题简述】给你n(n<=24)根火柴棒,叫你拼出 “A + B = C”这样的等式,求方案数。 【思路点拨】本题主要考查对枚举法的掌握,可以 枚举A和B的取值,考查等式是否刚好用了24根火柴 棒。1S的时限对枚举的范围有所要求,必须要仔细 分析A和B的取值。

例题2:火柴棒等式(NOIP2008)
?本题最多24根火柴,等号和加号共用4根火 柴,所以A,B,C这3个数字需用20根火柴。 我们考查A和B的最大的取值可能:0~9这10 个数字所用的火柴数为 6,2,5,5,4,5,6,3,7,6,很明显数字1用的 火柴棒最少只要2根
?为了加快速度,可以将0到2000的所有整数需 要的火柴棒数目提前算好保存在数组中。

解题思路:
? n<=24,数据范围很小, ? ①首先用两个循环枚举两个加数的每种情况。 ? ②然后把两加数相加,算出和,后用三个数所使 用的火柴棒数相加(可以用一个函数计算),判断 所得的和是否等于(n-4)【符号】。 ? ③如果相等,就把记录答案的计数器变量自加1, 重复步骤①直到循环结束。 ? 下面看代码。

const inp='medic.in'; begin oup='medic.out'; assign(input,inp); reset(input); num:array['0'..'9'] of assign(output,oup);rewrite(output); integer=(6,2,5,5,4,5,6,3,7,6);//0~9火柴棒数 readln(n); maxn=1000; init; var ans:=0; f:array[0..maxn*2] of longint; n:=n-4;//总火柴棒数减去'+'和'='所需的火 i,j,k,n,ans:longint; for i:= 0 to maxn do//枚举A s:string; begin procedure init;//0~2000每个数需要的火柴棒数 if f[i]>=n then continue;//剪枝 var f

or j:= 0 to maxn do//枚举B i,j,k:longint; begin s:string; if f[i]+f[j]>=n then continue;//剪枝 begin k:=i+j; for i:= 0 to maxn*2 do if f[i]+f[j]+f[k]=n then inc(ans);//符 begin end; str(i,s); end; f[i]:=0; write(ans); for j:= 1 to length(s) do close(input); inc(f[i],num[s[j]]); close(output); end; end. 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 n<9 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.

五、枚举算法的优化
枚举算法的时间复杂度:状态总数*单个状态的耗时。 ? ⑴提取有效信息; ? ⑵减少重复计算; ? ⑶将原问题化为更小的问题; ? ⑷根据问题的性质进行截枝; ? ⑸引进其他算法


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