枚举算法 |
您所在的位置:网站首页 › 枚举法例题 › 枚举算法 |
1. 枚举算法
设计步骤: 确定枚举对象(即问题解的表达形式,一般需要用若干参数来描述)逐一列举可能(根据枚举对象的参数构造循环,一一列举其表达式的每一种取值情况)逐一验证可能解( 根据问题解的要求,验证枚举对象表达式的每一个取值,如果满足条件,则采纳它,否则抛弃之。)这里注意:①对象不能重复,不能遗漏; ② 每个参数要相互独立,这个时候算法才能简洁;每个参数的取值范围要搞清楚,尽可能小。 2. 实际例子1解答 确定对象:对象就是解的表达式,用一个参数x表示;x的范围是(0~9)逐一列举对象:用 x 确定的循环来一一列举可能的解逐一验证可能的解,只有满足验证条件才能确定 x 的取值。解答: 确定对象:这个可能的对象是有两个参数组成的,i,j ( i 的范围是[1-9] , j 的范围是[0--9] )逐一列举循环:由于这里有两个参数,那必定要用到两层循环,一个以 i ,一个以 j。逐一验证这些枚举的个体,满足条件的才可以取值。当这里的三个数字都看不见的时候: 解答: 问题对象,这三个参数,其实可以看成是一个参数;x 取值100~999;这样参数减少了,代码易读;逐一枚举,利用 x 的取值范围构成循环;但是这里三个参数看成是一个参数并没有减少复杂度逐一进行验证,取满足条件的值 3.实际例子二公鸡:5元一只 母鸡:3元一只 小鸡:1元三只 问:m 元买 n 只鸡有几种方案? 枚举算法解答: 问题对象(即解的表达式:公鸡,母鸡,小鸡数量分别是:n1,n2,n3;范围都是0~n逐一列举对象:可想而知,要列出三层循环~验证每个个体是否满足 n1+ n2+ n3==n, 5n1+ 3n2+ n3 /3 ==m但是:很明显,n1,n2,n3不是相互独立的,这里的n1+ n2+ n3==n,可以代替一个变量,从而变成两层循环。 4.实际例子三从数组 A 中选出两个数,这两个数的和是 k 的倍数,问有几种方案? 枚举算法分析: 选择对象 对象就是解的表达形式,设 i j 为选出的两个数;范围是( i 0~n ; j i+1 ~ n )一一枚举对象:利用上面的范围去做两层循环。验证每一个枚举个体 (a + b)%k = 0但是上面的算法复杂度达到了O(n^2); 如果要优化的话:① 从数学模型层面 ② 从算法实现的层面 本题就是用到了数学上的解析关系:(a + b)% k = 0 == (a%k +b%k) % k = 0 将数组的每一个元素 % k 得到的余数存入 这样几个盒子:解题思路:(二分枚举算法) 选择对象(即解的表达形式,设长度最长是 d ,d 的范围是 (0.01--10000))二分枚举( d = d / 2.0)验证 li / d = ki if sum(ki) == k 结束 else 返回第二步 有关子序列的枚举算法 6. 实际例子六给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。这道题如果用枚举算法:对于任何一个子序列,左端 i (0-n)右端 j ( i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |