窮舉（枚舉）算法，又稱是暴力破解法，也是我接觸最多的理解比較全面深刻的一個算法。
窮舉算法就是一一列出所有可能的元素，用題目已知的條件驗證每個結果，看是否滿足。
枚舉法的本質就是從所有候選答案中去搜索正確的解，使用該算法需要滿足兩個條件：
（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 閱讀(979)
評論(0) 編輯 收藏 引用