《noi导刊_基础算法策略》由会员分享，可在线阅读，更多相关《noi导刊_基础算法策略（108页珍藏版）》请在金锄头文库上搜索。
1、基础算法策略,长沙市第一中学 曹利国,第一部分,枚举策略,枚举策略的基本思想,枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。,枚举策略的基本思想,枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。 枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。,虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚
2、举法求解的问题必须满足两个条件： 可预先确定每个状态的元素个数n； 状态元素a1，a2，an的可能值为一个连续的值域。 设 ai1状态元素ai的最小值；aik状态元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aiaik，an1anank for a1a11 to a1k do fo a2a21 to a2k do for aiai1 to aik do for anan1 to ank do if 状态(a1，ai，an)满足检验条件 then 输出问题的解；,枚举策略的基本思想,枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问
3、题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。,枚举方法的优化,枚举算法的时间复杂度：状态总数*单个状态的耗时 主要优化方法： 减少状态总数 降低单个状态的考察代价 优化过程从以下几个方面考虑： 枚举对象的选取 枚举方法的确定 采用局部枚举或引进其他算法,枚举算法的应用,例题1：二进制数的分类 若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如： （13）10=（1101）2， 13为B类数； （10）10=（1010）2 10为B类数； （24）10=（11000）2 24为A类数； 程序要求：求出11000之中（包括1与1000），
4、全部A、B两类数的个数。,【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。 具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为11000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。,枚举算法的应用,例题2：01统计,将问题的数据规模扩充到求1到m（m=1030）中A类数的个数。,分析,本题是统计问题，但使用1m的循环来逐个判断显然耗时过多，对于m较大时无法在规定的时间内出解。所以我们希望通过分类统计的方法，进一步抽象问题，得到可行的算法: 根据二进制数的前缀来分类是合理的
5、，既没有重复也没有遗漏。当m的二进制数长度为n时，最多有2n种类型，即2（log2m +1） 种，比穷举m种类型有了很大进步。,设m=(112)10=(1110000)2，求1m的A类数个数。可以将112个数分为以下几类： 数字形式为(111xxxx)2 这一类数只有1个，即(1110000)2，是A类数 数字形式为(110xxxx)2 设4个填数位置填0的个数为S0，填1的个数为S1，则S0 + S1 + 3 = 7,若为A类数，则S0 + 1 S1 + 2,可以取S0 = 4 S1 = 0；S0 = 3 S1 = 1.这一类数中的A类数个数：(4 4) + (3 4),数字形式为(10xx
6、xxx)2 设5个填数位置填0的个数为S0，填1的个数为S1，则S0 + S1 + 2 = 7 若为A类数，则S0 + 1 S1 + 1,可以取S0 = 5 S1 = 0；S0 = 4 S1 = 1；S0 = 3 S1 = 2.这一类数中的A类数个数： (55) + (45) + (35) 数字形式为(0xxxxxx)2 这一类数字的分析与前几类略有不同，因为前几类二进制数的位数都是7，而这一类数还需对位数进行讨论： （1）1位数，即(1)2，不是A类数 （2）2位数，即(1x)2，(10)2和(11)2都不是A类数 （3）3位数，即(1xx)2，A类数个数为(22) =1 （4）4位数，即(
7、1xxx)2，A类数个数为(33) =1 （5）5位数，即(1xxxx)2，A类数个数为 (44)+ (34)=5 （6）6位数，即(1xxxxx)2，A类数个数为 (55) + (45) =6 最后的答案是1 + 5 + 16 + (1 + 1 + 5 + 6) = 35,例题3：圆桌骑士（IOI试题） 在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。,枚举对象的确定,【分析】此题可从3个方面考虑： 分治、枚举、数学方法。 由于无法将这个问题划分为各
8、自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点： 1、最后的汇聚点。 2、国王与背他的骑士的汇聚点。 3、国王与背他的骑士。,枚举算法的应用,国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。 这样我们估算一下时间为O（8*8*8*8*63）=O（36*104），完全可以承受。 另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。,枚
9、举算法的应用,算法流程： disx1，y1，x2，y2-（x1，y1）（x2，y2）之间的距离。 For I：=1 to 8 do枚举汇合点 For j：=1 to 8 do begin All ：=所有骑士到这一点的和； Best:=min(best,all+国王到汇聚点的步数) For x：=1 to 8 do 枚举武士国王的相会点 For y：=1 to 8 do begin For kk：=1 to k do 枚举与国王结合的武士 If disknightkk.x,knightkk.y,x,ymin then begin Min:= disknightkk.x,knightkk.y,x
10、,y; Mink:=k; End; End； Now:= all-mink武士走到汇合点的距离+ mink武士走到汇聚点的距离+ 国王走到汇聚点的距离+从汇聚点到汇合点的距离； Best：=min（best，now） End；,局部枚举,例题4：求第一、第二、第三最短路问题,局部枚举,例题5：新年好 重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。,佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。
11、过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？,分析,这一题中的边数远小于n2，所以复杂度也只有nlogn+m 算法框架是： （1）用5次最短路，计算出6个点两两之间的距离 （2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。,第二部分,递推策略,递推的概念与基本思想,给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。,解决递推问题的一般步骤,建立递推关系式 确定边界条件 递推求解,递推的形式,顺推法和倒推法,递
12、推的应用分类,一般递推问题 组合计数类问题 一类博弈问题的求解 动态规划问题的递推关系,递推的应用（一般递推问题）,例题1 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,递推的应用（一般递推问题）,例题1 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个
13、圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,分析,设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柱上，
14、然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：h1=1,递推的应用（一般递推问题）,例2：实数数列 一个实数数列共有n项，已知 ai=(ai-1-ai+1)/2+d，(1in) (n60) 键盘输入n，d，a1，an，m，输出am。 输入数据均不需判错。,分析,根据公式ai=(ai-1-ai+1)/2+d 变形得，ai+1=ai-1-2ai+2d，因此该数列的通项公式为：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，这样就可以根据公式递推求出am ai=ai-2-2ai-1
15、+2d (1) =ai-2-2（ai-3-2ai-2+2d）+2d =-2ai-3+5（ai-4-2ai-3+2d）-2d =5ai-4-12ai-3+8d 一直迭代下去，直到最后，可以建立ai和a1与a2的关系式。,分析,设ai=Pia2+Qid+Ria1，我们来寻求Pi,Qi,Ri的变化规律。 ai=ai-2-2ai-1+2d ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 Pi=Pi-2-2Pi-1 Qi=Qi-2-2Qi-1+2 Ri=Ri-2
16、-2Ri-1 显然，P1=0 Q1=0 R1=1 （i=1） P2=1 Q2=0 R2=0 （i=2） 将初值P1Q1R1和P2Q2R2代入可以求出PnQnRn an=Pna2+Qnd+Rna1 a2=(an-Qnd+Rna1)/Pn 然后根据公式递推求出am，问题解决。,改进算法,但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。 为了减少误差，我们可设计如下算法： ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3
