穷举（枚举）算法，又称是暴力破解法，也是我接触最多的理解比较全面深刻的一个算法。
穷举算法就是一一列出所有可能的元素，用题目已知的条件验证每个结果，看是否满足。
枚举法的本质就是从所有候选答案中去搜索正确的解，使用该算法需要满足两个条件：
（1）可预先确定候选答案的数量；
（2）候选答案的范围在求解之前必须有一个确定的集合。
一般应用在规模比较小的问题上，因为穷举算法一般都是循环和条件判断来实现的，当循环比较多的时候可能，时间复杂性和空间复杂性都很大。
举几个例子来看看：
委派任务
某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：
1)A和B两人中至少去一人；
2)A和D不能一起去；
3)A、E和F三人中要派两人去；
4)B和C都去或都不去；
5)C和D两人中去一个；
6)若D不去，则E也不去。
问应当让哪几个人去？
我们可以根据已知信息得到一些限制性的条件，假设能去执行任务的代表是1，而不能去执行任务的是0，
A+B >1 :表示A,B至少一人要去
A+D != 2:表示AD不能同时去
A+E+F == 2：表示三者中派两人去
B+C == 0 & B+C == 2:表示BC要么都去，要么都不去
C+D == 1:表示CD只能有一人去，
D+E == 0 & D==1表示：D不去的话，则E也不去，D去的话，E随便，
核心算法
nt a,b,c,d,e,f;
for(a=1;a>=0;a--) /*穷举每个人是否去的所有情况*/
for(b=1;b>=0;b--) /*1:去 0:不去*/
for(c=1;c>=0;c--)
for(d=1;d>=0;d--)
for(e=1;e>=0;e--)
for(f=1;f>=0;f--)
if(a+b>=1&&a+d!=2&&a+e+f==2
&&(b+c==0||b+c==2)&&c+d==1
&&(d+e==0||d==1))
{
printf("A will%s be assigned. \n",a?"":"not");
printf("B will%s be assigned. \n",b?"":"not");
printf("C will%s be assigned. \n",c?"":"not");
printf("D will%s be assigned. \n",d?"":"not");
printf("E will%s be assigned. \n",e?"":"not");
printf("F will%s be assigned. \n",f?"":"not");
}
一个比较有代表性的问题就是填写运算符的游戏
5 5 5 5 5 =5
由于算术表达式的特殊性，在编程求解这个算式时，需要注意以下几点：
–（1）当填入除号时，要求右侧的数不能为0。
–（2）乘除的运算级别比加减高。
代码如下：
int j,i[5]; //循环变量 ，数组i用来表示4个运算符
int sign;//累加运算时的符号
int result; //保存运算式的结果值
int count=0; //计数器，统计符合条件的方案
int num[6]; //保存操作数
float left,right; //保存中间结果
char oper[5]={' ','+','-','*','/'}; //运算符
printf("请输入5个数：");
for(j=1;j<=5;j++)
scanf("%d",&num[j]);
printf("请输入结果：");
scanf("%d",&result);
for(i[1]=1;i[1]<=4;i[1]++)//循环4种运算符，1表示+，2表示-,3表示*，4表示/
{
if((i[1]<4) || (num[2]!=0))//运算符若是/,则第二个运算数不能为0
{
for(i[2]=1;i[2]<=4;i[2]++)
{
if((i[2]<4) || (num[3]!=0))
{
for(i[3]=1;i[3]<=4;i[3]++)
{
if((i[3]<4) || num[4]!=0)
{
for(i[4]=1;i[4]<=4;i[4]++)
{
if((i[4]<4) || (num[5]!=0))
{
left=0;
right=num[1];
sign=1;
for(j=1;j<=4;j++)
{
switch(oper[i[j]])
{
case '+':
left=left+sign*right;
sign=1;
right=num[j+1];
break;
case '-':
left=left+sign*right;
sign=-1;
right=num[j+1];
break;//通过f=-1实现减法
case '*':
right=right*num[j+1];
break;//实现乘法
case '/':
right=right/num[j+1];//实现除法
break;
}
}
if(left+sign*right==result)
{
count++;
printf("%3d：",count);
for(j=1;j<=4;j++)
printf("%d%c",num[j],oper[i[j]]);
printf("%d=%d\n",num[5],result);
}
}
}
}
}
}
}
}
}
if(count==0)
printf("没有符合要求的方法！\n");
posted on 2011-09-25 10:22
mengkai 阅读(949)
评论(0) 编辑 收藏 引用