day2基础算法-曹利国-noip培训

基础算法策略长沙市第一中学曹利国算法效率的评价算法的评估有时求解同一个问题常常有多种可用的算法，在一定的条件下当然要选择使用好的算法。用什么方法评估算法的好坏呢？通常使用算法复杂性这一概念来评估算法。算法评价算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：事后统计的方法事前分析估算的方法算法评价一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：①依据的算法选用何种策略；②问题的规模.例如求100以内还是1000以内的素数；③书写程序的语言.对于同一个算法,实现语言的级别越高,执行效率就越低；④编译程序所产生的机器代码的质量；⑤机器执行指令的速度。算法评价一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本操作重复执行的次数作为算法的时间度量。算法评价一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作T（n）=O（f（n））它表示问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。算法评价例如：在下列三个程序段中，①x:=x+1②fori:=1tondox:=x+1;③forj:=1tondofork:=1tondox:=x+1含基本操作“x增1”的语句x:=x+1的频度分别为1，n和n2，则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。算法评价算法还可能呈现的时间复杂度有：对数阶O（logn），指数阶O（2n）等。在n很大时,不同数量级时间复杂度显然有O（1）O（logn）O（n）O（nlogn）O（n2）O（n3）O（2n），可以看出，在算法设计时，我们应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。算法评价由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以计算基本操作执行次数(或语句频度)的情况下，只需求出它关于n的增长率或阶即可。例如，在下列程序段中：fori:=2tondoforj:=2toi-1dox:=x+1语句x:=x+1执行次数关于n的增长率为n2，它是语句频度表达式(n-1)(n-2)/2中增长最快的一项。算法评价类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记作S(n)=O(f(n))其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。算法评价评价一个数学模型有以下几个原则：1.时间复杂度一个好的算法一般效率比较高。在竞赛中，试题常常会做一些算法运行时间上的限制。这就要求我们所建立的数学模型对应算法的效率一定要符合要求。这也是最重要的一个原则。算法评价2.空间复杂度出于计算机自身的限制，程序在运行时一般只被提供有限的内存空间。这也就要求我们建立模型时顾及到这一点。但对于模型对应的算法来说，并不是要求空间越低越好，只要不超过内存限制就可以了。算法评价3.编程复杂度相对而言，“编程复杂度”的要求要略低一些。但是在竞赛中，如果建立的算法实现起来十分繁琐，自然不利于比赛。所以，在建立模型时（特别是在竞赛中）这点也要纳入考虑之中。算法评价一道题目可能对应几种不同思想的模型，就要根据评价模型的标准来衡量一下，确定一个模型作为分析方向。这时的评价标准除了上述的时间、空间、编程复杂度三个标准外，还要加上一个思维的复杂度。算法评价所谓思维的复杂度，是指思考所耗费的时间和精力。如果我们确定了一个模型作为分析的方向（没有考虑思维复杂度），从问题原型到该数学模型的建模过程却十分复杂，导致思维耗费时间长，精力多，那自然是不合算的。总的来说，对于多种数学模型的选择，我们遵循“边分析，边选择”的原则。影响算法效率的因素问题的算法模型的建立问题的数据结构选择第一部分枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略的基本思想枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举策略的基本思想枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法巧妙填数将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图192384576分析本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。算式设有下列的算式：208-------------□□)□□□□□□-------------□□□□□□-------------1要求：求出□中的数字，并打印出完整的算式。枚举方法的优化【分析】此题找不到很好的方法，于是考虑枚举法。本题中，待填数字的空格共有14个，每个格子中都可填0..9这10个数字。若对14个格子都进行0..9十个数字逐一枚举，枚举量是1014，不可能在指定的时间内得出结果。优化方法：减少枚举量，找出适当的元素进行枚举。枚举方法的优化由数学知识知道，在除法中只要知道被除数、除数、商和余数中的任意三部分就可以求得第四部分。本题已知商和余数，只要知道被除数或除数，整个算式也就确定下来了。而被除数和除数，分别是4位数和2位数。我们只需枚举除数。枚举量降为102=100，这个时间复杂度是完全可以承受的。方格填数方格填数问题。如图所示形状的八个方格中填入1-8这八个数字，使得相邻的和对角线上的数字之差不为1，编程求解所有的填法方案和总数。B1B2B3B4B5B6B7B8【分析】将1至8填入到B1至B8中，总共有8！＝40320种填法。该问题的枚举总量为8！个。由于B3和B6这两个方格与其相邻的格子共有6个，放入这两个格子中的数，必须和六个数不连续，这样的两个数只有1和8。B1，B3，B6，B8这四个格子中仅仅有两种可能放法，即：2，8，1，7和7，1，8，2。挖掘出这一隐含条件之后，B2，B4，B5，B7四个格子中的数就只能从3，4，5，6这四个数中进行选择，整个问题的枚举总量将变得只有2＊4！＝48种，从而大大地减少了枚举量，提高枚举效率。枚举方法的优化枚举算法的应用二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（10）10=（1010）210为B类数；（24）10=（11000）224为A类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。枚举算法的应用01统计将问题的数据规模扩充到求1到m（m=1030）中A类数的个数。分析本题是统计问题，但使用1~m的循环来逐个判断显然耗时过多，对于m较大时无法在规定的时间内出解。所以我们希望通过分类统计的方法，进一步抽象问题，得到可行的算法:根据二进制数的前缀来分类是合理的，既没有重复也没有遗漏。当m的二进制数长度为n时，最多有2n种类型，即2（log2m+1）种，比穷举m种类型有了很大进步。设m=(112)10=(1110000)2，求1~m的A类数个数。可以将112个数分为以下几类：数字形式为(111xxxx)2这一类数只有1个，即(1110000)2，是A类数数字形式为(110xxxx)2设4个填数位置填0的个数为S0，填1的个数为S1，则S0+S1+3=7,若为A类数，则S0+1S1+2,可以取S0=4S1=0；S0=3S1=1.这一类数中的A类数个数：(44)+(34)数字形式为(10xxxxx)2设5个填数位置填0的个数为S0，填1的个数为S1，则S0+S1+2=7若为A类数，则S0+1S1+1,可以取S0=5S1=0；S0=4S1=1；S0=3S1=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位数，即(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圆桌骑士（IOI试题）在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。枚举对象的确定【分析】此题可从3个方面考虑：分治、枚举、数学方法。由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：1、最后的汇聚点。2、国王与背他的骑士的汇聚点。3、国王与背他的骑士。枚举算法的应用国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。这样我们估算一下时间为O（8*8*8*8*63）=O（36*10^4），完全可以承受。另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。枚举算法的应用算法流程：dis[x1，y