-

常用算法——穷举搜索法

二、穷举搜索法

穷举搜索法是对可能是解的众多候 选解按某种顺序进行逐一枚举和检验，

并从众找出那些

符合要求 的候选解作为问题的解。

【问题】

将

A

、

B

、

C

、

D

、

E

、

F

这六个变量排成如图所示的三角形，这六个变量分别取

[1

< br>，

6]

上的整数，且均不相同。求使三角形三条边上的变 量之和相等的全部解。如图就是一

个解。

程序引入变量

a

、

b

、

c

、

d

、

e

、< /p>

f

，并让它们分别顺序取

1

至

6

的证书，在它们互不相同

的条件下，

测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，

如相等即为

一种满足要求的排列，

把它们输出 。

当这些变量取尽所有的组合后，

程序就可得到全部可能

的解。细节见下面的程序。

【程序

1

】

# include

void main()

{

int a,b,c,d,e,f;

for (a=1;a<=6;a++)

for (b=1;b<=6;b++)

{

if (b==a)

continue;

for (c=1;c<=6;c++)

{

if (c==a)||(c==b)

continue;

for (d=1;d<=6;d++)

{

if (d==a)||(d==b)||(d==c)

continue;

for (e=1;e<=6;e++)

{

if (e==a)||(e==b)||(e==c)||(e==d)

continue;

f=21-(a+b+c+d+e);

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a))

{

printf(“%6d,a);

printf(

“%4d%4d”,b,f);

printf(“%2d%4d%4d”,c,d,e);

scanf(“%*c”);

}

}

}

}

}

}

按穷举法编写的程序通常不能适应变化的情况。

如问题改成有

9

个变量排成三角形，

每条边

有

4

个变量的情况，程 序的循环重数就要相应改变。

对一组数穷尽所有排列，

还有更直接 的方法。

将一个排列看作一个长整数，

则所有排列对