noip基础算法综合

《noip基础算法综合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP基础算法综合巴蜀中学黄新军第一节枚举算法一、枚举法的基本思想枚举法的基本思想：根据实际问题设计多重循环，一一枚举所有可能的状态，并用问题给定的约束条件检验哪些状态是需要的，哪些状态是不需要的。能使命题成立的状态，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。二、枚举法的条件:①可预先确定每个状态的元素个数n。如百钱买百鸡问题，3文钱一只鸡的状态元素个数可预先确定；②可预先确定每个状态元素a1,a2,…,an的值域。三、枚举法的框架结构设a11为状态元素ai的最小值；aik为状态元素ai的最大值(1<

2、=i<=n),即状态元素a1,a2,…an的值域分别为a11<=a1<=a1k,a21<=a2<=a2k,……ai1<=ai<=aik,…an1<=an<=ank。for(a1=a11;a1<=a1k;a1++)for(a2=a21;a2<=a2k;a2++).....for(ai=ai1;ai<=aik;ai++).....for(an=an1;an<=ank;an++)if(状态(a1,...,ai...,an)满足检验条件)输出问题的解;四、枚举法的优缺点枚举法的优点：由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举

3、所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。例题1：砝码称重【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），求用这些砝码能称出不同的重量个数。【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。【文件输出】输出能称出不同重量的个数。【样例输入】110000【样例输出】3例题1：砝码称重【思路点拨】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续

4、的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g,……,20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量<=1000g，所以，可以开一个a[1001]的数组来判重例题1：砝码称重伪代码如下：memset(a,0,sizeof(a));for(c[1]=0;c[1]<=a;c[1]++)//1g砝码的个数for(c[2]=0;c[2]<=b;c[2]++)//2g砝码的个数for(c

5、[3]=0;c[3]<=c;c[3]++)//3g砝码的个数for(c[4]=0;c[4]<=d;c[4]++)//5g砝码的个数for(c[5]=0;c[5]<=e;c[5]++)//10g砝码的个数for(c[6]=0;c[6]<=f;c[6]++)//20g砝码的个数{sum=0;for(i=1;i<=6;i++)sum=sum+c[i]*w[i];a[sum]=1;//标记}for(i=1;i<=1000;i++)if(a[i])num++;//统计不同重量的个数cout<

6、根火柴棍，你可以拼出多少个形如“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(n<=24)根火柴棍必须全部用上例题2：火柴棒等式（NOIP2008）【问题简述】给你n(n<=24)根火柴棒,叫你拼出"A+B=C"这样的等式,求方案数.【思路点拨】本题主要考查对枚举法的掌握，可以枚举A和B的取值，考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范

7、围有所要求，必须要仔细分析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根，不妨让B为1，那么A和C最多可以使用18根火柴，而C>=A，满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。为了加快速度，可以将0到2222的所有整数需要的火柴棒数目提前算好保存在数组中。五、枚举算法的优化枚举算法的时间复杂度

8、：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确