《啊哈算法》第三章--枚举 与 暴力
文章目录
- 前言
- 一、坑爹的奥数
- 二、炸弹人
- 三、火柴棍等式
- 四、全排列
- 总结
前言
前面我们学习了排序和栈 队列 链表，本节就学习暴力枚举的思想。
一、坑爹的奥数
题目1
□3 x 6528 = 3□ x 8256，在 □ 里填入相同数字使等式成立
代码如下
#include<iostream>using namespace std;int main(){for(int i=1;i<=9;++i){if((i*10+3)*6528 == (30+i)*8256)cout<<i<<endl;}return 0;}
样例
输出：4
题目2
□□□ + □□□ = □□□
将数字1 ~ 9分别填入 □ 种，每个数字只能使用一次使等式成立
比如173 + 286 = 459 与 286 + 173 = 459 为一种可能
解题思路
因为有9个空格需要填充，所以可以暴力使用9个for循环，用 a[i] 表示第 i 个格子地数字，通过book数组标记数字1 ~ 9是否出现过
如果满足每个数字只出现一次，且满足等式，total++，注意最后输出total / 2
同时，为避免book[i]累加，每次开始前都要置零
代码如下
#include<iostream>using namespace std;int a[10], book[10];int main(){int i,total = 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(a[9] = 1; a[9] <= 9; ++a[9])//9个格子，9个for循环{for(i = 1; i <= 9; ++i)book[i] = 0;//每次归零for(i = 1; i <= 9; ++i)book[a[i]] = 1; //标记是否出现int sum = 0; //统计不同数字个数for(i = 1; i<= 9; ++i)sum += book[i]; //这里不是book[a[i]]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++;cout<<a[1]<<a[2]<<a[3]<<"+"<<a[4]<<a[5]<<a[6]<<"="<<a[7]<<a[8]<<a[9]<<endl;}}cout<<total/2<<endl;return 0;}
二、炸弹人
还记得小霸王游戏机上的“炸弹人”吗，用放置炸弹的方法来消灭敌人炸弹的爆炸方向沿上下左右四个方向
问在哪里放置炸弹可以消灭最多的敌人，已知两种墙，一种可以被炸掉
由于现在只有一枚炸弹，所以墙都用”#“表示（一枚炸弹可以炸掉这种墙，但也会被挡住）
敌人用”G”表示，空地用”.”表示，只有空地才能放置炸弹
代码中的x, y表示第x行，第y列，且从第0行第0列开始计算
这里介绍一下走格子的表示方法：
向上 x–，向下 x++，向左 y–，向右 y++
代码如下
#include<iostream>using namespace std;int main(){char a[20][21];//存放地图int n=0,m=0;cin>>n>>m;int sum,i,j;int map=0,p=0,q=0;//读入n行字符for(int i=0;i<n;++i)cin>>a[i];//遍历地图for(i=0;i<n; ++i){for(j=0;j<m; ++j){//首先判断这个点是不是平地，是平地才可以放炸弹if(a[i][j]=='.'){sum=0;//sum用来计数，所以要反复初始化为0//将i，j分别放入到x与y当中以便于后续的向上下左右四个方向分别统计//可以消灭的敌人数//统计向上可以消灭的敌人数int x=i,y=j;while(a[x][y]!='#')//判断是不是墙，如果不是墙就继续{if(a[x][y]=='G') sum++;//是敌人就计数x--;//继续向上统计}//统计向下可以消灭的敌人数x=i,y=j;while(a[x][y]!='#'){if(a[x][y]=='G') sum++;//是敌人就计数x++;//继续向下统计}//统计向左可以消灭的敌人数x=i,y=j;while(a[x][y]!='#')//判断是不是墙，如果不是墙就继续{if(a[x][y]=='G') sum++;//是敌人就计数y--;//继续向左统计}//统计向右可以消灭的敌人数x=i,y=j;while(a[x][y]!='#')//判断是不是墙，如果不是墙就继续{if(a[x][y]=='G') sum++;//是敌人就计数y++;//继续向右统计}if(sum>map){map=sum;//保存最大值p=i;//保存坐标q=j;//保存坐标}}}}printf("将炸弹放在(%d, %d)处，最多可以消灭%d个敌人",p,q,map);return 0;}输入：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个敌人，怎么解决这个问题呢？
我会在《啊哈算法》第四章的博客解决这个问题
三、火柴棍等式
小哼有 n(n <= 24) 根火柴棍，希望拼出形如 A + B = C 的等式，等式种的A，B，C均是用火柴棍拼出的整数（若该数非0，则最高位不为0），数字 1 ~ 9 的拼法如下图所示
要求：
1，+ 与 = 各自需要两根火柴
2，如果 A != B，则 A + B = C 与 B + A = C 视为不同等式（A，B，C 都大于 0）
3，所有火柴棍都要用上
#include<iostream>using namespace std;int fun(int x) //写个判断火柴数的函数{int a[10] = {6,2,5,5,4,5,6,3,7,6}; //单个数字对应的火柴数int sum = 0; //火柴数while(x / 10 != 0){sum += a[x%10]; //敲重点x /= 10;}sum += a[x]; //此时x为个位数return sum;}int main(){int n, c, all = 0;cin>>n; //总的火柴数for(int i=0;i<=1111; ++i)for(int j=0;j<=1111; ++j){c=i+j; //"="右边的数if(fun(i)+fun(j)+fun(c)==n-4){cout<<i<<"+"<<j<<"="<<c<<endl;all++;}}cout<<"可以拼出"<<all<<"种不同等式"<<endl;return 0;}
四、全排列
DFS里面的经典问题，下一节详细讲解
也可以先看这个预习
AcWing算法学习—dfs
总结
终于完结了，下一节讲解搜素知识.
待我称王封你为后i
我就是我
还没有评论，来说两句吧...