穷举(枚举)算法,又称是暴力破解法,也是我接触最多的理解比较全面深刻的一个算法。
穷举算法就是一一列出所有可能的元素,用题目已知的条件验证每个结果,看是否满足。
枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件:
(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) 编辑 收藏 引用