暴力出奇迹 打表出省一
枚举算法 也称为穷举算法,它的核心思想是根据问题中的“约束条件”,将问题的所有可能答案一一列举出来,然后再逐个验证是否符合整个问题的求解要求,从而求得满足问题要求的正确答案。
枚举算法 暴力的枚举所有可能,尽可能地尝试所有的方法。虽然枚举算法非常暴力,而且速度可能很慢,但确实我们最应该优先考虑的。因为枚举法编程的实现最简单,并且得到的结果总是正确的,在此基础上再进一步尝试优化,是编程水平提升的必经之路。
使用枚举算法需要满足两个条件:
❶、可预先确定候选答案的数量。
❷、候选答案的范围在求解之前必须有一个确定的集合。
根据问题的条件将可能的情况一 一列举起来,逐一尝试找出问题的解。有时问题的规模太大,可以排除一些明显不合理的情况。
枚举法的步骤:
◆ 确定枚举对象和枚举范围:分析问题所涉及的所有情况,确定枚举的要素,再分析每个要素的范围。
◆ 找出约束条件:分析问题的解需要满足的条件,并用逻辑表达式实现。一一枚举可能的情况,根据约束条件,验证是否是问题的解。
◆ 对枚举法的优化 根据问题的需要,对约束范围或约束条件的数学优化。
自学习循环结构以来,我们就已经常常使用到循环枚举。
枚举法的缺点:由于枚举算法要通过列举问题的所有状态来得到满足条件的解,因此在问题规模变大时,其效率一般是比较低的。
但是,枚举算法也有自己特有的优点:
❶、建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。
❷、多数情况下容易编程实现,也容易调试。
枚举法种三类常见问题的优化思路:
1、循环枚举:减少枚举量、去掉重复情况、转换思维,枚举其他要素。
2、子集枚举:抽象成集合,并集、交集、包含、属于、补集,集合的枚举,枚举子集的复杂度分析;
3、排列枚举:枚举排列的原理、熟练使用next_permutation() 函数求下一个序列,枚举排列的复杂度分析。
我们在后续的学习过程中,将不断进行各种枚举的优化。