暴力枚举算法

《啊哈！算法》学习笔记

        本博客的题目仅用暴力枚举，并不一定是最好的解法，主要是了解枚举算法

        例题一：两方框奥数

               在两个方框内填入相同的数字使得等式成立： 

代码如下： 

for(i=1;i<=9;i++)
{if((i*10+3)*6528 == (30+i)*8256)printf("%d",i);
}

        

        例题二：九方框奥数

        将数字1~9分别填入9个方框中，每个数字只能使用一次使等式成立，例如173+286=459，其中286+173=459与173+286=459是同一种组合。

 

#include<stdio.h>int main()
{int a,b,c,d,e,f,g,h,i,total = 0;for(a=1;a<=9;a++)for(b=1;b<=9;b++)for(c=1;c<=9;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  && f!=i&&  g!=h && g!=i&&  h!=i&& 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);return 0;}

其中的a,b,c,d,e,f,g,h,i可以用一个数组代替 ，然后用标记的方法判断互不相等。代码如下：

#include<stdio.h>int main()
{int a[9]={0};int book[9]={0};int sum = 0,total=0;for(a[0]=1;a[0]<=9;a[0]++)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]++)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 (int i = 0; i < 9; i++){book[i]=0;}for (int i = 0; i < 9; i++){book[a[i]-1]=1;}sum = 0;for (int i = 0; i < 9; i++){sum+=book[i];}if (sum==9 && a[0]*100+a[1]*10+a[2]+a[3]*100+a[4]*10+a[5] == a[6]*100+a[7]*10+a[8]){total++;printf("%d%d%d+%d%d%d=%d%d%d\n",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);}   }printf("total=%d",total/2);return 0;
}

如果sum等于9，就代表1~9每个数字只有一个。

例题三：炸弹人

        现在有一个特殊关卡如图。你只有一枚炸弹，但是这枚砸蛋威力超强（杀伤距离超长，可消灭杀伤范围内所有的敌人）。请问在哪里放置炸弹才可以消灭最多的敌人呢？

        我们先将这个地图模型化。墙用#表示。这里有两种墙，一种是可以被炸掉的但是由于现在只有一种炸弹，所以用#表示，炸弹是不能穿墙的。敌人用G表示，空地用 . 表示，当然炸弹只能放地上。

#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.###
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############  

我们需要统计上下左右四个方向消灭的敌人数。代码如下：

#include<stdio.h>int main()
{int x=0,y=0;char a[30][30]={'\0'};int i=0,j=0,m=0,n=0,sum=0,max=0,p=0,q=0;scanf("%d %d",&x,&y);getchar(); //读入换行符for ( i = 0; i < x; i++){for ( j = 0; j < y; j++){scanf("%c",&a[i][j]);  //读入地图// printf("yes!");}getchar(); //读入换行符}// ******************************测试读入数据for (int i = 0; i < x; i++){for (int j = 0; j < y; j++){printf("%c",a[i][j]);}printf("\n");}// ********************************for ( i = 0; i < x; i++){for ( j = 0; j < y; j++)  {if (a[i][j] == '.')   //枚举每块空地      {sum=0;// 该点上方敌人n=i,m=j;while (a[n][m]!='#')  //不为墙则继续搜索敌人{if (a[n][m] == 'G')  //为敌人则消灭{sum++;        //该空地消灭敌人总数加1}n--;printf("%d %d\n",n,m);}// 该点下方敌人n=i,m=j;while (a[n][m]!='#'){if (a[n][m] == 'G'){sum++;}n++;printf("%d %d\n",n,m);}// 该点左方敌人n=i,m=j;while (a[n][m]!='#'){if (a[n][m] == 'G'){sum++;}m--;printf("%d %d\n",n,m);}// 该点右方敌人n=i,m=j;while (a[n][m]!='#'){if (a[n][m] == 'G'){sum++;}m++;printf("%d %d\n",n,m);}if (sum>max)  //统计所有点中消灭敌人最大总数{max=sum;p=i;q=j;} }}}printf("(%d,%d)  %d",p,q,max);return 0; 
}

例题四：火柴棍等式 

         现在小哼有n根火柴，希望拼出形如A+B=C的等式。等式中的A、B、C均是用火柴棍拼出来的整数（若该数为非零，则最高位不能是0）。数字0~9的拼法如下图：

        例如现在小哼手上有14根火柴棍，则可以拼出两个不同的等式 0+1=1和1+0=1。

        再例如小哼有18根火柴棍，可以拼出9个等式：0+4=4、0+11=11、1+10=11、2+2=4、2+7=9、10+1=11和11+0=11。

        注意：

• 加号和等号各自需要两根火柴。
• 如果A!=B,则A+B=C与B+A=C是两个等式（A、B不能全为0）
• 所有火柴棍都必须用上。
• 规定时间为1s。

本题较为复杂，约束条件更多的需要我们自己去想，范围越小时间复杂度就越低。

        大题思路就是枚举A、B、C从零到各自的最大值，在满足约束条件的前提下形成等式。

我们先找出n个火柴拼出的A、B、C各自的最大值，假设火柴有24根，去掉+和=还有20个，可以组成10个1，A和B的值肯定小于等于C。

        我们假设B为0，还剩14根，A和C平分最大值为7根火柴；确定一个大致范围为小于1111（当然更精细也行）。那么就可以得到A、B、C的范围为0~1111。

        我们遍历A、B、C的时间复杂度为O（N^3）=1111^3,那我们可以想一想有没有办法降低一点，我们加上约束条件A+B=C便可直接得到C，将算法复杂度降到O（N^2）=1111^2；

        那么有一个问题，A+B=C（A==B）这种情况的约束条件怎么写呢？其实只需要考虑一种情况，这种情况只有0满足，0由六个火柴棍组成，共6×3+4=22个.并且只用22根火柴才会出现

#include<stdio.h>int num[10]={6,2,5,5,4,5,6,3,7,6}; //存放）0~9每个数字所需的火柴根数
int fun(int x) //返回A，B，C各自需要的火柴数
{int sum = 0;while (x/10!=0)  //两位数及以上的火柴数{sum+=num[x%10];x=x/10;}sum+=num[x]; //个位数火柴数return sum;
}int main()
{int A=0,B=0,C=0;int flag=0,sum=0;scanf("%d",&flag); //火柴总数int n=flag-4; //去掉+和=后的火柴总数for ( A = 0; A <= 1111; A++){for ( B = 0; B <= 1111; B++){C=A+B;if (fun(A)+fun(B)+fun(C)==n)//相加等于火柴数 {printf("%d + %d = %d\n",A,B,C);sum++;}}}if (n==18){sum--;}printf("%d",sum);return 0;
}

例题五：数的全排列

         123的全排列是123、132、213、312。1234的全排列为：1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4321

        求123的全排列

for(a=1;a<=3;a++)for(b=1;b<=3;b++)for(d=1;d<=3;d++){if(a!=b && a!=c && b!=c)printf("%d%d%d\n",a,b,c);}

        1234就是四层循环，如果123456789就需要9层循环，可以写出来，但复杂，大家可以去了解一下“搜索”算法来做这道题。