基础算法(枚举、贪心、分治策略).ppt

《基础算法(枚举、贪心、分治策略).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、基础算法策略长沙市第一中学曹利国第一部分枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略的基本思想枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。虽然枚举法本质上属于搜索策略，但是它

2、与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：      ⑴可预先确定每个状态的元素个数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输出

3、问题的解；枚举策略的基本思想枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法枚举算法的应用例题1：二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（

4、10）10=（1010）210为B类数；（24）10=（11000）224为A类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。枚举算法的应用例题2：01统计例题3：围巾裁剪（NOI试题）将一个边长为n(n<=100)的大的正三角形均匀的分成

5、n*n的小三角形，某些小三角形已经损坏。求出2个面积最大的（即包含小三角形个数最多的）2个子正三角形，要求这两个子正三角形中没有损坏的小三角形。枚举算法的应用【分析】三角形的分割必定将沿着其分割线分割。由于n〈=100，将每个分割线枚举一次，最多只有100*3条，所以可以考虑用枚举求解。枚举出分割线以后，我们当前最重要的任务就是如何求出上下2个三角形的最大子三角形。我们又可以使用枚举，以每一个点最为一次顶点，向下扩展，求出其可以扩展的最大面积。为了减少枚举次数，我们可以考虑将其值先计算并保存下来。枚举算法的应用定义变量：lup[I，j]表示以第I

6、行j列的正放着的小三角形为上顶点的最大可扩展的面积。ldown[I，j]表示以第I行j列的倒放着的小三角形为下顶点的最大可扩展的面积。Up[I，j]表示第I行j列的正放着的小三角形是否损坏。down[I，j]表示以第I行j列的倒放着的小三角形是否损坏。枚举算法的应用容易得出lup，ldown[I，j]的递推式：min{lup[I+1,j],lup[I+1,j+1]}+1[down[I+1,j]=true]lup[I,j]:=1[down[I+1,j]=false]0[up[I,j]=false]边界：lup[n，I]：=1min{ldown[I-

7、1,j],ldown[I-1,j-1]}+1[up[I-1,j]=true]ldown[I,j]:=1[up[I-1,j]=false]0[down[I,j]=false]求出了lup，ldown后，算法的设计就不难了。枚举算法的应用另外，还需要注意的一点是关于三角形60度的旋转。对于正放着的三角形：xx：=n-y+1yy：=x-（n-xx）对于倒放着的三角形：xx：=n-y+1yy：=x-1-（n-xx）枚举算法的应用例题4：圆桌骑士（IOI试题）在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同

8、一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。枚举算法的应用【分析】此题可从3个方面考虑