枚举——NOIP.ppt

NOIP基础算法综合布冠澡衍胎抛葵丘壬睫胰看亨孵纳嗅垒蓉演计邦品鼎哇图疗迪溯樱径气祷枚举——NOIP枚举——NOIP第一部分枚举策略跪跺君坐殆丧爷贝罩洞啄砌蛀隧花穴嘶准樱虹惶徊逸湘桩肌西拣脊掀槐蹋枚举——NOIP枚举——NOIP一、枚举法的基本思想枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。枚举结构:循环+判断语句。凑咀跺荐记匝疵步氟协享奸之棕桂芦喂布怀坪哑寺祖往竿沽局菇关龋外侍枚举——NOIP枚举——NOIP二、枚举法的条件:虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件:⑴可预先确定每个状态的元素个数n;⑵状态元素a1,a2,…,an的可能值为一个连续的值域。猪务昏褒菊寂代尾捆篱全纬伴贬窃怒投坎濒伤赂朱厚芳讶揉霍疡舱岩汤款枚举——NOIP枚举——NOIP三、枚举法的框架结构设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k,ai1≤ai≤aik,……,an1≤an≤ankfora1←a11toa1kdofora2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1,…,ai,…,an)满足检验条件then输出问题的解;鞍属谱堆利寄碟寨晴冶则茵吭堤杯同耶溪富透韩壕铺酞舍喳碌援柬芒菱禄枚举——NOIP枚举——NOIP枚举法的优点⑴由于枚举算法一般是现实生活中问题的“直译”,因此比较直观,易于理解;⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。枚举法的缺点枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。四、枚举法的优缺点钩宁额站摆皂扔壶绚崖搁奢馆掀箱姓升趁珍侦挖振缉砰胖非耀菜企窝痹慕枚举——NOIP枚举——NOIP“直译”枚举:直接根据题意设定枚举对象、范围和约束条件。注意认真审题,不要疏漏任何条件新汾脉转常蓉殃蒋储业牌艘攒效秩纬齿铲憎架迁拣梦辱刨愧私纹兽填橱滇枚举——NOIP枚举——NOIP例题1:砝码称重(noip1996)【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000),求用这些砝码能称出不同的重量个数。【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。【文件输出】输出能称出不同重量的个数。【样例输入】110000【样例输出】3喝某推共潭伤仇鄙哎琶扮碾肄桓赶胚折千浊碑镜妓士柬群肖筷搜凿姬待执枚举——NOIP枚举——NOIP【分析】根据输入的砝码信息,每种砝码可用的最大个数是确定的,而且每种砝码的个数是连续的,能取0到最大个数,所以符合枚举法的两个条件,可以使用枚举法。枚举时,重量可以由1g,2g,……,20g砝码中的任何一个或者多个构成,枚举对象可以确定为6种重量的砝码,范围为每种砝码的个数。判定时,只需判断这次得到的重量是新得到的,还是前一次已经得到的,即判重。由于重量<=1000g,所以,可以开一个a[1001]的数组来判重。它耐蝴磷芭祖力翟咎生诵话炸逗袋蹦韩吾酗七逊剥硝绸情梯荆疟肆挪媳楼枚举——NOIP枚举——NOIP核心参考代码:readln(a,b,c,d,e,f)forc[1]:=0toado//1g砝码的个数forc[2]:=0tobdo//2g砝码的个数forc[3]:=0tocdo//3g砝码的个数forc[4]:=0toddo//5g砝码的个数forc[5]:=0toedo//10g砝码的个数forc[6]:=0tofdo//20g砝码的个数beginsum:=0;fori:=1to6dosum:=sum+c[i]*w[i];a[sum]:=1;//标记end;fori:=1to1000doifa[i]=1theninc(num);//统计不同重量的个数Writeln(num);聚啪皇脱渣词眉骏准死号岸秦资济肄锡莎鹃飘背团冤饲滞废铆淆墙豌禄赣枚举——NOIP枚举——NOIP