目录

前言

 一、百钱买百鸡

二、百元兑钞

三、门牌号码（蓝桥杯真题）

 四、相乘（蓝桥杯真题）

五、卡片拼数字（蓝桥杯真题）

六、货物摆放（蓝桥杯真题）

七、最短路径（蓝桥杯真题）

---

前言

  循环有while,do-while,for三种形式，三者各自可以自己嵌套自己，也可以交叉嵌套。暴力破解法（穷举法）（枚举法），即用循环把该有的结果全部遍历出来，之后再用if语句做筛选,判断这个答案是不是我们需要的,此思想在蓝桥杯竞赛中相当重要。

解决此类题目的思路：

  首先我们应该确定穷举范围，不能多，不能少，要不然就容易漏掉一个。其次想应该用什么方式穷举，单层for循环或者嵌套,然后想if的判断条件。

  下面几道例题具体展现暴力的思想，每道题均采用问题描述，分析，代码实现和运行结果的形式呈现。

 一、百钱买百鸡

问题描述：

  我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题，该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？

  翻译过来，意思是公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？

分析：

  思路讲解：假设买的全为公鸡，则最能买到20只，即100/5=20，所以x<=20;同理若买的全为母鸡则100/3=33余1,y<=33；此处小心小鸡数目不是300，而应该是100，因为题目要求了要买100只鸡,所以z<=100; if语句满足三个条件：1、一百元 2、一百只鸡 3、小鸡数量是三的倍数。

代码实现：

#include<iostream>
using namespace std;

int main() {
	int x, y, z;              //分别代表公鸡，母鸡，小鸡的数量
	for (x = 0; x <= 20; x++) {
		for (y = 0; y <= 33; y++) {
			for(z=0;z<=100;z++)
			if (z % 3 == 0 && (5 * x + 3 * y + z / 3) == 100 && (x+y+z)==100) 
            //满足三个条件：1、一百元 2、一百只鸡3、小鸡数量是三的倍数
{   
				cout << "公鸡，母鸡，小鸡数：" << x << " " << y << " " << z << " " << endl;
			}
		}
	}
}

运行结果： 

二、百元兑钞

问题描述：

  一百元可以兑换多少张10元，5元，1元？有多少种兑换方法？要求每种情况都要包含10元，5元，1元。

分析：
  和第一道题思路一致，三重循环暴力破解，设置count值求解次数。

代码实现：

//百元兑钞问题
int main() {
	int a, b, c,count=0;
	for (a = 1; a < 10; a++) 
		for(b=1;b<20; b++)
			for (c = 1; c < 100; c++) 
				if (100 == a * 10 + b * 5 + c) {
					cout << "10元有：" << a << "张";
					cout << "5元有：" << b << "张";
					cout << "1元有：" << c << "张";
					cout << endl;
					count++;
					break;//提高效率，每次兑换方案成功后跳出最内层循环
				}
	cout << "共有" << count << "种兑换方法";
		return 0;
}

运行结果

三、门牌号码（蓝桥杯真题）

问题描述：

  小蓝要为一条街的住户制作门牌号。这条街一共有2020位住户,门牌号从1到2020编号。小蓝制作门牌的方法是先制作0到9这几个数字字符,最后根据需要将字符粘贴到门牌上,例如门牌1017需要依次粘贴字符1、0、1、7,即需要1个字符0,2个字符1,1个字符7。请问要制作所有的1到2020号门牌,总共需要多少个字符2?

分析：

  此题比较简单，问题简化为：1~2020总共有多少个2？用到求一个数各位数字的思想，即把当前这个数每一位都拆出来。

拆解一个数的各位代码

代码实现：

int main() {
	int count = 0;
	for (int i = 1; i <= 2020; i++) {
		int n = i;
		while (n != 0) {
			int t = n % 10;
			n /= 10;
			if (t == 2)
				count++;
		}
	}
	cout<<"0~2020共有" << count<<"个2";
	return 0;
}

运行结果： 

 

 四、相乘（蓝桥杯真题）

问题描述：

  小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以 1000000007 的余数，会得到不同的数。
  小蓝想知道，能不能在 1 至 1000000007 之间找到一个数，与 2021 相乘后 再除以 1000000007 后的余数为 999999999。
  如果存在，请在答案中提交这个数； 如果不存在，请在答案中提交 0。

分析：  

此题非常简单，分析省略。

代码实现：

int main() {
	unsigned long long i,n=1000000007,b=999999999;
	for(i=1;i<=n;i++)
		if (i * 2021 % n == b) {
			cout << i;
		}
}

运行结果：

 

 

五、卡片拼数字（蓝桥杯真题）

问题描述：

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。小蓝有很多数字卡片,每张卡片上都是数字0到9。小蓝准备用这些卡片来拼一些数,他想从1开始拼出正整数,每拼一个,就保存起来,卡片就不能用来拼其它数了。小蓝想知道自己能从1拼到多少。例如,当小蓝有30张卡片,其中0到9各3张,则小蓝可以拼出1到10,但是拼11时卡片1已经只有一张了,不够拼出11。现在小蓝手里有0到9的卡片各2021张,共20210张,请问小蓝可以从1拼到多少?

