1、NOIP基础算法综合n枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。n枚举结构：循环+判断语句。n虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：n可预先确定每个状态的元素个数n；n状态元素a1，a2，an的可能值为一个连续的值域。n设ai1状态元素ai的最小值；aik状态元素ai的最大值(1in)，即a11a1a1k，a21a2a2k，ai1aiaik，an1anankfora1a11toa1kdofora2a21toa2kdo
2、foraiai1toaikdoforanan1toankdoif状态(a1，ai，an)满足检验条件then输出问题的解；枚举法的优点枚举法的优点n由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；n由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点枚举法的缺点n枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。四、枚举法的优缺点四、枚举法的优缺点n“直译”枚举：直接根据题意设定枚举对象、范围和约束条件。n注意认真审题，不要疏漏任何条件例题例题1：砝码称重：砝码称重(noi
3、p1996)【问题描述问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），求用这些砝码能称出不同的重量个数。【文件输入文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。【文件输出文件输出】输出能称出不同重量的个数。【样例输入样例输入】110000【样例输出样例输出】3【分析分析】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g,20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的
4、个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量=1000g，所以，可以开一个a1001的数组来判重。readln(a,b,c,d,e,f)forc1:=0toado/1g砝码的个数砝码的个数forc2:=0tobdo/2g砝码的个数砝码的个数forc3:=0tocdo/3g砝码的个数砝码的个数forc4:=0toddo/5g砝码的个数砝码的个数forc5:=0toedo/10g砝码的个数砝码的个数forc6:=0tofdo/20g砝码的个数砝码的个数beginsum:=0;for
5、i:=1to6dosum:=sum+ci*wi;asum:=1;/标记标记end;fori:=1to1000doifai=1theninc(num);/统计不同重量的个数统计不同重量的个数Writeln(num);【问题描述】给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C0）3.n根火柴棍必须全部用上【输入】输入文件matches
8、：O(nm)【优化算法优化算法】先递推计算出先递推计算出si=si-1+ai，再回答询问情况，再回答询问情况;readln(n);fori:=1tondo统计求和统计求和beginread(ai);si:=si-1+ai;end;fori:=1tomdobeginread(x,y);writeln(sy-sx-1);end;【例题例题4】对于给定的对于给定的N*M的矩形，在其中找一个的矩形，在其中找一个R*C的权值最大的区域的权值最大的区域,1=N,M=1,000。【算法一算法一】：以每一个格子为左上角枚举：以每一个格子为左上角枚举R*C的区的区域，并求
12、henbest:=sum；/调整最优解调整最优解end;n这个算法相当粗糙，枚举状态的费用为这个算法相当粗糙，枚举状态的费用为O(n6)(x1,y1)(x2,y2)22、从减少重复计算入手、从减少重复计算入手n有刚才一维情况可以推广到二维，在统计左上角为有刚才一维情况可以推广到二维，在统计左上角为(x1,y1)右下角右下角为为(x2,y2)内矩形的元素之和时，我们同样可以先初始化，计算出左内矩形的元素之和时，我们同样可以先初始化，计算出左上角为上角为(1,1)，右下角为，右下角为(x,y)内矩形的元素之和内矩形的元素之和sxy。fori:=1tondo/枚举矩形右下角，求和
14、到，最大子矩阵问题是最大连续子序列和问题的提升，即将一条线换成一个面，将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。n但是还有一个问题，那就是应该如何高效地存储矩阵？n我们可以想到：在一个一维的数列中，设数组bi表示从第1个元素到第i个元素的和，则如果想要求第i个元素到第j个元素的和，只需要计算bj-bi-1的值就行了。由此推广到二维矩阵，设bi,j表示矩阵第j列前i个元素的和，ai,j表示元素数据，则压缩存储：fori:=1tondoforj:=1tondobeginread(ai,j);bi,j:=bi-1,j+ai,j
16、begint1:=bj,1-bi-1,1;/初始化第初始化第1列的值列的值fork:=2tondo/决策决策:第几列第几列beginiftk-10thentk:=tk-1+bj,k-bi-1,kelsetk:=bj,k-bi-1,k;iftksumthensum:=tk;end;end;end;writeln(sum);例题例题7：求第一、第二、第三最短路问题：求第一、第二、第三最短路问题n重庆城里有重庆城里有n个车站，个车站，m条双向公路连接其中的某些车站。条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出每两个
19、例题1：faibonacci数列数列【问题描述问题描述】已知faibonacci数列的前几个数分别为0，1，1，2，3，5，编程求出此数列的第n项。（n=60）例题例题2：输出杨辉三角的前：输出杨辉三角的前N行行【问题描述问题描述】输出杨辉三角的前N行(N10)。【文件输入文件输入】输入只有一行，包括1个整数N(N2)个盘子时，我们可以利用下列步骤：n第一步：先借助3柱把1柱上面的n-1个盘子移动到2柱上，所需的移动次数为f(n-1)。n第二步：然后再把1柱最下面的一个盘子移动到3柱上，只需要1次盘子。n第三步：再借助1柱把2柱上的n-1个盘子移动到3上，所需的移动次数为f(
20、n-1)。n由以上3步得出总共移动盘子的次数为：f(n-1)+1+f(n-1)。n所以：f(n)=2f(n-1)+1hn=2hn-1+1=2n-1边界条件：h1=1【扩展扩展2】：四塔问题：四塔问题【问题分析问题分析】令令fi表示四个柱子时，把表示四个柱子时，把i个盘子从原柱移动到目标柱所需的个盘子从原柱移动到目标柱所需的最少移动次数。最少移动次数。jn第一步：先把1柱上的前j个盘子移动到另外其中一个非目标柱（2或3柱均可，假设移到2柱）上，此时3和4柱可以作为中间柱。移动次数为：fj。n第二步：再把原1柱上剩下的i-j个盘子在3根柱子（1、3、4）之间移动，最后移动到目标柱4
21、上，因为此时2柱不能作为中间柱子使用，根据三柱问题可知，移动次数为：2(i-j)-1。n第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：fj。in通过以上步骤我们可以初步得出：通过以上步骤我们可以初步得出：fi=2*fj+2(i-j)-1nj可取的范围是可取的范围是1=ji，所以对于不同的，所以对于不同的j，得到的，得到的fi可能可能是不同的，本题要求最少的移动次数。是不同的，本题要求最少的移动次数。fi=min2*fj+2(i-j)-1，其中1=ji【扩展扩展3】：m塔问题塔问题【问题分析问题分析】设F(m,n)为m根柱子,n个盘子时移动的最少次数：n1、先把1柱
22、上的前j个盘子移动到另外其中一个除m柱以外的非目标柱上，移动次数为：fm,j；n2、再把原1柱上剩下的n-j个盘子在m-1根柱子之间移动，最后移动到目标柱m上，移动次数为：fm-1,n-j；n3、最后把非目标柱上的j个盘子移动到目标柱没柱上，移动次数为：fm,j。F(m,n)=min2*F(m,j)+F(m-1,n-j)(1=jn)j例题例题4:数的计数数的计数【问题描述】我们要求找出具有下列性质数的个数(包含输入的自然数n)，先输入一个自然数n(n1000)，然后对此自然数按照如下方法进行处理：(1)、不作任何处理；(2)、在它的左边加上一个自然数，但该自然数不能超过原
24、推：还是用递推。n只要做仔细分析，其实我们还可以得到以下的递推公式：(1)当i为奇数时,h(i)=h(i-1);(2)当i为偶数时,h(i)=h(i-1)+h(i/2);【思考思考】1.若若n=10000怎么计算；怎么计算；2.若若n=3000000怎么计算；怎么计算；n例题例题5：猴子吃桃问题：猴子吃桃问题1538n【问题描述问题描述】猴子摘了一堆桃，第一天吃了一半，猴子摘了一堆桃，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天又吃了剩下的还嫌不过瘾，又吃了一个；第二天又吃了剩下的一半零一个；以后每天如此。到第一半零一个；以后每天如此。到第n天，猴子一天，猴子一看只剩下一个了。问
25、最初有多少个桃子？看只剩下一个了。问最初有多少个桃子？【扩展练习扩展练习】猴子分桃猴子分桃【问题描述问题描述】有一堆桃子和N只猴子，第一只猴子将桃子平均分成了M堆后，还剩了1个，它吃了剩下的一个，并拿走一堆。后面的猴子也和第1只进行了同样的做法，请问N只猴子进行了同样做法后这一堆桃子至少还剩了多少个桃子(假设剩下的每堆中至少有一个桃子)？而最初时的那堆桃子至少有多少个？【文件输入文件输入】输入包含二个数据，数据间用空格隔开。第一个数据为猴子的只数N(1N10)，第二个数据为桃子分成的堆数M(2M7)。【文件输出文件输出】输出包含两行数据，第一行数据为剩下的桃子数，第二行数据为原来的桃子
26、数。【样例输入样例输入】32【样例输出样例输出】115【例题例题6】传球游戏（传球游戏（NOIP2008普及）普及）【问题描述问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的：n（3=n=30）个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m（3=m2-3
27、-1和1-3-2-1，共两种。分析n设fi,k表示经过k次传到编号为i的人手中的方案数，传到i号同学的球只能来自于i的左边一个同学和右边一个同学，这两个同学的编号分别是i-1和i+1，所以可以得到以下的递推公式：fi,k=fi-1,k-1+fi+1,k-1f1,k=fn,k-1+f2,k-1,当i=1时fn,k=fn-1,k-1+f1,k-1,当i=n时边界条件：f1,0=1；answer=f1,m参考代码readln(n,m);f1,0:=1;fork:=1tomdobeginf1,k:=f2,k-1+fn,k-1;fori:=2ton-1do
28、fi,k:=fi-1,k-1+fi+1,k-1;fn,k:=fn-1,k-1+f1,k-1;end;writeln(f1,m);n例题例题7：凸：凸n边形的三角形剖分边形的三角形剖分n在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用f(n)表之，f(n)即为Catalan数。例如五边形有如下五种拆分方案，故f(5)=5。求对于一个任意的凸n边形相应的f(n)。分析:设f(n)表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，
29、只要在P2，P3，Pn-1点中找一个点Pk(1kn)，与P1、Pn共同构成一个三角形的三个顶点，就将n边形分成了三个不相交的部分(如图)，我们分别称之为区域、区域、区域，其中区域必定是一个三角形，区域是一个凸k边形，区域是一个凸n-k+1边形，区域的拆分方案总数是f(k)，区域的拆分方案数为f(n-k+1)，故包含P1PkPn的n边形的拆分方案数为f(k)*f(n-k+1)种，而Pk可以是P2，P3，Pn-1种任一点，根据加法原理，凸n边形的三角拆分方案总数为:12)1(*)()(niinfifnf边界条件：f(2)=1【扩展扩展11】：二叉树数目：二叉树数目【问题描述问题描述】：求：
30、求nn个结点能构成不同二叉数的数目。个结点能构成不同二叉数的数目。【问题分析】：设F(n)为n个结点组成二叉树的数目。容易知道：f(1)=1;f(2)=2,f(3)=5选定1个结点为根，左子树结点的个数为i，二叉树数目f(i)种；右子树结点数目为n-i-1，二叉树数目f(n-i-1)种，i的可取范围0，n-1。所以有：为了计算的方便：约定f(0)=110)1(*)()(niinfifnf【扩展扩展2】：出栈序列：出栈序列【问题描述问题描述】：N个不同元素按一定的顺序入栈，求不同的个不同元素按一定的顺序入栈，求不同的出栈序列数目。出栈序列数目。【问题分析】设f(n)为n个元素的不同出
31、栈序列数目。容易得出：f(1)=1；f(2)=2。第n个元素可以第i(1=i=n)个出栈，前面已出栈有i-1个元素，出栈方法：f(i-1)；后面出栈n-i个元素，出栈方法为：f(n-i)。所以有：初始条件：F(0)=1ni1i)-f(n*1)-f(iniinfifnf1)(*)1()(例题例题10：错排问题（经典问题）：错排问题（经典问题）nn个数，分别为1n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个排列是一个错排。例如，n=3，则错排有231、312。编写程序，求n的错排个数分析我们设k个元素的错位全排列的个数记做：f(k)。四个元素的
32、错位排列f(4)我们用穷举法可以找到如下9个：(4,3,2,1);(3,4,1,2);(2,1,4,3)(4,3,1,2);(2,4,1,3);(2,3,4,1)(4,1,2,3);(3,4,2,1);(3,1,4,2)它们有什么规律呢？n通过反复的试验，我们发现事实上有两种方式产生错位排列：A、将k与(1，2，k-1)的某一个数互换，其他k-2个数进行错排，这样可以得到(k-1)f(k-2)个错位排列。B、另一部分是将前k-1个元素的每一个错位排列(有f(k-1)个)中的每一个数与k互换，这样可以得到剩下的(k-1)f(k-1)个错位排列。n根据加法原理，我们得到求错位排列的递推
33、公式f(k):f(k)=(k-1)*(f(k1)+f(k2)例题例题11：编码问题：编码问题n【问题描述问题描述】编码工作常被运用于密文或压缩传编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。字母表中共有把一些有规律的单词编成数字。字母表中共有26个小写字母个小写字母a,b,c.,z。这些特殊的单词长度不。这些特殊的单词长度不超过超过6且字母按照升序排列。把所有这样的单词且字母按照升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就放在一起，按字典顺序排列，一个单词的编码就对应着
34、它在字典中的位置，例如：对应着它在字典中的位置，例如：a-1;b-2;z-26;ab-27;ac-28;你的任务就是对于所给的单词，你的任务就是对于所给的单词，求出它的编码。求出它的编码。例题例题12：2k进制数（进制数（NOIP2006）见见word文档文档有如下所示的一个编号为到的方格：现由计算机和人进行人机对奕，从到，每次可以走个方格，其中为集=a1,a2,a3,.am中的元素(m=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。12345N-1N分析n题设条件：若谁先走到第N格谁将获胜，例如，假设S=1,2，从第N格往前
35、倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。例如，设N10，S1,2，则可确定其每个棋格的状态如下所示：而N10，S2,3时，其每格的状态将会如下所示：有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到
36、达目标格）的策略下棋，这样就能保证计算机尽可能不败。n例题例题14：最小伤害：最小伤害n把儿站在一个NxN的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。nFi,j：设走到(i,j)这格的最小伤害值,aij表示(i,j)这格的伤害值。nFi,j=min(fi-1,j,fi,j-1)+ai,jn边界条件：f1,1=a1,1fi,1=fi-1,1+ai,1(2=i=n)f1,i=f1,i-1+a1,i(2=imaxthenmax:=j;end;end;n起始状态就是调用起始状态就是调用
37、findmax(1,max),而像上述过程而像上述过程中的变参中的变参max完全可以省略。将上述方法修改可得下完全可以省略。将上述方法修改可得下面的算法：面的算法：Procedurefindmax(i:integer);beginifi=nthenexitelsebeginfindmax(i+1);ifaimaxthenmax:=ai;end;end;n起始状态就是调用起始状态就是调用findmax(1)，max为全局为全局变量，同时还减少了一个局部变量的使用。尽管变量，同时还减少了一个局部变量的使用。尽管这只是一个很简单的例子，在本例中不做精简，这只是一个很简单的
38、例子，在本例中不做精简，程序也还是能通过，但它精简的原则对其它使用程序也还是能通过，但它精简的原则对其它使用递归的程序而言却是同样适用的。特别是在递归递归的程序而言却是同样适用的。特别是在递归过程出现过程出现堆栈溢出情况时堆栈溢出情况时就应该考虑这一问题。就应该考虑这一问题。n优点：采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。n缺点：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循
39、环或者内存溢出的窘境。五、递归的应用五、递归的应用n处理递归定义或解决方法为递归方式的问题n解决搜索问题和组合计数n实现分治思想n用于输出动态规划的中间过程n树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。n因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例子很多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题。例题例题3：全排列：全排列【问题描述问题描述】编程列举出编程列举出1、2、n的全排列，要的全排列，要求产生的任一个数字序列中不允许出现重复的数字。求产生的任一个数字序列中不允许出现重复的数字。【文件输入文件输入】输入输入n
40、(1=n=9)【文件输出文件输出】有有1到到n组成的所有不重复数字的序列，组成的所有不重复数字的序列，每行一个序列每行一个序列n我们假设n=3时，如下图：位置1可以放置数字1、2、3；位置2可以放置数字1、2、3；位置3可以放置数字1、2、3，但是当位置1放了数字1后位置2和位置3都不能在放1，因此画树的约束条件是：各位置的数字不能相同。n我们画“解答树”时，根结点一般是一个空结点，根结点下面的第1、2、3三层分别对应位置1、位置2、位置3，用“”标示的分支表示该结点不满足约束条件，不能被扩展出来：proceduref(k:integer)/搜索第搜索第k层结点（向第层结点（向第k个
41、位置放数）个位置放数）beginvari:integer;ifk=n+1thenbeginfori:=1tondowrite(ai);writeln;end/如果搜索到一条路径，则输出一种解如果搜索到一条路径，则输出一种解elsefori:=1tondo/每一个结点可以分解出每一个结点可以分解出n个子结点；个子结点；ifbi=0then/如果能生成第如果能生成第k层的第层的第i个结点；个结点；beginak:=i;/第第k个位置为数字个位置为数字i；bi:=1;/标记数字标记数字i已用已用f(k+1);/扩展第扩展第k层的第层的第i
44、分阶段，都符合策略的最优化原理和无后效性。考虑到k=m，以抄写员编号来划分阶段会方便些。n设fi,j为前i个抄写员复制前j本书的最小“页数最大数”。Si=a1+a2+ai，则状态转移方程为：nfi,j=minmax(fi-1,k,Sj-Sk)(i-1=k=j-1)ndi,j=k；记录第i个人的最佳位置n边界条件f1,i=Si。n输出方案，则递归输出；输出方案，则递归输出；procedurePrint(i,j:integer)beginifi=1thenbeginwriteln(1,,j);exit;end;Print(i-1,di,j);writeln(di,j+
45、1,,j);endn归纳法的基本思想：归纳法的基本思想：是通过列举少量的特殊情况，经过分析，最后找出一般的关系。n从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。n细心的观察；细心的观察；n丰富的联想；丰富的联想；n继续尝试；继续尝试；n总结归纳出结论。总结归纳出结论。n归纳是一种抽象，即从特殊现象中找出一般关系。n由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。n从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。n从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。：求前n个自然数的平方之和