计算机算法:穷举法
穷举法
穷举法是程序设计中使用最为普遍的一种基础算法。计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老算法。它一般是在一时半会不到解决问题的更好途径，即从数学上不到求解的公式或规律时，根据问题中的“约束条件”，将求解的所有可能情况一一列举出来，然后再逐一验证它否符合整个问题的求解要求，从而得到问题的所有解。
示例1：求满足表达式A+B=C的所有整数解，其中A,B,C为1~3之间的整数。
【分析】本题非常简单，即枚举变量A，B，C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。
【算法】算法用伪代码描述如下：
for A:=1 to 3 do
for B:=1 to 3 do
for C:=1 to 3 do
if(A+B=C) then
writeln(A,’’,B,’’C);
【流程图】
所谓穷举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定那些是无用的，哪些是有用的。能使命题成立的，即为解。
在本案例中解变量有3个：A，B，C。其中：
解变量A的可能取值范围A∈｛1,2,3｝
解变量B的可能取值范围B∈｛1,2,3｝
解变量C的可能取值范围C∈｛1,2,3｝
从而问题的可能解有3*3*3=27个，可能解集
在上述可能解集中，满足题目给定的检验条件（A+B==C）的解元素，即为问题的解。
穷举法的适用范围：其一，能确定解变量（枚举变量）的个数n，其二，每个解变量Ai（1<=i<=n）的可能值能确定范围且能连续取得。
设解变量的个数是n，Ai1----解变量Ai的最小值；Aik----解变量Ai的最大值（1≤i≤n）；即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank
算法框架如下（伪代码）：
for A1←A11 to A1k do
……
for Ai←Ai1 to Aik do
……
for An←An1 to Ank do
if状态（A1,…,Ai,…,An）满足检验条件
then 输出问题的解
穷举法（枚举法）的特点是算法简单，但是有时运算量大。为了提高效率必须优化枚举算法。
枚举算法的时间复杂度=状态总数*考查单个状态的耗时
要优化算法，可以从以下方面着手：
计算机的特点（1）排除明显不属于解集的元素
（2）减少状态总数（即减少枚举变量和枚举变量的值域）
（3）减低单个状态的考察代价
对于示例1其算法显然可以修改如下：
for A:=1 to 3 do
for B:=1 to 3 do
begin
C:=A+B;
If (C>=1) and (C<=3) then 输出A,B,C
end
通过变量的依赖关系减少了解变量的个数（局部枚举），优化了枚举算法，n^3  n^2。
【流程图】
示例2：百鸡百钱问题。公元前5世纪，我国古代数学家张丘建在他的《算经》中提出了著名的百鸡百钱问题“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，鸡翁，母，雏各几何？”
【分析】
根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不合理的情况，尽可能减少问题可能解的列举数目，然后出满足问题条件的解。
完成百鸡百钱问题可以选择两种不同的方法实现。其一是常规算法（懒惰枚举）的实现，其二是改进算法（非懒惰枚举）的实现，以实验方法证明对于同一问题可以有不同的枚举范
围，不同的枚举对象，解决问题的效益差别会很大。
【算法】
算法设计一（懒惰枚举法）：首先问题有三种不同的鸡，那么我们可以设鸡翁为x只，鸡母为y只，鸡雏为z只。由题意给出一共要用100钱买一百只鸡，如果我们全部买鸡翁最多可以买100/5=20只，显然x的取值范围是1~20之间；如果全部买鸡母最多可以买100/3=33只，显然y的取值范围在1~33之间；如果全部买鸡雏最多可以买100*3=300只，可是题目规定是买100只，所以z的取值范围是1~100.那么约束条件为：x+y+z=100且5*x+3*y+z/3=100。
懒惰算法算法语言描述
main()
{
int x,y,z;  //定义鸡翁，鸡母，鸡雏
int count=0; //统计时间复杂度的变量
for(x=1;x<=20;x++) //鸡翁的取值范围
for(y=1;y<=34;y++) //鸡母的取值范围
for(z=1;z<=100;z++) //鸡雏的取值范围
100==x+y+z and 100==5*x+3*y+z/3;  //约束条件
Cout<<x<<y<<z;//输出鸡翁，鸡母，鸡雏的可能取值
count++; //统计此算法的时间复杂度
}
【流程图】
算法设计二（非懒惰枚举法）：假如设了鸡翁和鸡母的个数为x和y了，那么鸡翁和鸡母的数量就是确定的，那么鸡雏的数量就是固定的为100-x-y，那么此时就不再需要进行枚举了，约束条件就只有一个了：5*x+3*y+z/3=100.
非懒惰算法算法语言描述
main()
{
int x,y,z;
int count;
for(x=1;x<=20;x++)
for(y=1;y<=33;y++)
{
z=100-x-y;
if(z mod 3=0 and 5*x+3*y+z/3=100)
cout<<x<<y<<z; //输出鸡翁，鸡母，鸡雏的可能取值

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。