啊哈磊老师的《啊哈！算法》学习记录。
枚举法可以直观的解决我们的问题，但是会浪费时间。
比如我们有一个：【】【】【】+【】【】【】=【】【】【】，我们将1~9填入到里面，那么有多少种方法呢？
使用枚举可以直观的写出来：
#include<stdio.h>
int main()
{
int a,b,c,d,e,f,g,h,i;
int sum=0,n;
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
&&100*a+10*b+c+100*d+10*e+f==100*g+10*h+i)
{
sum++;
}
n=sum/2;//有相同的情况
printf("%d种",n);
getchar();getchar();
return 0;
}
上面的代码也可以用一个数组来承接：
#include<stdio.h>
int main()
{
int array[10],i,total,book[10],sum,n;
total=0;
for(array[1]=1;array[1]<=9;array[1]++)
for(array[2]=1;array[2]<=9;array[2]++)
for(array[3]=1;array[3]<=9;array[3]++)
for(array[4]=1;array[4]<=9;array[4]++)
for(array[5]=1;array[5]<=9;array[5]++)
for(array[6]=1;array[6]<=9;array[6]++)
for(array[7]=1;array[7]<=9;array[7]++)
for(array[8]=1;array[8]<=9;array[8]++)
for(array[9]=1;array[9]<=9;array[9]++)
{
for(i=1;i<=9;i++)
{
book[i]=0;
}
for(i=1;i<=9;i++)
{
book[array[i]]=1;
}
sum=0;
for(i=1;i<=9;i++)
{
sum=sum+book[i];
}
if(sum==9&&array[1]*100+array[2]*10+array[3]+array[4]*100+array[5]*10+array[6]==array[7]*100+array[8]*10+array[9])
{
total++;
}
}
n=total/2;
printf("%d种",n);
getchar();getchar();
return 0;
}
书中有一个炸弹人的栗子：大概的意思是通过放置炸弹的方法来消灭敌人，炸弹只能放置在空地上，炸弹可以往上下左右的四个方向前进，遇到墙就会被挡住，遇到敌人会把敌人消灭，游戏里还有一种墙可以被炸开，但是炸开后无法穿透。然后现有一个超级炸弹，可以无限距离，然后我们的炸弹放到哪里才能炸掉最多的人呢？
作者给了一种想法，就是把墙用 # 表示，敌人使用G来表示，我们的空闲区域使用 . 来表示。然后我们使用一个二维的字符串数组来储存我们的地图，用两个变量来表示行和列的关系。
#include<stdio.h>
int main()
{
char array[21][21];
int m,n;
int x,y;
int sum;//可以消灭掉的敌人数量
scanf("%d %d",&n,&m);
int i,j;
int p,q,map;//定义变量不要定义到循环语句内，否则成为局部变量，应当定义为全局变量。
for(i=0;i<=n-1;i++)//读取n行字符
{
scanf("%s",array[i]);
}
for(i=0;i<=n-1;i++)
{
//int j;
for(j=0;j<=m-1;j++)
{
if(array[i][j]=='.')//平地放炸弹
{
//int sum;//可以消灭掉的敌人数量
sum=0;
//int x,y;
x=i;y=j;
//向上攻击
while(array[x][y]!='#')//不是墙的话
{
//再看有没有人
if(array[x][y]=='G')
{
sum++;
}
x--;//继续向上统计
}
x=i;y=j;
//向下攻击
while(array[x][y]!='#')
{
if(array[x][y]=='G')
{
sum++;
}
x++;
}
x=i;y=j;
//向右攻击
while(array[x][y]!='#')
{
if(array[x][y]=='G')
{
sum++;
}
y++;
}
x=i;y=j;
//向左攻击
while(array[x][y]!='#')
{
if(array[x][y]=='G')
{
sum++;
}
y--;
}
if(sum>map)//不断更新比较
{
map=sum;
p=i;
q=j;
}
}
}
}
printf("(%d , %d)处可以消灭%d个敌人\n",p,q,map);
getchar();getchar();
return 0;
}
书中作者还提到了一个叫做“火柴棍等式”的问题，按我个人理解，并查了一些资料，感觉书上写的稍有一些模糊，我们先看一下问题是什么：
然后他问：假如现在小哼手上有m根(m≤24）火柴棍，那么小哼究竟可以拼出多少个不同的方式呢？
最直白的方法，我们可以用枚举把每一位都举出来，建立之间的关系式，而作者也写到了，这样大概会运行1000多秒。所以作者举了一个栗子，就是枚举A和B，那么C就是A+B来表示。
#include<stdio.h>
int fun(int x)
{
int num=0;
int book[10]={6,2,5,5,4,5,6,3,7,6}; //用一个数组记录0到9数字所需的火柴棍数
while(x/10!=0) // x除以10不等于0的话，说明该数至少有两位
{
num=num+book[x%10];
x=x/10;
}
num=num+book[x]; //加上最高位的火柴棍数
return num;
}
int main()
{
int a,b,c,m,sum=0;
scanf("%d",&m); //火柴棍总个数
//书上是1111，但是这里写成11111会更好理解一些
for(a=0;a<=11111;a++) //开始枚举
{
for(b=0;b<=11111;b++)
{
c=a+b;
if(fun(a)+fun(b)+fun(c)==m-4)
{
printf("%d+%d=%d\n",a,b,c);
sum++;
}
}
}
printf("%d种方法",sum);
return 0;
}
对于“1111”的理解，可以参考此位博主的文章： 关于《啊哈！算法》第三章火柴棍等式“1111”问题的解析。
数的全排列
将1，2，3全排列，有多少种方式？
#include<stdio.h>
int main()
{
int a,b,c;
for(a=1;a<=3;a++)
for(b=1;b<=3;b++)
for(c=1;c<=3;c++)
if(a!=b&&a!=c&&b!=c)
printf("%d%d%d\n",a,b,c);
return 0;
}
当数据更大的时候，使用这种方法就不行了，之后的“搜索”会帮助我们。
算法打卡~