第一节

第一节主要是求解如下数学问题

暴力穷举判断

要满足九个数字都只能用一次,最容易想到的判断方法是:

总体代码:

标记法穷举判断

我们可以想到第一章学的桶排序可以用来标记,在第二章纸牌游戏中我们也利用它来标记已有的数。

总体思路:设a[9],a[0],a[1],a[2]为第一个 三位数的, a[3],a[4],a[5]为第二个三位数, a[6],a[7],a[8]为第三个三位数 ,用book[i]标记里面的数,出现过的为1,没出现过的为0,这样只要book[i]之和为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]时,即满足条件

  • 用a[9]来表示这9个数,循环条件:
int a[9];
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]++)
  • 初始化九个数的”桶“,以及a[9]
int book[10]
for (int i = 0; i < 10; i++) 
    book[i] = 0;
  • 出现过的数标记
for(int i=0;i<9;i++)
    book[a[i]] = 1;   //这样本次外循环a[1]到a[9]全都标记了
  • 统计有几个数标记过
int sum = 0;
for(int i=0;i<10;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])
    printf("%d%d%d+%d%d%d=%d%d%d",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);

总代码

#include <stdio.h>

int main() {
    int a[9];int book[10];
    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 < 10; i++)
                                            book[i] = 0;
                                        for(int i=0;i<9;i++)
                                            book[a[i]] = 1;
                                        int sum = 0;
                                        for(int i=0;i<10;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])
                                           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]);
                                    }
}

第二节.炸弹人游戏

规则如下:炸弹成十字爆炸,且爆炸距离无限,这两种墙炸弹都不能穿过,(如图所示),只有一个炸弹,求放在哪个位置能消灭最多的敌人。

思路:将地图用二位数组存储(如图所示),敌人用“G”表示,不能穿过的墙用“#”表示,可以放置炸弹的空地用“.”表示,遍历二位数组的所有位置,每次循环时,都分别进行向左(x--),向右(x++) ,向下(y++),向上(y--)循环的操作,遇到G时杀敌数+1,直到碰到“#”时停止。

  • 假设地图长和宽均为13,用a[13][13]二维数组来存储地图,注意,存的是字符,要用char类型
char a[13][13] = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
                  {'#', 'G', 'G', '.', 'G', 'G', 'G', '#', 'G', 'G', 'G', '.', '#'},
                  {'#', '#', '#', '.', '#', 'G', '#', 'G', '#', 'G', '#', 'G', '#'},
                  {'#', '.', '.', '.', '.', '.', '.', '.', '#', '.', '.', 'G', '#'},
                  {'#', 'G', '#', '.', '#', '#', '#', '.', '#', 'G', '#', 'G', '#'},
                  {'#', 'G', 'G', '.', 'G', 'G', 'G', '.', '#', '.', '#', '#', '#'},
                  {'#', 'G', '#', '.', '#', 'G', '#', '.', '#', '.', '#', '#', '#'},
                  {'#', '#', 'G', '.', '.', '.', 'G', '.', '.', '.', '.', '.', '#'},
                  {'#', 'G', '#', '.', '#', 'G', '#', '#', '#', '.', '#', 'G', '#'},
                  {'#', '.', '.', '.', 'G', '#', 'G', 'G', 'G', '.', 'G', 'G', '#'},
                  {'#', 'G', '#', '.', '#', 'G', '#', 'G', '#', '.', '#', 'G', '#'},
                  {'#', 'G', 'G', '.', 'G', 'G', 'G', '#', 'G', '.', 'G', 'G', '#'},
                  {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};
  • 遍历所有为‘.’的可以放炸弹的位置
for (int i = 0; i < 13; i++)
    for (int j = 0; j < 13; j++) 
        if(a[i][j] == '.'){
            printf("(%d,%d)处可以放炸弹。",i,j);
        }
  • 在每次遍历循环时,该位置分别向四个方向遍历,遇到G时杀敌数+1,遇到#时终止循环
//统计往四个方向的总杀敌数
int kill = 0;       //记录杀敌数
int x = i, y = j;
while (a[x][y] != '#') {      //向左方向
    if (a[x][y] == 'G')
        kill++;
    x--;
}
x = i, y = j;
while (a[x][y] != '#') {      //向右方向
    if (a[x][y] == 'G')
        kill++;
    x++;
}
x = i, y = j;
while (a[x][y] != '#') {      //向上方向
    if (a[x][y] == 'G')
        kill++;
    y--;
}
x = i, y = j;
while (a[x][y] != '#') {      //向下方向
    if (a[x][y] == 'G')
        kill++;
    y++;
}
if (kill > max_kill) {             //记录该位置是否是最大杀敌数
    max_kill = kill;
    max_x = i;
    max_y = j;
}
  • 每次循环后看杀敌数是不是最多,如果最多,则记录其位置和总杀敌数。
if (kill > max_kill) {             //记录该位置是否是最大杀敌数
    max_kill = kill;
    max_x = i;
    max_y = j;
}

总代码:

#include <stdio.h>

