第 3 章 枚举!很暴力

第 3 章 枚举!很暴力

第 1 节 坑爹的奥数

枚举算法又叫做穷举算法,光听这名字是不是就觉得很暴力很暴力呢。首先还是从一个小学三年级的奥数题开始吧。

小哼在数学课上遇到一道奥数题是这样的,□3×6528=3□×8256,在两个□内填入相同的数字使得等式成立。你可能觉得这个太简单了!用3行代码就可以搞定。

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

这就是最简单的枚举算法。枚举算法的基本思想就是“有序地去尝试每一种可能”。

现在小哼又遇到一个稍微复杂一点的奥数题,□□□+□□□=□□□,将数字1~9分别填入9个□中,每个数字只能使用一次使得等式成立。例如173+286=459就是一个合理的组合,请问一共有多少种合理的组合呢?注意:173+286=459 与 286+173=459 是同一种组合!根据枚举思想我们只需要枚举每一位上所有可能的数就好了。没错就是酱紫的O(∩_∩)O

#include <stdio.h>
int main()
{
  int a,b,c,d,e,f,g,h,i,total=0;
  for(a=1;a<=9;a++)//第1个数的百位
  for(b=1;b<=9;b++)//第1个数的十位
  for(c=1;c<=9;c++)//第1个数的个位
  for(d=1;d<=9;d++)//第2个数的百位
  for(e=1;e<=9;e++)//第2个数的十位
  for(f=1;f<=9;f++)//第2个数的个位
  for(g=1;g<=9;g++)//第3个数的百位
  for(h=1;h<=9;h++)//第3个数的十位
  for(i=1;i<=9;i++)//第3个数的个位
  { //接下来要判断每一位上的数互不相等
    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);//请想一想为什么要除以2
  getchar();getchar();
  return 0;
}

注意因为173+286=459 与 286+173=459 是同一种组合,因此我们在输出的时候需要将total除以2。

我猜你刚刚看到这段代码一定有想骂人的冲动。如果以后都这样写代码那真是太变态了。特别是判断a、b、c、d、e、f、g、h、i这九个变量互不相等的部分真的是太坑人了。还有更好的方法来实现吗?当然!那就是我们第一章就学过的标记法!用一个book数组来解决互不相等的问题。请看下面这段代码。

