《啊哈算法》第三章--枚举与暴力

待我称王封你为后i 2024-03-17 21:13 78阅读 0赞

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一、坑爹的奥数
 *  二、炸弹人
 *  三、火柴棍等式
 *  四、全排列
 *  总结

--------------------

## 前言 ##

**前面我们学习了排序和栈 队列 链表，本节就学习暴力枚举的思想。**

--------------------

## 一、坑爹的奥数 ##

![在这里插入图片描述][5a6561c773954a078d96999873a8fd43.png]

![在这里插入图片描述][575e54c96f344b9e95a1c0b160b4ee19.png]

**题目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;
    }

## 二、炸弹人 ##

![在这里插入图片描述][b42db3b4812b49e8a3b23e6be9bacd92.png]

**还记得小霸王游戏机上的“炸弹人”吗，用放置炸弹的方法来消灭敌人炸弹的爆炸方向沿上下左右四个方向  
问在哪里放置炸弹可以消灭最多的敌人，已知两种墙，一种可以被炸掉  
由于现在只有一枚炸弹，所以墙都用"\#“表示（一枚炸弹可以炸掉这种墙，但也会被挡住）  
敌人用"G"表示，空地用”."表示，只有空地才能放置炸弹**

![在这里插入图片描述][078f1ed4c6d24d93873f395f27cb7f4b.png]

代码中的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）这个位置

![在这里插入图片描述][9b143e7e5a5248de821ab7a9b6f5cff7.png]  
**炸弹放在(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][AcWing_dfs]

--------------------

## 总结 ##

终于完结了，下一节讲解搜素知识.

[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/56d97b815e3840298d307182057bb2e3.png
[5a6561c773954a078d96999873a8fd43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/aed5116c962b47a0a6add82898d0964c.png
[575e54c96f344b9e95a1c0b160b4ee19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9c6b3b5ec993451999a33aa9012e354b.png
[b42db3b4812b49e8a3b23e6be9bacd92.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4a3b0d6e9ae24c08a1737e4eaecaaed6.png
[078f1ed4c6d24d93873f395f27cb7f4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b9d648a4c69044cf93e2b2913d86c769.png
[9b143e7e5a5248de821ab7a9b6f5cff7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a0ddf644eef647a59f3778fa007d30ad.png
[AcWing_dfs]: https://congfen214.blog.csdn.net/article/details/128431672