分析：

依旧用到上一题求一个数各位数字的思想，比较拆出来的各位数和剩余卡片数量，卡片数量不够说明拼不了这个数字，这时退出循环，最多拼到上一个数。

代码实现：

int main()
{
	int cards[10] = { 2021,2021,2021,2021,2021,2021,2021,2021,2021,2021 };
	//定义一个整数数组cards，包含了数字0到9的卡片数量，每个数字的卡片数量都是2021
	int num = 1;  //ans代表所要拼接的数字
	int temp = 0; //用另一个变量操作num
	int temp2 = 0; //拆出的各位数字
	while (1) //用一个无限循环
	{
		temp = num;
		while (temp != 0)
		//第一次写的时候忘记了这条语句，当temp=0时,对该数操作完毕
		{
			temp2 = temp % 10;
			cards[temp2]--; //对应的该卡片数量减一
			if (cards[temp2] == 0) //说明对应卡片用完
			{
				cout << num - 1 << endl; //即最大的拼接数字为上一个数字
				return 0; //循环终止
			}
			temp = temp / 10;
		}
		num++;
	}
	return 0;

运行结果：

六、货物摆放（蓝桥杯真题）

问题描述：

  小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆L、W、H 的货物，满足n = L × W × H。给定n，请问有多少种堆放货物的方案满足要求。
例如，当n = 4 时，有以下6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
请问，当n = 2021041820210418 （注意有16 位数字）时，总共有多少种方案？

分析：

 当n = 4 时，1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。通过这个例子，可以看出找出n的所有因子并求出所有的组合方式，存放到数组中，再使用三重循环遍历所有因子，找出所有因子用到求素数的思想。

代码实现：

#include<iostream>
#include<cmath>
using namespace std;
typedef unsigned long long A;
//typedef 是一个类型声明语句，它用于定义一个新的数据类型标识符，给一个已有的数据类型取别名。
//即unsigned long long ==A;
 A n = 2021041820210418;
A a[3000], cnt = 0; //存放因子
int main(void)
{
	//找出所有因子放进数组，素数思想
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			a[++cnt] = i;
			if (i * i != n) //简化寻找次数
				a[++cnt] = n / i;
		}
	}
	//循环
	A count = 0; //计数
	for (int l = 1; l <= cnt; l++)
		for (int w = 1; w <= cnt; w++)
			for (int h = 1; h <= cnt; h++)
				if (a[l] * a[w] * a[h] == n) 
					count++;

	cout << count;
	return 0;

}

运行结果： 

 

七、最短路径（蓝桥杯真题）

问题描述：

  小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由2021 个结点组成，依次编号1 至2021。对于两个不同的结点a, b，如果a 和b 的差的绝对值大于21，则两个结点之间没有边相连；如果a 和b 的差的绝对值小于等于21，则两个点之间有一条长度为a 和b 的最小公倍数的无向边相连。

  例如：结点1 和结点23 之间没有边相连；结点3 和结点24 之间有一条无向边，长度为24；结点15 和结点25 之间有一条无向边，长度为75。
  请计算，结点1 和结点2021 之间的最短路径长度是多少。

分析：

求最小公倍数问题以及怎样找到并更新最短路径。

代码实现：

int main()
{
    
    int f[2022];  // 数组 f[j] 存放从节点 i到节点 j 的最短路径。
    memset(f, 0, sizeof f);
    for (int i = 1; i <= 2021; i++)
    {
        for (int j = i + 1; j <= i + 21; j++) //考虑与节点 i 相差不超过 21 的节点 j。
        {
            if (j > 2021)//确保j不超出范围
                break;
            //把路径长度存储到数组中j对应的节点位置中
            if (f[j] == 0)  //如果节点 j 还没有被计算过（即 f[j] == 0），则将 f[j] 设置为从节点 i 到节点 j 的路径长度。
                f[j] = f[i] + j * i / gcd(i, j);   //j * i / gcd(i, j)为求最小公倍数
            else
                f[j] = min(f[j], f[i] + j * i / gcd(i, j)); // 如果节点j已经有计算过的路径长度，则更新 f[j] 为当前的较短路径长度。
        }
    }
    cout << f[2021] << endl;

    return 0;
}

解释上面用到的函数：

1、memset(f, 0, sizeof f); 是一个用于将数组 f 中的所有元素初始化为 0 的函数调用。memset 是 C 标准库中的一个函数，用于将一段内存区域的每个字节设置为指定值,传递数组首地址，让memset 函数知道要操作的内存区域的起始地址，以及需要操作的字节范围。这种方式常用于在程序开始时将数组或其他内存区域初始化为特定的默认值，以确保它们在使用前具有一致的初始状态。这样可以消除未初始化变量可能导致的意外结果，并提高代码的可靠性。

2、min() 函数通常用于找出两个或多个值中的最小值。它可以是标准库中的函数，也可以是用户自定义的函数，C++ 标准库中的 min() 函数可能在 <algorithm> 头文件中定义，它接受两个或多个参数，并返回这些参数中的最小值。

运行结果：