#include <stdio.h>
int main()
{
    int a[10],i,total=0,book[10],sum;
    //这里用a[1]~a[9]来代替刚才的a,b,c,d,e,f,g,h,i
    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数组
                    book[i]=0;
                for(i=1;i<=9;i++) //如果某个数出现过就标记一下
                    book[a[i]]=1;
                //统计共出现了多少个不同的数
                sum=0;
                for(i=1;i<=9;i++)
                sum+=book[i];
                //如果正好出现了9个不同的数,并且满足等式条件,则输出
                if( sum == 9 && a[1]*100 + a[2]*10 + a[3] + a[4]*100+a[5]*10
                    + a[6] == a[7]*100 + a[8]*10 + a[9])
                {
                 total++;
                 printf("%d%d%d+%d%d%d=%d%d%d\n", 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;
}

上面这段代码中,为了方便标记哪些数出现过,我将循环变量a、b、c、d、e、f、g、h、i用一个一维数组a来代替,用book数组来标记1~9每个数是否出现过,默认为0,出现过的就设为1。然后我们只需要判断book数组中有多少个1就可以了。如果恰好有9个1则表示,1~9每个数都有且只出现过一次。你可能会说,这还是很坑人啊,有没有更好的方法呢?不要着急,我们将在第4章彻底地解决这个问题。现在还是先请看下一节——炸弹人的策略。

第 2 节 炸弹人

小哼最近爱上了“炸弹人”游戏。你还记得在小霸王游戏机上的炸弹人吗?用放置炸弹的方法来消灭敌人。须将画面上的敌人全部消灭后,并找到隐藏在墙里的暗门才能过关。

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

{%}

我们先将这个地图模型化。墙用 # 表示。这里有两种墙,一种是可以被炸掉的,另外一种是不能被炸掉的。但是由于现在只有一枚炸弹,所以都用 # 表示,炸弹是不能穿墙的。敌人用 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#
#############

首先我们需要用一个二维字符数组来存储这个地图,至于将炸弹放置在哪一个点可以消灭的敌人最多,则需要一个个地来尝试。炸弹的爆炸方向是沿上下左右四个方向,因此我们在对每个点进行枚举的时候,需要沿着上下左右四个方向分别统计可以消灭敌人的数目。最终输出可以消灭敌人最多的那个点。请注意这里是从0行0列开始计算的。

请注意!本书中所说的坐标(x,y)指的就是第x行第y列,并不是数学中二维坐标系x轴y轴的坐标,这一点需要特别注意,不然你会被绕晕的。请记住(x,y)就是指第x行第y列哦。

如何分别统计上下左右四个方向上可以消灭的敌人数呢?只要搞清楚一个方向,其他的方向都是一样的,这里就以向下统计为例。向下就是y不变,x每次增加1,直到遇到墙为止。

//向下统计可以消灭的敌人数
while(a[x][y]!='#')
{
    if(a[x][y]=='G')
        sum++;  //如果可以消灭一个敌人就sum++
    x++; //x++的作用是继续向下
}

向另外几个方向进行统计的坐标变化如下。

{%}

接下来只需要统计在每一个空地上放置炸弹可以消灭的敌人总数(上下左右四个方向上可以消灭的敌人数之和)。最终输出消灭敌人数最多的那个空地的坐标即可,完整代码如下。

#include <stdio.h>
int main()
{
    char a[20][21]; //假设这里的地图大小不超过20*20
    int i,j,sum,map=0,p,q,x,y,n,m;
    //读入n和m,n表示有多少行字符,m表示每行有多少列
    scanf("%d %d",&n,&m);

    //读入n行字符
    for(i=0;i<=n-1;i++)
         scanf("%s",a[i]);

    //用两重循环枚举地图中的每一点
    for(i=0;i<=n-1;i++)
    {
        for(j=0;j<=m-1;j++)
        {
            //首先判断这个点是不是平地,是平地才可以被放置炸弹
            if(a[i][j]=='.')
            {
                sum=0;//sum用来计数(可以消灭的敌人数),所以需要初始化为0
                //将当前坐标i,j复制到两个新变量x,y中,以便向上下左右四个方向分别统计可以消灭的敌人数
                //向上统计可以消灭的敌人数
                x=i; y=j;
                while(a[x][y]!='#')//判断是不是墙,如果不是墙就继续
                {
                    //如果当前点是敌人,则进行计数
                    if(a[x][y]=='G')
                        sum++;
                    //x--的作用是继续向上统计
                    x--;
                }

                //向下统计可以消灭的敌人数
                x=i; y=j;
                while(a[x][y]!='#')
                {
                    if(a[x][y]=='G')
                        sum++;
                    //x++的作用是继续向下统计
                    x++;
                }

                //向左统计可以消灭的敌人数
                x=i; y=j;
                while(a[x][y]!='#')
                {
                    if(a[x][y]=='G')
                        sum++;
                    //y--的作用是继续向左统计
                    y--;
                }

                //向右统计可以消灭的敌人数
                x=i; y=j;
                while(a[x][y]!='#')
                {
                    if(a[x][y]=='G')
                        sum++;
                    //y++的作用是继续向右统计
                    y++;
                }

                //更新map的值
                if(sum>map)
                {
                    //如果当前点所能消灭的敌人总数大于map,则更新map
                    map=sum;
                    //并用p和q记录当前点的坐标
                    p=i;
                    q=j;
                }
            }
        }
    }

    printf("将炸弹放置在(%d,%d),最多可以消灭%d个敌人\n",p,q,map);
    getchar();getchar();
    return 0;
}

可以输入以下数据进行验证。第一行两个整数为n~m,分别表示迷宫的行和列,接下来的nm列为地图。

13 13
#############
#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#
#############

运行结果是:

将炸弹放置在(9,9)处,最多可以消灭8个敌人

喜欢思考的同学会发现这个算法有个问题。比如我们将地图(6,11)的墙改为平地,小人默认站在(3,3)这个位置,如右下图。

根据我们之前的算法,应该将炸弹放置在(1,11)处,最多可以消灭11个敌人。其实小人根本无法走到(1,11)处。所以正确的答案应该是将炸弹放在(7,11)处,最多可以消灭10个敌人。那如何解决这种问题呢?不要着急,我们将在第4章的第4节再来讨论。

第 3 节 火柴棍等式

闲来无聊的小哼,又拿出了火柴棍,不知道在摆弄什么……

现在小哼有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、4+0=4、7+2=9、10+1=11和11+0=11。

注意:

  1. 加号与等号各自需要两根火柴棍。
  2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C都大于0)。
  3. 所有根火柴棍必须全部用上。

假如现在小哼手上有m根(m\leqslant24)火柴棍,那么小哼究竟可以拼出多少个不同的形如A+B=C的等式呢?(本题根据NOIP2008提高组第二题改编。)

你有没有想到什么好方法?忘记说了,规定的时限是1秒。此刻,你可以先尝试实现一下。一定要好好思考后再往下看,看看你的想法和我是否一样。

既然是要找出形如A+B=C这样的等式,那最简单的办法就是分别枚举A、B、C啦。接下来的问题就是:A、B、C的枚举范围是什么呢?我们只需要在0~1111之间枚举就可以了。为什么呢?因为题目中最多只有24根火柴棍即m\leqslant24。除去“+”和“=”占用的4根火柴棍,那么最多剩下20根火柴棍。而0~9这10个数字中,数字1需要用到的火柴棍最少,只需要2根火柴棍。而20根火柴棍最多能组成10个1。因此A+B=C这个等式中A、B、C中的任意一个数都不能超过1111。

接下来就简单了,我们只需要分别来枚举A、B、C,范围都是0~1111。A所使用的火柴棍的根数,加上B所使用的火柴棍的根数,再加上C所使用的火柴棍的根数,如果恰好等于m-4的话,则成功地找出了一组解。这个算法的时间复杂度是O(N^3)\approx1112^3,这个时间复杂度很高,大约需要1000多秒才能算出解。是否可以将复杂度降到O(N^2)呢?当然可以。其实我们这里只需要枚举A和B就可以了,C可以通过A+B算出来。所以在采用暴力枚举的时候也需要仔细分析问题,我们只是将枚举C改为通过A+B来算出C,就将O(N^3)的算法优化到了O(N^2)

#include <stdio.h>
int fun(int x)
{
    int num=0;//用来计数的变量,一定要记得初始化
    int f[10]={6,2,5,5,4,5,6,3,7,6};//用一个数组来记录0~9每个数字需要用多少根火柴棍
    while(x/10!=0)//如果x/10的商不等于0的话,说明这个数至少有两位
    {
        //获得x的末尾数字并将此数所需要用到的火柴棍根数累加到num中
        num += f[x%10];
        x = x/10; //去掉x的末尾数字,例如x的值为123则现在x的值为12
    }
    //最后加上此时x所需用到的火柴棍的根数(此时x一定是一位数)
    num += f[x];
    return num;//返回需要火柴棍的总根数

}
int main()
{
    int a,b,c,m,i,sum=0;//sum是用来计数的,因此一定要初始化为0
    scanf("%d",&m);//读入火柴棍的个数

    //开始枚举a和b
    for(a=0;a<=1111;a++)
    {
        for(b=0;b<=1111;b++)
        {
            c=a+b; //计算出c
            //fun是我们自己写的子函数,用来计算一个数所需要用火柴棍的总数
            //当a使用的火柴棍根数 + b使用的火柴棍的根数 + c使用的火柴棍的根数之和恰好等于m-4时,则成功地找出了一组解
            if(fun(a)+fun(b)+fun(c)==m-4)
            {
                printf("%d+%d=%d\n",a,b,c);
                sum++;
            }
        }
    }
    printf("一共可以拼出%d个不同的等式",sum);
    getchar();getchar();
    return 0;
}

可以输入以下数据进行验证。

18

运行结果是:

0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11

一共可以拼出9个不同的等式。

第 4 节 数的全排列

刚刚研究完火柴棍,小哼又在研究一种特殊的排列——全排列。

123的全排列是123、132、213、231、312、321。1234的全排列是1234、1243、1324、1342、1423、1432、2134、2143、2314、2341、2413、2431、3124、3142、3214、3241、3412、3421、4123、4132、4213、4231、4312、4321。小哼现在需要写出123456789的全排列,对,一定要在吃饭之前写出来才行。你能写个程序来帮助小哼吗?

首先还是求123的全排列吧。很简单,三重循环嵌套就可以搞定,代码如下。

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);

上面的代码中,我们用for a循环来枚举第1位,用for b循环来枚举第2位,用for c循环来枚举第3位。再用一个if语句来进行判断,只有当a、b和c互不相等的时候才能输出。

如果求1234的全排列呢?你可能会说那还不简单,看我的。

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

没错,123和1234的全排列尚算简单,但是求123456789的全排列这样写就比较麻烦了。OK,现在终极问题来了:输入一个指定点的数n,输出1\sim n的全排列,又该如何呢?例如:输入3时输出123的全排列,输入4时输出1234的全排列……输入9时输出123456789的全排列。怎么样,亲爱的赶快动起来吧,看看你能否完成这个挑战。

代码编写得如何?如果你还没有动手,我还是建议你去尝试一下,肯定是可以做出来的,只是非常繁琐。那有没有方便一点的办法呢?请看下一章——万能的搜索。

目录