int main() {
    char a[13][13] = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
                      {'#', 'G', 'G', '.', 'G', 'G', 'G', '#', 'G', 'G', 'G', '.', '#'},
                      {'#', '#', '#', '.', '#', 'G', '#', 'G', '#', 'G', '#', 'G', '#'},
                      {'#', '.', '.', '.', '.', '.', '.', '.', '#', '.', '.', 'G', '#'},
                      {'#', 'G', '#', '.', '#', '#', '#', '.', '#', 'G', '#', 'G', '#'},
                      {'#', 'G', 'G', '.', 'G', 'G', 'G', '.', '#', '.', '#', '#', '#'},
                      {'#', 'G', '#', '.', '#', 'G', '#', '.', '#', '.', '#', '#', '#'},
                      {'#', '#', 'G', '.', '.', '.', 'G', '.', '.', '.', '.', '.', '#'},
                      {'#', 'G', '#', '.', '#', 'G', '#', '#', '#', '.', '#', 'G', '#'},
                      {'#', '.', '.', '.', 'G', '#', 'G', 'G', 'G', '.', 'G', 'G', '#'},
                      {'#', 'G', '#', '.', '#', 'G', '#', 'G', '#', '.', '#', 'G', '#'},
                      {'#', 'G', 'G', '.', 'G', 'G', 'G', '#', 'G', '.', 'G', 'G', '#'},
                      {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};
    //遍历所有为“.”的可以放置炸弹的位置
    int max_x = 0, max_y = 0, max_kill = 0;        //用来记录杀敌最多的位置及杀敌数量
    for (int i = 0; i < 13; i++)
        for (int j = 0; j < 13; j++)
            if (a[i][j] == '.') {
                //统计往四个方向的总杀敌数
                int kill = 0;       //记录杀敌数
                int x = i, y = j;
                while (a[x][y] != '#') {      //向左方向
                    if (a[x][y] == 'G')
                        kill++;
                    x--;
                }
                x = i, y = j;
                while (a[x][y] != '#') {      //向右方向
                    if (a[x][y] == 'G')
                        kill++;
                    x++;
                }
                x = i, y = j;
                while (a[x][y] != '#') {      //向上方向
                    if (a[x][y] == 'G')
                        kill++;
                    y--;
                }
                x = i, y = j;
                while (a[x][y] != '#') {      //向下方向
                    if (a[x][y] == 'G')
                        kill++;
                    y++;
                }
                if (kill > max_kill) {             //记录该位置是否是最大杀敌数
                    max_kill = kill;
                    max_x = i;
                    max_y = j;
                }
            }
    printf("在(%d,%d)处杀敌最多,一共消灭%d个敌人", max_x, max_y, max_kill);
}

运行结果:

第三节.火柴棍等式

规则:用火柴棍表示数字,(如下图),拼凑出A+B=C,使用≤24根火柴(去掉加号和等号用去的4根火柴,最多剩20根火柴),可以有多少种不同组合。

注:A、B、C不一定是一位数。

分析:用数组f[10]={6,2,5,5,4,5,6,3,7,6}来存每个数字所需的火柴数。定义函数fun()来计算并返回每个数需要用到多少根火柴,两重for循环来遍历所有的A和B的数,循环内部:C=A+B,如果满足fun(A)+fun(B)=fun(C),则计数器count ++。

  • 因为三个数最多用20根火柴,使用火柴最少的数是1,因此20根火柴构成最大的数是1111111111,因此A、B肯定不会超过11111。
  • 定义fun()函数计算并返回每个数需要多少根火柴。采用循环的方法,循环条件是x有多于一位数(x/10 != 0),则num加上最后一位数对应的火柴数,并删除最后一位数
int fun(int x){
    int num = 0;         //用于记总火柴数
    int f[10] = {6,2,5,5,4,5,6,3,7,6};
    while(x/10 != 0){    //多于一位数
        num += f[x%10];  //num加上x最后一位数对应火柴数
        x=x/10;          //删除x最后一位数
    }
    num += f[x];        //此时x一定是个位数
    return num;
}
  • 两重for循环来遍历所有的A和B的数,循环内部:C=A+B,如果满足fun(A)+fun(B)=fun(C),则计数器count ++。
int count = 0;
for(int a=0;a<1111;a++)
    for(int b=0;b<1111;b++) {
        int c = a + b;
        if(fun(a)+ fun(b)+ fun(c)<=20) {
            count++;
        }
    }

总代码:

#include <stdio.h>
int fun(int x){
    int num = 0;         //用于记总火柴数
    int f[10] = {6,2,5,5,4,5,6,3,7,6};
    while(x/10 != 0){    //多于一位数
        num += f[x%10];  //num加上x最后一位数对应火柴数
        x=x/10;          //删除x最后一位数
    }
    num += f[x];        //此时x一定是个位数
    return num;
}

int main(){
    int count = 0;
    for(int a=0;a<1111;a++)
        for(int b=0;b<1111;b++) {
            int c = a + b;
            if(fun(a)+ fun(b)+ fun(c)<=20) {
                printf("%d + %d = %d \n",a,b,c);
                count++;
            }
        }
    printf("总共有%d种组合。",count/2);  //因为1+2=3和2+1=3是同一种组合,所以sum要除以2
}

运行结果:

第四节.全排列

这一节只是对全排列做了简单的介绍,具体的方法在下一章。