现在的位置: 首页 > 综合 > 正文

暴力之简单枚举

2018年04月23日 ⁄ 综合 ⁄ 共 1173字 ⁄ 字号 评论关闭

暴力之简单枚举

优点:算法简单,容易编程实现,正确性易证明

缺点:速度慢,时间复杂度高

重点,对于题目的分析,寻找优化的方法。

对于枚举法,应该要权衡枚举的时间代价和所得到的信息量的关系。

例如(黑书思考题1.2.6)离散函数,给定一个离散函数,为集合{1,2.....n},取值为-2^32--2^32,找出函数图像上两个点,是的函数在这两点之间的点都在连线的下方,且此连线的斜率尽量大。

n很大的时候容易超时,可是有个O(n)的算法。这题很显然想到枚举任意两个点求是否符合条件,如果满足则进行斜率的比较。可是,对于任意三点A1,A2,A3,如果A1A3连接有A2在连线下方,则A1A3的斜率一定介于A1A2A2A3之间,那么可以得出,中间有隔着点的情况即使满足条件也不可能是最优解,因此,我们只需要枚举相邻两个点即可,扫描一遍所有点的时间复杂度为O(n)

翻硬币(黑书习题1.2.5)说有N(N<=10000)行硬币,每行9个,排成一个N*9的方阵,硬币有的正面朝上,有的正面朝下,可以进行的操作时把一整行或者一整列的所有硬币翻过来,问怎么翻能够使得正面朝上的硬币尽量多。很显然,列数远远少于行数,那么,我们完全可以枚举列数(枚举行数是自杀行为…)是否有翻转,也就是说枚举每列的翻转情况,要么翻,要么不翻,时间复杂度为2^9=512,之后用贪心法扫描每行,如果该行反面的硬币数量大于正面的,那么就翻过来,否则不翻,这样总时间复杂度为O(N*2^9),如果直接枚举,由于每行每列要么翻要么不翻,显然时间复杂度为(2^(9*N)),由此可见,通过研究题目的特点可以大大降低时间复杂度,使得原来看起来不能枚举的题目变得可能。

此外,枚举待求数据的一小部分来进行推理也不失为一种好方法。例如2003年亚洲区赛广州赛区的一题,给一个数n,问是否可以由多个不同数的阶乘相加得来。这题看起来像是0/1背包,但是如果直接用枚举做可以让代码变得更简洁些。

现在要先来研究一个问题,就是n!>=0!+1!+...+(n-1)!ps:我依旧不会证明,但是打表出来显然成立…)当n=0的时候取等号。

那么,这道题的解法就显而易见了,当一个给定的数k,从大数的阶乘往小数阶乘扫描,如果大数阶乘i!小于等于给定的k时,执行k=k-i!(为什么要马上减去不用考虑其他的?),直到全部减完,如果k==0,那么说明给定的k满足条件,否则不满足条件。而为什么不需要考虑其他的呢?因为根据刚才的不等式,k-i>=0而不减,那么剩下的0!+...+(i-1)!即使都减去也没办法让k最终减完等于0。另外这题需要注意的是,0=1,最后结果是0输出yes,那么如果一开始的k给的就是0呢?那么需要判断一下刚开始给的数是否是0,如果是的话直接输出NO,不是的话才进行循环。(容易WA在这个地方…)

抱歉!评论已关闭.