No.3. 枚举

一、计算一个公式，将数字1~9分别填入空格，要求每个数字出现一次，并使等式成立

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]++)
　　　　　　　　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;　　//初始化标记数组
　　　　　　　　　　　　　　　　　　　　for(i=1;i<=9;i++)  book[a[i]]=1;　//a[i]出现，则标记为1
　　　　　　　　　　　　　　　　　　　　sum=0;
　　　　　　　　　　　　　　　　　　　　for(i=1;i<=9;i++)  sum = sum + book[i]; 　　//统计各数字出现的次数之和
　　　　　　　　　　　　　　　　　　　　if(sum==9 && 100*a[1]+10*a[2]+a[3] + 100*a[4]+10*a[5]+a[6] == 100*a[7]+10*a[8]+a[9])
　　　　　　　　　　　　　　　　　　　　　　{total++;
　　　　　　　　　　　　　　　　　　　　　　printf("%d%d%d + %d%d%d = %d%d%d\t",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;
}

二、炸弹人小游戏：简单场景，G=敌人， .=地面， #=墙壁，炸弹可以向上下左右四个方向无限杀敌，只要不遇到墙壁

int main(){
　　char a[20][20];　　//假设地图不超过该尺寸
　　int x,y,i,j,sum,m,n,max=0,p,q;
　　printf("input n*m matrix:");
　　scanf("%d %d",&n,&m);

　　for (i=0;i 　　　　scanf("%s",a[i]);　　//初始化地图
　　}
　　//G=敌人， .=地面， #=墙壁，炸弹可以向上下左右四个方向无限杀敌，只要不遇到墙壁
　　for(i=0;i 　　　　for(j=0;j 　　　　　　if(a[i][j]=='.'){
　　　　　　　　sum=0;

　　　　　　　　//每个方向判断之前，都要将(x,y)回归到(i,j)
　　　　　　　　x=i;y=j;  while(a[x][y]!='#') {if(a[x][y]=='G')  sum++;x--;}

　　　　　　　　x=i;y=j;  while(a[x][y]!='#') {if(a[x][y]=='G')  sum++;x++;}
　　　　　　　　x=i;y=j;  while(a[x][y]!='#') {if(a[x][y]=='G')  sum++;y--;}
　　　　　　　　x=i;y=j;  while(a[x][y]!='#') {if(a[x][y]=='G')  sum++;y++;}

　　　　　　　　if (sum>max){　　//记录位置
　　　　　　　　　　max=sum;
　　　　　　　　　　p=i;
　　　　　　　　　　q=j;
　　　　　　　　}
　　　　　　}
　　printf("Location: %d,%d",p,q);
　　printf("will kill %d enemy",max);
　　getchar();getchar();
　　return 0;
}

还有后续要解决的问题：

　　1.可走路径问题；

　　2.单向路径问题；

三、火柴棍问题：用 n 根火柴，拼出 A + B = C 的等式，+/= 各需两根火柴，0-9数字的火柴数如下：

 要求所有的火柴必须全部用上！

简单分析：

　　1.去除+/= 4根火柴之后，还有(n-4)可用于拼数字，因为1所用火柴最少，(n-4)/2可以估计A/B/C的最值，然后再进行枚举算法！

　　2.如果ABC都要枚举，那么时间复杂度O(N**3) 约1000秒；如果只枚举AB，推算C的话，时间复杂度只有O(N**2) 

int fun(int x){
　　int num=0;　　//计数变量，一定要初始化
　　/*
　　int a[10];
　　a[0]=6;a[1]=2;a[2]=5;a[3]=5;a[4]=4;a[5]=5;a[6]=6;a[7]=3;a[8]=7;a[9]=6;
　　*/
　　int f[10]={6,2,5,5,4,5,6,3,7,6};

　　while(x/10!=0){　　// 整除的商不为0，表示 x 超过1位数
　　　　num+=f[x%10]; //取余，使得统计数字所用的火柴数从低位开始计算
　　　　x=x/10;
　　}
　　num += f[x];　　　　//此时，x 的最高位还没统计 
　　return num;
}

int main(){
　　int i,j,k,n=18;

　　int sum=0;

　　for (i=0;i<11111;i++)
　　　　for(j=0;j<11111;j++)
　　　　{
　　　　　　k=i+j;
　　　　　　if (fun(i)+fun(j)+fun(k) == n-4){
　　　　　　　　printf("%d + %d = %d \n",i,j,k);

　　　　　　　　sum++;
　　　　　　}
　　　　}

　　printf("可拼出%d个不同的等式",sum);
　　getchar();getchar();
　　return 0;
}

四、数的全排列：和一、枚举计算公式一样

int main(){
　　int i,sum,total=0;
　　int a[4],book[4];
　　for (a[1]=1;a[1]<=4;a[1]++)
　　　　for(a[2]=1;a[2]<=4;a[2]++)
　　　　　　for(a[3]=1;a[3]<=4;a[3]++)
　　　　　　　　for(a[4]=1;a[4]<=4;a[4]++)
　　　　　　　　{
　　　　　　　　　　for(i=1;i<=4;i++)
　　　　　　　　　　　　book[i]=0;
　　　　　　　　　　for(i=1;i<=4;i++)
　　　　　　　　　　　　book[a[i]]=1;
　　　　　　　　　　sum=0;
　　　　　　　　　　for (i=1;i<=4;i++)
　　　　　　　　　　　　sum+=book[i];
　　　　　　　　　　if(sum==4)
　　　　　　　　　　{
　　　　　　　　　　　　printf("%d%d%d%d\t",a[1],a[2],a[3],a[4]);
　　　　　　　　　　　　total++;
　　　　　　　　　　}
　　　　　　　　}
　　printf("共有%d种排列",total);
　　getchar();getchar();
　　return 0;
}