枚举法_数学、计算机科学计算方法

枚举法

数学、计算机科学计算方法

在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法．

简介

枚举法是利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。

在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。

特点

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

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

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

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

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

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

基本思路

枚举法的基本思想是: 逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。采用枚举算法解题的基本思路：

（1）确定枚举对象、枚举范围和判定条件；

（2）枚举可能的解，验证是否是问题的解。

结构

枚举算法的一般结构：循环+判断语句。

首先考虑一个问题：将1到100之间的所有整数转换为二进制数表示。

算法一

for i:=1 to 100 do begin

将i转换为二进制，采用不断除以2，余数即为转换为2进制以后的结果。一直除商为0为止。

end;

算法二

二进制加法，此时需要数组来帮忙。

program p;

var a:array[1..100] of integer; {用于保存转换后的二进制结果}

i,j,k:integer;

begin

fillchar(a,sizeof(a),0); {100个数组元素全部初始化为0}

for i:=1 to 100 do begin

k:=100;

while a[k]=1 do dec(k); {找高位第一个为0的位置}

a[k]:=1; {找到了立刻赋值为1}

for j:=k+1 to 100 do a[j]:=0; {它后面的低位全部赋值为0}

k:=1;

while a[k]=0 do inc(k); {从最高位开始找不为0的位置}

write('(',i,')2=');

for j:=k to 100 do write(a[j]); {输出转换以后的结果}

writeln;

end;

end.

枚举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

优缺点

优点

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

缺点

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

枚举法的优化

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

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

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

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

⑴提取有效信息；⑵减少重复计算；⑶将原问题化为更小的问题；⑷根据问题的性质进行截枝；

⑸引进其他算法。

参考资料

浅谈“枚举法”.知网.

二进制数与数字通信.知网.

最新修订时间：2023-11-17 21:51

条目作者

小编

资深百科编辑

概述

简介

特点

参考资料