基础算法策略枚举

《基础算法策略枚举》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基础算法策略枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略解题思路为：首先确定可能的解集合；抽象出解包含的参数，确定每个参数的数据范围；对解的每个参数的数据范围采用循环语句一一枚举；对每次枚举，根据题意给定的条件判定是否解，是否是最优解。设某个问题的解所涉及的参数（状态参数）有n个，分别表示为a1，a2，…，an，其中ai1—状态元素ai的最小值；aik—状态元素ai的最大值(

2、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、态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法枚举算法的应用若将一个正整数转化为二进制数后，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：二进制数的分类【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：

4、逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。例题2：01统计将问题的数据规模扩充到求1到m（m<=1030）中A类数的个数。讨论！分析本题是统计问题，但使用1~m的循环来逐个判断显然耗时过多，对于m较大时无法在规定的时间内出解。所以我们希望通过分类统计的方法，进一步抽象问题，得到可行的算法:我们发现虽然m很大，但是这些数变成二进制后，其位数却不大，因此可以考虑从这m个数的每一位来分类进行统计。

5、设m=(112)10=(1110000)2，求1~m的A类数个数。可以将112个数分为以下几类：例：数字形式为(111xxxx)2这一类数只有1个，即(1110000)2，是A类数数字形式为(110xxxx)2设4个填数位置填0的个数为S0，填1的个数为S1，则S0+S1=4,若为A类数，则S0+1>S1+2,可以取S0=4S1=0；S0=3S1=1.这一类数中的A类数个数：(44)+(34)数字形式为(10xxxxx)2设5个填数位置填0的个数为S0，填1的个数为S1，则S0+S1=5;若为A类数，则S0+1>S1+1,可以取S0=5S1=0；S0=4S1

6、=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+

7、5+16+(1+1+5+6)=35对于一般情况：设m的二进制数为a1a2…an(其中a1为最高位)，设a1a2…ak中0的个数为S0(k)，1的个数为S1(k)，设b1b2…bn为1~m的一个数，此时可分为：第一大类，当b1=1时，可根据前缀的不同来分类统计；第二大类，当b1=0时，可根据二进制数位数的不同来分类统计。11xxxx12…i………n最高位最低位左数第i位设左数第i位为1，后n-i位（画X的位）中有j个0，记前k位（从左数）中0的个数为S0(k)，1的个数为S1(k)，（可预先求出），则前缀为(1…0X…X)2的A类数共有0个A类数，其中S0(i

8、-1)+1+j>S1(i-1)+n-i-j第一大类：