NOIP普级组枚举专题.ppt

NOIP基础算法综合--枚举法
江苏省南通市通州区金郊初中信息技术教研组
关联文件操作
assign(input,’’);
assign(output,’’);
reset(input);
rewrite(output);
close(input);
close(output);
注意:主程序中exit前、全程序中halt前务必加close!!!
1/3/2018
衡阳市第一中学计算机代表队***@DX8080
2
数据类型
整形:integer:-32768…32767
longint:-2147483648…2147483647
qword:0…18446744073709551615
int64:-9223372036854775808…9223372036854775807(较少用,不可作为循环变量)
实型:real
布尔型:boolean(true、false)
字符型:char
字符串:string(255位)、ansistring
1/3/2018
衡阳市第一中学计算机代表队***@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]的数组来判重。