枚举算法例题,python枚举法例题及解题思路

　　1.枚举算法设计步骤：

　　确定枚举对象(即问题解的表达式形式，一般用几个参数来描述)并逐一枚举可能性(根据枚举对象的参数构造一个循环，逐一枚举其表达式的每个值)并逐一验证可能的解（ 。根据问题解决方案的要求，验证枚举对象表达式的每个值。如果条件满足，就采用，否则就丢弃。这里注意：对象不能重复和省略；

　　各参数应相互独立，使算法简洁；每个参数的取值范围要明确，尽可能小。

　　2. 实际例子1

　　解释

　　确定对象：对象是解的表达式，用一个参数X表示；x的取值范围是(0~9)。逐一列举对象：以x确定的周期逐一列举可能的解，逐一验证可能的解。只有满足验证条件，才能确定x的值。

　　回答：

　　确定对象：这个可能的对象由两个参数I，J组成(I的取值范围是[1-9]，J的取值范围是[0-9])。逐一枚举循环：由于这里有两个参数，所以它必须使用两层循环，一层用I，一层用j，对这些枚举的个体逐一验证，只有满足条件的才能取值。

　　当这里的三个数字都看不见的时候：

　　回答：

　　对象，这三个参数实际上可以看作一个参数；x为100 ~ 999；这样参数减少，代码易读；逐一枚举，利用x的取值范围形成循环；但这里把三个参数看成一个参数，复杂度不降低，对满足条件的值逐一验证。3.实际例子2:5块钱一只公鸡。

　　母鸡：三元一只。

　　小鸡：1元3只。

　　问：M元买N只鸡有几种方案？

　　枚举算法解决方案：

　　问题的表述(即解法：公鸡、母鸡、小鸡的个数分别为n1、n2、n3；范围是0 ~ N .把对象一一列举出来：列出三层循环可想而知~验证每个个体是否满足N1N2N3==N，5N13N2N3/3==M但是：很明显，n1,n2,n3不是相互独立的，这里的n1+ n2+ n3==n,可以代替一个变量，从而变成两层循环。。

　　4.实际例子3从数组A中选两个数，这两个数之和是k的倍数，有多少种方案？

　　枚举算法分析：

　　选择一个对象就是解的表达式，i j是选择的两个数；是范围(I 0 ~ n；J 1 ~ n)逐个枚举对象：用上面的范围做两层循环。验证每个枚举个体(a b)%k=0，但上述算法复杂度达到O(n ^ 2)；

　　如果要优化：从数学模型层面从算法实现层面。

　　这个题目是用数学解析关系：(a b)% k=0=(a% k b% k)% k=0。

　　数组中每个元素% k的余数以二进制枚举的形式存储在这样的盒子中

　　5.实例5

　　解题思路：(二进制枚举算法)

　　选择对象(即解的表达式，设最长为d，d，d的取值范围为(0.01-10000))用二进制枚举(d=d/2.0)。如果sum(ki)==k，则验证li/d=ki，否则返回到关于子序列的枚举算法的第二步。6.实际例子6给定一个整数数组nums，求一个。

　　示例：

　　输入：[-2，1，-3，4，-1，2，1，-5，4]，输出：6解释：连续子阵列[4，-1，2，1]的最大和为6。如果在这个问题中使用枚举算法：对于任何子序列，左端i (0-n)和右端j (i=j=n)

　　算法的最内层还计算带有下标(I，j)的连续子序列的和；因此，该算法的时间复杂度为O (n 3)

　　这门课还有其他例子。我们将等到课程模块结束时再填写其他示例和所有代码。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。