3.0暴力枚举
枚举
枚举,暴力的一种算法,典型利用"计算机算力大大高于人力"这件事的做法
枚举,顾名思义:有序的尝试每一种可能
在书里,枚举被单独列为一章,不过每一节都是各种花式实战
因此只用了一个MD笔记来记录它
鬼畜奥数题
我们现在有一道奥数题,要求使用1-9九个数字填入下方的等式:
[][][]+[][][]=[][][]
注意:每个数字只能用一次
请问一共有多少种组合
#include
int main(){
int a,b,c,d,e,f,g,h,i = 0 ; //九个数字
int total = 0 ; //计数
//下面开始整活
for(a=1;a<=9;a++)
for(b=1;b<=9;b++)
for(c=1;c<=9;c++) //第一个数的百位a,十位b,个位c
for(d=1;d<=9;d++)
for(e=1;e<=9;e++)
for(f=1;f<=9;f++) //第二个
for(g=1;g<=9;g++)
for(h=1;h<=9;h++)
for(i=1;i<=9;i++){
//下面判断每个数字都不相等
if(a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h && a!=i &&
b!=c && b!=d && b!=e && b!=f && b!=g && b!=h && b!=i &&
c!=d && c!=e && c!=f && c!=g && c!=h && c!=i &&
d!=e && d!=f && d!=g && d!=h && d!=i &&
e!=f && e!=g && e!=h && e!=i &&
f!=g && f!=h && e!=i &&
g!=h && g!=i &&
h!=i ){
//只要理解了就可以无视上面那个大台阶,然后我们判断等式是正确的这件事
if( a*100+b*10+c + d*100+e*10+f == g+100+h*10+i){
total++ ; //符合条件了肯定++啊
printf("%d%d%d + %d%d%d = %d%d%d \n",a,b,c,d,e,f,g,h,i);
//找到了
}
}
}
}
printf("total = %d",total/2);
getchar(); getchar();
return 0 ;
}
至此我们已经初见了枚举的暴力之处,另外在写判断的时候还是很折磨的
“那么有什么办法方便一点呢”,其实可以。当我们利用标记法(见第一章)就可以节省一点代码量
下面给出用标记法的代码:
#include
int main(){
int a[10],i,total = 0 , book[10],sum;
for(a[1]=1;a[1]<=9;a[1]++)
for(a[2]=1;a[2]<=9;a[2]++)
for(a[3]=1;a[3]<=9;a[3]++) //第一个数的百位a,十位b,个位c
for(a[4]=1;a[4]<=9;a[4]++)
for(a[5]=1;a[5]<=9;a[5]++)
for(a[6]=1;a[6]<=9;a[6]++) //第二个
for(a[7]=1;a[7]<=9;a[7]++)
for(a[8]=1;a[8]<=9;a[8]++)
for(a[9]=1;a[9]<=9;a[9]++){
//下面是对每一个数的操作
for(i=1;i<=9;i++){
book[i] = 0 ; //初始化book数组
}
for(i=1;i<=9;i++){
book[a[i]] = 1;//出现过某个数,就将它标记
}
//下面统计共出现了多少个不同的数
sum = 0 ;
for(i=1;i<=9;i++){
sum+=book[i] ;
}
if(sum == 9){
//如果出现了九个数,我们就尝试验证等式
if(a[1]*100+a[2]*10+a[3] + a[4]+a[5]+a[6] = a[7]a[8]a[9]){
total++;
printf("%d%d%d + %d%d%d = %d%d%d",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
}
}
printf("total = %d" , total/2);
getchar(); getchar();
return 0 ;
}
除了鬼畜奥数,书中还举了“炸弹人”和“火柴棍等式”两个例子
但是枚举的思想是一样的,这里就不一一写出后两者的代码了
小结:枚举
那么一般而言,我们需要怎么完成一次合格的“暴力枚举”呢?
1.分析相关的情况,分析题意
2.列举所有的情况(枚举的核心,这一步就大胆做就好了,都枚举了还考虑超不超时?)
3.在2的基础上(一般而言2是通过循环实现的),进行条件判断
(比如上面的奥数题,就是检查“各个数不相等”和“等式成立”两个条件)
4.如果题目有多个要求,重复2-3步,直到枚举完所有要求
当然,暴力枚举的缺点很明显:时间与内存,因此很多时候不是枚举就完事了
需要带着脑子枚举,有的时候还要利用其它算法优化枚举,不过这就是后话了