NOIP基础算法综合.ppt
《NOIP基础算法综合.ppt》由会员分享,可在线阅读,更多相关《NOIP基础算法综合.ppt(91页珍藏版)》请在三一文库上搜索。
1、NOIP基础算法综合,巴蜀中学 黄新军,第一节 枚举算法,一、枚举法的基本思想,枚举法的基本思想:根据实际问题设计多重循环,一一枚举所有可能的状态,并用问题给定的约束条件检验哪些状态是需要的,哪些状态是不需要的。能使命题成立的状态,即为其解。虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法或宽度优先搜索有所不同。,二、枚举法的条件:,可预先确定每个状态的元素个数n。如百钱买百鸡问题,3文钱一只鸡的状态元素个数可预先确定; 可预先确定每个状态元素a1,a2,an的值域。,三、枚举法的框架结构,设a11为状态元素ai的最小值;aik为状态元素ai的最大值(1=i=n),即状态元素a1,a2,a
2、n的值域分别为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的砝码个数。 【文件输出】输出能称出不同重量的个数。 【样例输入】1 1 0 0 0 0 【样例输出】3,例题1:砝码称重,【思路点拨】根据输入的砝码信息,每种砝码可用的最大个数是确定的,而且每种砝码的个数是连续的,能取0到最大个数,所以符合枚举法的两个条件,可以使用枚举法。枚举时,重量可以由1g,2g,20g砝码中的任何一个或者多个构成,枚举对象可以确定为6
4、种重量的砝码,范围为每种砝码的个数。判定时,只需判断这次得到的重量是新得到的,还是前一次已经得到的,即判重。由于重量=1000g,所以,可以开一个a1001的数组来判重,例题1:砝码称重,伪代码如下: memset(a,0,sizeof(a); for(c1=0;c1=a;c1+) /1g砝码的个数 for(c2=0;c2=b;c2+) /2g砝码的个数 for(c3=0;c3=c;c3+) /3g砝码的个数 for(c4=0;c4=d;c4+) /5g砝码的个数 for(c5=0;c5=e;c5+) /10g砝码的个数 for(c6=0;c6=f;c6+) /20g砝码的个数 sum=0;
5、for(i=1;i=6;i+)sum=sum+ci*wi; asum=1; /标记 for(i=1;i=1000;i+)if(ai)num+; /统计不同重量的个数 coutnumendl;,例题2:火柴棒等式(NOIP2008),给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示: 注意: 1.加号与等号各自需要两根火柴棍 2.如果AB,则A+B=C与B+A=C视为不同的等式(A、B、C=0) 3.n(n=24)根火柴棍必须全部用上,例题2:火柴棒等式(NOIP2008),【问题
6、简述】给你n(n=24)根火柴棒,叫你拼出 “A + B = C“这样的等式,求方案数. 【思路点拨】本题主要考查对枚举法的掌握,可以枚举A和B的取值,考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范围有所要求,必须要仔细分析A和B的取值。,例题2:火柴棒等式(NOIP2008),本题最多24根火柴,等号和加号共用4根火柴,所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能:09这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6,很明显数字1用的火柴棒最少只要2根,不妨让B为1,那么A和C最多可以使用18根火柴,而C=A,满足条件的A的最大取值为1111
7、。所以枚举A和B的范围是从01111。,为了加快速度,可以将0到2222的所有整数需要的火柴棒数目提前算好保存在数组中。,五、枚举算法的优化,枚举算法的时间复杂度:状态总数*单个状态的耗时 主要优化方法: 减少状态总数 降低单个状态的考察代价 优化过程从以下几个方面考虑: 枚举对象的选取 枚举方法的确定 采用局部枚举或引进其他算法,【例题3】给你n个整数,然后要有m个询问。问第i个数字到第j个数字所有数字之和。,【朴素算法】 cinn; for(i=1;iai; for(i=1;ixy; sum=0; for(j=x;j=y;j+)sum+=aj; coutsumendl; ,【优化算法】先计
8、算si=si-1+ai cinn; for(i=1;iai;si=si-1+ai; for(i=1;ixy; coutsy-sx-1endl; ,【例题4】最大子矩阵问题,【问题描述】给定一个二维的数组(含正数或负数),请从中找出和最大的子矩阵。例如:,【例题4】最大子矩阵问题,1、“直译”枚举过程 for(x1=1;x1best)best=sum;/调整最优解 这个算法相当粗糙,枚举状态的费用为O(n6),2、从减少重复计算入手 有刚才一维情况可以推广到二维,在统计左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和时,我们同样可以先初始化,计算出左上角为(1,1)右下角为(x,y)
9、内矩形的元素之和sxy。 for(x1=1;x1mapij; sij=si-1j+sij-1-si-1j-1+mapij; 对于状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和,可以改为: sum=sx2y2-sx1-1y2-sx2y1-1+sx1-1y1-1; if(sumbest)best=sum;/调整最优解 由于利用了计算出的结果,整个算法的时间复杂度降为O(n4),【例题4】最大子矩阵问题,3、提取恰当的信息 容易观察到,最大子矩阵问题是最大连续子序列和问题的提升,即将一条线换成一个面,将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求
10、得最大值。 但是还有一个问题,那就是应该如何高效地存储矩阵? 我们可以想到:在一个一维的数列中,设数组bi表示从第1个元素到第i个元素的和,则如果想要求第i个元素到第j个元素的和,只需要计算bj-bi-1的值就行了。由此推广到二维矩阵,设bij表示矩阵第j列前i个元素的和,aij表示元素数据,则压缩存储: for(i=1;iaij;bij=bi-1j+aij; 因此,我们可以使用三重循环求出所有的矩形值,即枚举起始行i和终止行j,压缩子矩形成为一行,变成一维求最大字段和问题。 即tk=max(tk-1,0)+bjk-bi-1k; 时间复杂度为O(n3),【例题4】最大子矩阵问题,核心代码 su
11、m=-0x7fffffff; for(i=1;isum)sum=tk; coutsumendl;,六、局部枚举,例题5:求第一、第二、第三最短路问题,例题6:新年好,重庆城里有n个车站,m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连,从任何一个车站出发都可以经过一条或多条公路到达其他车站,但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。 佳佳的家在车站1,他有五个亲戚,分别住在车站a,b,c,d,e。过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福。怎样走,才需要最少的时间?,算法分析,这一题中的边数远小于
12、n2,所以复杂度也只有nlogn+m 算法框架是: (1)用5次最短路,计算出6个点两两之间的距离 (2)枚举5个结点的全排列,找到一个使得总路程长度最短的方案。,第二部分 递推策略,递推的概念与基本思想,给定一个数的序列H0,H1,Hn,若存在整数n0,使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来,这样的式子就叫做递推关系。,解决递推问题的一般步骤,建立递推关系式 确定边界条件 递推求解,递推的形式,顺推法和倒推法,递推的应用分类,一般递推问题 组合计数类问题 一类博弈问题的求解 动态规划问题的递推关系,例题1:faibonacci数列,【问题描述
13、】已知faibonacci数列的前几个数分别为0,1,1,2,3,5,编程求出此数列的第n项。( n=60),递推的应用(一般递推问题),递推的应用(一般递推问题),【例题2】输出杨辉三角的前N行 【问题描述】输出杨辉三角的前N行(N10)。 【文件输入】输入只有一行,包括1个整数N(N10)。 【文件输出】输出只有N行。 【样例输入】3 【样例输出】 1 1 1 1 2 1,递推的应用(一般递推问题),例题3 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上: (
14、1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?,分析,2,1,3,当n=1时:AC 当n=2时:AB,AC,BC 当n=3时:,分析,设hn为n 个盘子从a柱移到c柱所需移动的盘次。显然,当n=1时,只需把a 柱上的盘子直接移动到c柱就可以了,故h1=1。当n=2时,先将a柱上面的小盘子移动到b柱上去;然后将大盘子从a柱移到c 柱;最后,将b柱上的小盘子移到c柱上,共记3个盘次,故h2=3。以此类推,当a柱上有n(n=2)个盘子时,总是先借助c柱把上面的n-1个盘子移动到b柱上,然后把
15、a柱最下面的盘子移动到c柱上;再借助a柱把b柱上的n-1个盘子移动到c柱上;总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件:h1=1,思考: Hanoi双塔问题,递推的应用(一般递推问题),【例题4】数的计数 【问题描述】我们要求找出具有下列性质数的个数(包含输入的自然数n),先输入一个自然数n(n1000),然后对此自然数按照如下方法进行处理: l.不作任何处理; 2.在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3.加上数后,继续按此规则进行处理,直到不能再而 自然数为止;,方法1:用递推。用hn表示自然数n所能扩展的数据个数,则:h1=1,h2=2,h
16、3=2,h4=4,h5=4,h6=6,h7=6,h8=10,h9=10。分析上数据,可得递推公式:hi=1+h1+h2+hi/2。时间复杂度O(n2)。,方法2:是对方法1的改进。我们定义数组s. s(x)=h(1)+h(2)+h(x), h(x)=s(x)-s(x-1) 此算法的时间复杂度可降到O(n)。,方法3:还是用递推。 只要做仔细分析,其实我们还可以得到以下的递推公式: (1)当i为奇数时,h(i)=h(i-1); (2) 当i为偶数时,h(i)=h(i-1)+h(i/2);,【思考】1.若n=10000怎么计算; 2.若n=3000000怎么计算;,递推的应用(一般递推问题),例题
17、5:猴子吃桃问题1538 猴子吃桃问题。猴子摘了一堆桃,第一天吃了一半,还嫌不过瘾,又吃了一个;第二天又吃了剩下的一半零一个;以后每天如此。到第n天,猴子一看只剩下一个了。问最初有多少个桃子?,【扩展练习】猴子分桃,【问题描述】有一堆桃子和N只猴子,第一只猴子将桃子平均分成了M堆后,还剩了1个,它吃了剩下的一个,并拿走一堆。后面的猴子也和第1只进行了同样的做法,请问N只猴子进行了同样做法后这一堆桃子至少还剩了多少个桃子(假设剩下的每堆中至少有一个桃子)?而最初时的那堆桃子至少有多少个? 【文件输入】输入包含二个数据,数据间用空格隔开。第一个数据为猴子的只数N(1N10),第二个数据为桃子分成的
18、堆数M(2M7)。 【文件输出】输出包含两行数据,第一行数据为剩下的桃子数,第二行数据为原来的桃子数。 【样例输入】3 2 【样例输出】 1 15,递推的应用(一般递推问题),【例题6】传球游戏(NOIP2008普及)2309 【问题描述】上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。 游戏规则是这样的:n(32-3-1和1-3-2-1,共两种。,分析,设fik表示经过k次传到编号为i的人手中的方案数,传到i号同学的球只能来自于i的左边一个同学和右边一个同学,这两个同学的编号分别是i-1和i+1,所以可以得到以下的递推公式: fik=fi-1k-1+f
19、i+1k-1 f1k=fnk-1+f2k-1, 当i=1时 fnk=fn-1k-1+f1k-1, 当i=1时 边界条件:f10=1;结果在f1m中。,参考代码,cinnm; memset(f,0,sizeof(f); f10=1; for(k=1;k=m;k+) f1k=f2k-1+fnk-1; for(i=2;i=n-1;i+)fik=fi-1k-1+fi+1k-1; fnk=fn-1k-1+f1k-1; coutf1mendl;,递推的应用(组合计数),Catalan数 定义:Cn=n+2条边的多边形,能被分割成三角形的方案数,例如5边型的分割方案有:,如图,有一个正n+2边形。任取一边,
20、从这边的端点开始,依次给顶点编号为:0,1,2,3,.,n,n+1(所取的边端点编号为:0,n+1)。这样,除线段所在顶点外,还有n个顶点:1,2,3,n。我们以该线段为三角形的一条边,另一个顶点为i(1=i=n)。,我们设题意要求的三角形剖分方案数为H(n),即除线段顶点(编号0与n+1)外,还有n个顶点时的三角形剖分方案为H(n)。则以顶点0,i为指定线段(上面还有1,2,i-1,共i-1个顶点)的剖分数位H(i-1);以顶点n+1,i为指定线段的剖分数为H(n-i)。根据乘法原理,以0,i,n+1为一剖分三角形的剖分数应为:H(i-1)*H(n-i),i=1,2,n,所得的剖分各不相同,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 基础 算法 综合
链接地址:https://www.31doc.com/p-2202270.html