第三章, 枚举 (暴力破解)
枚举, 说白了就是, 穷举每一种可能.
对于我们人来说, 这个太难了.
但是对于计算机来说这种工作再适合不过了.
第一个🌰:
小试牛刀之解出以下等式:
x3 * 6528 = 3x * 8256
// 枚举, 尝试每种可能性
for (i = 1; i <= 9; i++) {
if ((i * 10 +3 ) * 6528 == (3*10 + i) * 8256) {
printf("%d", i);
}
}
第二个🌰:
算出以下等式:
xxx(数字1)+xxx(数字2)=xxx;
要求:
1.每一位的数字范围在[1, 9], 其中每个数字不能重复,
2.xxx(数字1)+xxx(数字2)=xxx; 或者 xxx(数字2)+xxx(数字1)=xxx; 这算是一种 , 所以算出总数后需要 除以 2.
这道题, 使用标记法. 定义book数组来标记, 哪些个数字已经使用过了.
参考代码
#include <stdio.h>
int main()
{
int a[10];
int book[10]; // 标记你哪些
int i
int sum; // 记录
int total = 0; // 记录总数
// 初始化数组
for(i = 1; i <= 9; i++)
{
a[i] = i;
}
sum = 1;
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]++) {
// 初始化book数组
for (i = 1; i <= 9; i++)
book[i] = 0;
// 如果某个数出现过就标记以下
for (i =1; i <= 9; i++)
book[a[i]] = 1;
// 统计共出现 了多少个不同的数
sum = 0;
for (i = 1; i <= 9; i++)
sum += book[i];
// 如果同时满足两个条件:
// 1. 出现9个不同的数
// 2. 满足等式要求
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])) {
printf("%d %d %d %d %d %d %d %d %d",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
total++; // 统计个数
}
}
}
}
}
}
}
}
}
}
printf("total: %d\n", total/2); // 因为加法的交换律, a+b=c 等价于 b+a=c, 需要除以2
getchar();
return 0;
}
第三个🌰:
炸弹人游戏
放置一颗威力巨大的炸弹, 尽可能多的消灭敌人.
模拟地图如下:
地图.png
在地图上有三种地图类型,
1.空白地, 使用 ‘ . ’
2.墙, 使用 ‘#’
3.敌人, 使用 ‘G’
核心代码:
// 1.首先判断地图上是否是空地, 是空地才能安放炸弹
if (a[x][y] == '.') {
// 2.然后在四个方向上, 统计消灭敌人数量
// 向下移动, 统计消灭敌人数量
while(a[x][y] != '#')
{
if (a[x][y] == 'G') {
sum++;
}
x++; //向下移动
}
// 向上移动, 统计消灭敌人数量
while(a[x][y] != '#')
{
if (a[x][y] == 'G') {
sum++;
}
x--; //向上移动
}
// 向左移动, 统计消灭敌人数量
while(a[x][y] != '#')
{
if (a[x][y] == 'G') {
sum++;
}
y--; //向上移动
}
// 向右边移动, 统计消灭敌人数量
while(a[x][y] != '#')
{
if (a[x][y] == 'G') {
sum++;
}
y++; //向上移动
}
}
完整代码:
#include <stdio.h>
int main()
{
char map[20][21]; // 设置地图数组大小
int sum, q, p, i, j, x, y, n, m, max = 0;
scanf("%d %d", &n, &m); // 输入地图大小, 20 * 20
// 输入地图数据
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++)
{
x = i; y = j;
if (a[x][y] == '.') // 判断是否是空地
{
sum = 0; // 重新计数
// 向下统计
while (a[x][y] != '#')
{
if (a[x][y] == 'G')
{
sum++;
}
x++;
}
// 向上统计
while (a[x][y] != '#')
{
if (a[x][y] == 'G')
{
sum++;
}
x--;
}
// 向左统计
while (a[x][y] != '#')
{
if (a[x][y] == 'G')
{
sum++;
}
y++;
}
// 向右统计
while (a[x][y] != '#')
{
if (a[x][y] == 'G')
{
sum++;
}
x++;
}
// 四个方向统计结束后, 进行判断是否是最大消灭敌人的位置
if (sum > max)
{
max = sum;
p = x;
q = y;
}
}
}
}
printf("炸弹放置在坐标(%d, %d), 最大消灭敌人个数 %d\n", p, q, max);
getchar();
return 0;
}
第四个🌰:
火柴棍等式
现在有n (n <= 24)根火柴棍, 希望能拼出等式: A + B = C的等式.
其中A, B, C都是用火柴棍拼出来的整数(非零, 则最高位不能是0),
数组0~9, 拼法如下:
火柴棍拼法.png
定义数组如下:
int f[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 用来表示每个数所需要的火柴棍的数量
关键点:
- 符号+, = 需要4跟火柴棍. 现在一共有24, 这样话, 减去4根, 还剩下20根.
- 在0~9, 10个数中, 需要最少火柴棍的就是数字 1 , 只需要2根. 所以, 最大能摆出的数字就是 11111
- A, B, C三个数, 只需要算出A, B,就能算出C, 这样就能算出所需的火柴棍数量.
参考代码如下:
// 算出x需要多少根火柴棍的方法
int func(int x)
{
int i = 0, sum = 0;
int f[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
while(x != 0)
{
sum += f[x%10];
x = x/10;
}
return sum;
}
int main()
{
int a, b, c;
int m;
int sum =0; // 统计等式的个数
scanf("%d", &m); // 输入火柴棍的个数
// 开始枚举a, b
for(a = 0; a <= 11111; a++)
{
for(b = 0; b <= 11111; b++)
{
c = a+b; // 通过a+b, 计算出c
if (f(c) + f(b) + f(a) == m-4) // 判断三个数字所用的火柴棍的总数是否等于m-4
{
printf("%d + %d = %d\n", a, b, c);
sum++;
}
}
}
printf("一共有 %d 不同的等式\n", sum);
getchar();
return 0;
}
第5五个🌰:
数的全排列
三个数, 1,2,3的全排列是:
123, 132, 213, 231, 312, 321, 六个数.
四个数, 五个数依次类推,
我们可以通过三个for循环来求的结果
参考代码
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);
}
}
}
}
