关于暴力枚举，你应该知道这些

这里是关于蓝桥杯算法类型的讲解专栏，针对一些算法如枚举算法，递归算法，动态规划算法等，通过图解的方式来讲解。欢迎同学围观，该文章将会首发于公众号：元气算法。 欢迎大家关注公众号，获取最新的文章以及相关备考资料。

前言

说到蓝桥杯，大家可能会说的就是暴力杯，通过过往的一些题目可以发现历年前面几题都是通过枚举找出最佳答案，哪怕是在最后几题也可以用暴力枚举跑出一些答案，得到几分。可谓是得暴力者得天下，下面我们就来讲讲暴力枚举。下图是本文的提纲。

枚举定义

最开始接触算法的时候，大家练习的基础算法都是有关于枚举算法的，比如打印出9 * 9的乘法表，求水仙花数，求素数等等，像这一类的题目就是在一定的范围内寻找满足条件的答案。 枚举算法的核心思想就是：枚举所有的可能

案例引入

题目描述

输出所有的“水仙花数”，所谓的“水仙花数”是指一个三位数其各位数字的立方和等于该数本身，例如153是“水仙花数”，因为：153 = 1 * 1 * 1 + 5 * 5 * 5 + 3 * 3 * 3。

题目分析

第一步：我们要确定的是这里面我们要确定的循环变量是什么，这里很容易想到变量为 这个三位数 ，这一步确定了我们的这个变量了。 第二步：确定我们变量的范围，只有确定好范围后，才知道从哪些数字中找的，我们可以知道这个数是整数，其次它是一个三位数 第三步：在已经知道从哪找的情况下，就是一个个遍历，进行判断了。这里我们就要将三位数拆开，依次三次方，然后相加，最后进行判断就可以了。

题目代码

#include<iostream>
using namespace std;
//判断条件
bool check(int num)
{
	int a = num%10;
	int b = num/10%10;
	int c = num/100;
	return a*a*a + b*b*b + c*c*c == num;
} 
int main()
{
    //确定范围
	for(int i = 100; i <= 999; i++)
	{
		if(check(i))
		{
			cout << i <<ends;
		}
	}
	return 0;
} 

枚举模板

按照上面我们分析的来一共3步，这里我总结为3W:

• Who:表示几个循环变量，有几个循环变量就有几重循环
• Where:表示变量范围。
• How:表示如何进行操作、筛选。 对循环变量的操作和判断是该模板的重点

//简单版本

//how:筛选满足的条件
bool check(*arg)
{
    
}
int main(){
    /*who：确定几个变量就有几个循环*/
    /*where:判断变量的范围，模板中的 a,b表示范围*/
    for(int i = a; i < b; i++)
    {
        for(int j = a; j < b; j++)
        {
            ...
            for(int z = a; z < b; z++)
            {
                //how1.对变量进行操作。
                
                //how2.对变量进行判断
                if(check(*args))
                {
                    //do
                }
            }
        }
    }
}

元气训练

题目1：啤酒和饮料

啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。

题目分析：

• who:此题中循环变量为 啤酒个数 和 饮料个数
• where:对于啤酒的个数最小为1，最大为82.3/2.3 饮料的最小个数为1，最大个数为82.3/1.9
• how:判断有两个条件：1.买的啤酒比饮料的数量少,2.所花费用一共82.3。
• 对于如何判断两个浮点型相等用fabs函数

题目解答

#include<iostream>
#include<math.h>
using namespace std;
bool check(int i,int j)
{
	//判断价格是否等于82.3 
	return (fabs(i*2.3+j*1.9 - 82.3) <= 1e-5); 
} 
int main()
{
	//啤酒 
	for(int i = 0; i < 82.3/2.3; i++)
	{
		//饮料 
		for(int j = i+1;j < 82.3/1.9; j++)
		{
			if(check(i,j))
			{
				cout << i <<ends << j <<endl;
			}
		}
	}
	return 0;
}

题目2：跑步训练

小明要做一个跑步训练。 初始时，小明充满体力，体力值计为 10000 。如果小明跑步，每分钟损耗 600 的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达 0 ，他就停止锻炼。 请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。

题目分析

• who：此题中 体力 是循环变量，所以只有一重循环
• where:题中 体力值 的变化的，最开始的值是1000，当体力为零时候循环结束。在这里我们不明确
• how:判断当体力值是零的时候，我们可以输出时间，同时跳出循环

题目解答

#include<iostream>

using namespace std;

int main()
{
	int n = 10000;//体力最开始的值
	int run = 600/60;//每秒的消耗 
	int time = 0;//时间
	//who:循环变量
	while(n)
	{
	    //how2:判断
	    //当剩余体力不满足再跑一次时候,压榨最后一点体力，然后跳出循环
	    if(n-600 < 0)
	    {
	        time += n/run;
	        break; 
	    }
	    
	    //how1:对体力进行操作
	    //跑步
	    n -= 600;
	    n += 300;
	    //加上两分钟
	    time += 120;
	}
	cout << time << endl;
	return 0;
} 

出题风格

对于暴力枚举基础应用就是以上，而蓝桥杯的风格在不断变化，需要大家不断地练习，总的来说就是熟能生巧。总结历年的出题风格发现，发现蓝桥出题人主要在三个方面来考察枚举算法。

1.模拟题 这个主要考察基础知识点，像一些二进制转十进制、跑步训练之类的，总的来说就是你根据题目要求模拟，对变量进行操作，从而得出结果 2. 数学题 考察你的基础数学能力，放心这个对于数学的能力要求不是很高，高中水平就可以应对。 3. 日期题 这类题目应该是套路问题，要会处理好日期中的年月日关系，该类型题目要做做两三道，外加细心。excel大佬可以跳过。

学习建议

1. 编程基础入门100题：如果觉得自己的基础学的不是很扎实，可以把其中的100题都过一下，对自身的实力提升还是很大的，针对于小白同学。链接：编程入门100题
2. 欧拉计划：专门来培养学生的数学思维，学会用数学的方法来解题。链接：欧拉计划
3. 蓝桥杯真题：上面几种搞完就可以上手真题。链接：蓝桥杯真题

学习资源

收集了一些网上的一些学习资源，由于链接易失效，请有需要的同学关注公众号自提即可，资源收集于网上，请勿用于商业。