首页 > 编程知识 正文

枚举算法实例,python解析算法枚举算法

时间:2023-05-04 09:52:30 阅读:195884 作者:4427

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 得到的余数存入 这样几个盒子:二分枚举

5.实际例子五

解题思路:(二分枚举算法)

选择对象(即解的表达形式,设长度最长是 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<=j <=n)

算法最里层还要计算 这个下标为(i,j)的连续子序列的和;故算法的时间复杂度是O(n^3)

 

 

 

这门课中还例举了其他例子,这里将等到课程块结束时,填上另外的例子和全部代码。

 

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。