窮舉（枚舉）算法，又稱是暴力破解法，也是我接觸最多的理解比較全面深刻的一個算法。
窮舉算法就是一一列出所有可能的元素，用題目已知的條件驗(yàn)證每個結(jié)果，看是否滿足。
枚舉法的本質(zhì)就是從所有候選答案中去搜索正確的解，使用該算法需要滿足兩個條件：
（1）可預(yù)先確定候選答案的數(shù)量；
（2）候選答案的范圍在求解之前必須有一個確定的集合。
一般應(yīng)用在規(guī)模比較小的問題上，因?yàn)楦F舉算法一般都是循環(huán)和條件判斷來實(shí)現(xiàn)的，當(dāng)循環(huán)比較多的時候可能，時間復(fù)雜性和空間復(fù)雜性都很大。
舉幾個例子來看看：
委派任務(wù)
某偵察隊(duì)接到一項(xiàng)緊急任務(wù)，要求在A、B、C、D、E、F六個隊(duì)員中盡可能多地挑若干人，但有以下限制條件：
1)A和B兩人中至少去一人；
2)A和D不能一起去；
3)A、E和F三人中要派兩人去；
4)B和C都去或都不去；
5)C和D兩人中去一個；
6)若D不去，則E也不去。
問應(yīng)當(dāng)讓哪幾個人去？
我們可以根據(jù)已知信息得到一些限制性的條件，假設(shè)能去執(zhí)行任務(wù)的代表是1，而不能去執(zhí)行任務(wù)的是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");
}
一個比較有代表性的問題就是填寫運(yùn)算符的游戲
5 5 5 5 5 =5
由于算術(shù)表達(dá)式的特殊性，在編程求解這個算式時，需要注意以下幾點(diǎn)：
–（1）當(dāng)填入除號時，要求右側(cè)的數(shù)不能為0。
–（2）乘除的運(yùn)算級別比加減高。
代碼如下：
int j,i[5]; //循環(huán)變量 ，數(shù)組i用來表示4個運(yùn)算符
int sign;//累加運(yùn)算時的符號
int result; //保存運(yùn)算式的結(jié)果值
int count=0; //計(jì)數(shù)器，統(tǒng)計(jì)符合條件的方案
int num[6]; //保存操作數(shù)
float left,right; //保存中間結(jié)果
char oper[5]={' ','+','-','*','/'}; //運(yùn)算符
printf("請輸入5個數(shù)：");
for(j=1;j<=5;j++)
scanf("%d",&num[j]);
printf("請輸入結(jié)果：");
scanf("%d",&result);
for(i[1]=1;i[1]<=4;i[1]++)//循環(huán)4種運(yùn)算符，1表示+，2表示-,3表示*，4表示/
{
if((i[1]<4) || (num[2]!=0))//運(yùn)算符若是/,則第二個運(yùn)算數(shù)不能為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實(shí)現(xiàn)減法
case '*':
right=right*num[j+1];
break;//實(shí)現(xiàn)乘法
case '/':
right=right/num[j+1];//實(shí)現(xiàn)除法
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 閱讀(957)
評論(0) 編輯 收藏 引用