穷举(一):穷举法的基本思想

穷举是用计算机求解问题最常用的方法之一,常用来解决那些通过公式推导、规则演绎的方法不能解决的问题。采用穷举法求解一个问题时,通常先建立一个数学模型,包括一组变量、以及这些变量需要满足的条件。问题求解的目标就是确定这些变量的值。根据问题的描述和相关的知识,能为这些变量分别确定一个大概的取值范围。在这个范围内对变量依次取值,判断所取的值是否满足数学模型中的条件,直到找到全部符合条件的值为止。穷举法(枚...

穷举是用计算机求解问题最常用的方法之一,常用来解决那些通过公式推导、规则演绎的方法不能解决的问题。采用穷举法求解一个问题时,通常先建立一个数学模型,包括一组变量、以及这些变量需要满足的条件。问题求解的目标就是确定这些变量的值。根据问题的描述和相关的知识,能为这些变量分别确定一个大概的取值范围。在这个范围内对变量依次取值,判断所取的值是否满足数学模型中的条件,直到找到全部符合条件的值为止。

穷举法(枚举法)的基本思想是:列举出所有可能的情况,逐个判断有哪些是符合问题所要求的条件,从而得到问题的全部解答。

它利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检查,从中找出符合要求的答案。

用穷举算法解决问题,通常可以从两个方面进行分析。

(1)问题所涉及的情况:问题所涉及的情况有哪些,情况的种数可不可以确定。把它描述出来。应用穷举时对问题所涉及的有限种情形必须一一列举,既不能重复,也不能遗漏。重复列举直接引发增解,影响解的准确性;而列举的遗漏可能导致问题解的遗漏。

(2)答案需要满足的条件:分析出来的这些情况,需要满足什么条件,才成为问题的答案。把这些条件描述出来。

只要把这两个方面分析好了,问题自然会迎刃而解。

穷举通常应用循环结构来实现。在循环体中,根据所求解的具体条件,应用选择结构实施判断筛选,求得所要求的解。

穷举法的程序框架一般为:

cnt=0; // 解的个数初值为0

for(k=<区间下限>;k<=<区间上限>;k ) // 根据指定范围实施穷举

if (<约束条件>) // 根据约束条件实施筛选

{

cout<<(<满足要求的解>); // 输出满足要求的解

cnt ; // 统计解的个数

}

【例1】硬币方案

有50枚硬币,可能包括4种类型:1元、5角、1角和5分。

已知50枚硬币的总价值为20元,求各种硬币的数量。

例如:2、34、6、8就是一种方案。而2、33、15、0是另一个可能的方案,显然方案不唯一。

编写程序求出类似这样的不同的方案一共有多少种?

(1)编程思路。

直接对四种类型的硬币的个数进行穷举。其中,1元最多20枚、5角最多40枚、1角最多50枚、5分最多50枚。

另外,如果以元为单位,则5角、1角、5分会化成浮点型数据,容易计算出错。可以将1元、5角、1角、5分变成100分、50分、10分和5分,从而全部采用整型数据处理。

(2)源程序及运行结果。

#include <iostream>

using namespace std;

int main()

{

int a,b,c,d,cnt=0;

for(a=0;a<=20;a )

for(b=0;b<=40;b )

for(c=0;c<=50;c )

for(d=0;d<=50;d )

{

if(a*100 b*50 c*10 d*5==2000 && a b c d==50)

{

cout<<a<<" , "<<b<<" , "<<c<<" , "<<d<<endl;

cnt ;

}

}

cout<<"Count="<<cnt<<endl;

return 0;

}

(3)程序的优化。

上面的程序采用穷举法求解,比较简单。但在穷举结构的设置、穷举参数的选取等方面存在着改进与优化的空间。

一般来说,在采用穷举法进行问题求解时,可从两个方面来优化考虑。

1)建立简洁的数学模型。

数学模型中变量的数量要尽量少,它们之间相互独立。这样问题解的搜索空间的维度就小。反应到程序代码中,循环嵌套的层次就少。例如,上面的程序中,采用变量a、b、c、d分别表示1元、5角、1角和5分硬币的枚数,对这4个变量穷举,循环层次为4层。实际上这4个变量彼此间有两个条件在约束,或者枚数等于50,或者总价值为20元。因此,可以只穷举3个变量,另外一个变量通过约束条件求出,从而将循环层次减少为3层。

2)减小搜索的空间。

利用已有的知识,缩小数学模型中各个变量的取值范围,避免不必要的计算。反应到程序代码中,循环体被执行的次数就减少。例如,在穷举时,先考虑1元的枚数a,最多为20枚(即0<=a<=20),再考虑5角的枚数b,若采用总价值不超过20元约束,则其枚数最多为(2000-a*100)/50枚(即0<=b<=(2000-a*100)/50),之后考虑1角的枚数c,其枚数最多为 (2000-a*100-b*50)/10(即0<=c<=(2000-a*100-b*50)/10)。这样穷举的循环次数会大大减少。

采用上述思路优化后的源程序如下。

#include <iostream>

using namespace std;

int main()

{

int a,b,c,d,cnt=0;

for(a=0;a<=20;a )

for(b=0;b<=(2000-a*100)/50;b )

for(c=0;c<=(2000-a*100-b*50)/10;c )

{

d=(2000-a*100-b*50-c*10)/5; // 剩下的用5分硬币填充

if(a b c d==50)

{

cout<<a<<" , "<<b<<" , "<<c<<" , "<<d<<endl;

cnt ;

}

}

cout<<"Count="<<cnt<<endl;

return 0;

}

也可以采用总枚数不超过50枚约束。先考虑1元的枚数a,最多为20枚(即0<=a<=20),再考虑5角的枚数b,则其枚数最多为(50-a)枚(即0<=b<=(50-a),之后考虑1角的枚数c,其枚数最多为 (50-a-b)枚(即0<=c<=50-a-b)。采用这种思路优化后的源程序如下。

#include <iostream>

using namespace std;

int main()

{

int a,b,c,d,cnt=0;

for(a=0;a<=20;a )

for(b=0;b<=50-a;b )

for(c=0;c<=50-a-b;c )

{

d=50-a-b-c; // 剩下的用5分硬币填充

if(100*a 50*b 10*c 5*d==2000)

{

cout<<a<<" , "<<b<<" , "<<c<<" , "<<d<<endl;

cnt ;

}

}

cout<<"Count="<<cnt<<endl;

return 0;

}

源文地址:https://www.guoxiongfei.cn/cntech/19289.html
0