算法学习(3)-枚举

大家好，欢迎来到IT知识分享网。

目录

坑爹的奥数

炸弹人

火柴棍等式 

数的全排列

坑爹的奥数

        枚举算法又叫做穷举绊法， 光听这名字是不是就觉得很暴力很暴力呢。首先还是从一个
小学三年级的奥数题开始吧。
        小哼在数学课上遇到一道奥数题是这样的， 口3×6528=3口x8256, 在两个口内填入相同
的数字使得等式成立。你可能觉得这个太简单了！用3行代码就可以搞定。

for(i = l; i <= 9; i++) { if((i * l0 + 3) * 6528 == (30 + i) * 8256) { printf("%d", i); } }

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

        现在小哼又遇到一个稍微复杂一点的奥数题， 口口口＋口口口＝口口口，将数字1~9分别
填入9个口中， 每个数字只能使用一次使得等式成立． 例如173+286=459就是一个合理的组
合， 请问一共有多少种合理的组合呢？注意：173+286=459与286+173 =459是同一种组合！
        根据枚举思想我们只衙要枚举每一位上所有可能的数就好了。

#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[i] = 0; // 初始化 book 数组 // 如果某个数出现过就标记一下 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\n", total / 2); getchar(); getchar(); return 0; } 

        上面这段代码中， 为了方便标记哪些数出现过， 我将循环变量用一个一维数组a 来代替， 用book 数组来标记1~9 每个数是否出现过， 默认为O, 出现过的就设为1。然后我们只需要判断book 数组中有多少个1就可以了。如果恰好有9 个1则表示， 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() { char a[20][21]; //假设这里的地图大小不超过20*20 int i, j, sum, map = 0, p, q, x, y, n, m; //读入n和m, 表示有多少行字符，而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; } 

火柴棍等式 

#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 // 当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个不同的等式\n", sum); getchar(); getchar(); return 0; } 

数的全排列

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 e 循
环来枚举第3位。再用一个if语句来进行判断， 只有当a 、b和c互不相等的时候才能输出。
        如果求1234 的全排列呢？

for (a = -l; a <= 4; a++) { for (b = l; b <= 4; b++) { for (c = l; c <= 4; c++) { for (d = l; 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); } } } } } 

        以上便是暴力枚举的全部内容了。。。