基础算法枚举贪心分治策略教学课件

基础算法策略长沙市第一中学曹利国Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyLHNFMS第一部分枚举策略Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL枚举策略的基本思想枚举法,又称穷举法,指在一个有穷的可能的解的集合中,一一枚举出集合中的每一个元素,用题目给定的检验条件来判断该元素是否符合条件,若满足条件,则该元素即为问题的一个解;否则,该元素就不是该问题的解。Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL枚举策略的基本思想枚举方法也是一种搜索算法,即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中,可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如,求解不定方程的问题就可以采用列举法。Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyLHNFMS虽然枚举法本质上属于搜索策略,但是它与回溯法有所不同。因为适用枚法求解的问题必须满足两个条件:1)可预先确定每个状态的元素个数n()状态元素a1,a2,…,an的可能值为一个连续的值域设a1-状态元素a的最小值;ak-状态元素a1的最大值(1ssn),即11Sa1sa1k,a21sa2sa2k,aisasaik,fora,←atoadofoa2←atoa.dtoa.doforan*anttoankdoif状态(a1,…,ap…,an)满足检验条件then输出问题的解Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL枚举策略的基本思想枚举法的特点是算法比较简单,在用枚举法设计算法时,重点注意优化,减少运算工作量。将与问题有关的知识条理化、完备化、系统化,从中找出规律,减少枚举量Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL枚举方法的优化枚举算法的时间复杂度:状态总数*单个状态的耗时主要优化方法:(1)减少状态总数(2)降低单个状态的考察代价优化过程从以下几个方面考虑:(1)枚举对象的选取(2)枚举方法的确定(3)采用局部枚举或引进其他算法Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL枚举算法的应用例题1:二进制数的分类若将一个正整数转化为二进制数后,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两类数的个数。Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyL枚举算法的应用【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法:逐枚举所有情况,同时进行统计,枚举结束时,统计也完成,得到结果具体对本题而言,采用枚举法的正确性与可行性是显然的,而本题的数据规模又仅为1~1000,所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。Valadononry.chAsposeslidesforNET4odientPEvaluationonly.CreatedwithAsposeSlidesforNET4.0dientProfilo71Copyright2019-2019AsposePtyLHNFMS例题2:01统计Valadononry.chAspos