Question

枚举法解题技巧和方法

Answer 1

枚举法解题技巧和方法是：1、确定枚举对象、枚举范围和判定条件；2、枚举可能的解，验证是否是问题的解。

将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如：找出1到100之间的素数，需要将1到100之间的所有整数进行判断。

枚举法特点

枚举算法因为要列举问题的所有可能的答案，所以它具备以下几个特点：

1、得到的结果肯定是正确的；

2、可能做了很多的无用功，浪费了宝贵的时间，效率低下；

3、通常会涉及到求极值（如最大，最小，最重等）；

4、数据量大的话，可能会造成时间崩溃。

枚举法的优缺点

1、优点

算法简单，正确性容易证明，在局部地方使用枚举法，效果十分的好。

2、缺点

运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢。

枚举法的优化

枚举法的时间复杂度可以用状态总数*考察单个状态的耗时来表示，因此优化主要是：

1、减少状态总数（即减少枚举变量和枚举变量的值域）；

2、降低单个状态的考察代价。

优化过程从几个方面考虑。具体讲：

1、提取有效信息；

2、减少重复计算；

3、将原问题化为更小的问题；

4、根据问题的性质进行截枝；

5、引进其他算法。