《啊哈！算法》学习笔记
本博客的题目仅用暴力枚举，并不一定是最好的解法，主要是了解枚举算法
例题一：两方框奥数
在两个方框内填入相同的数字使得等式成立：
代码如下：
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层循环，可以写出来，但复杂，大家可以去了解一下“搜索”算法来做这道题。
