文章目录
前言
穷举法是一种基础而实用的算法策略，它通过逐一检查所有可能的情况来寻找问题的解。这种方法特别适用于问题规模较小或解决方案数量有限的情况。尽管穷举法可能不是最高效的算法，但它保证能找到问题的正确答案，尤其适合于初学者理解和实践。
本章将介绍穷举法的基本概念、步骤以及通过几个具体的例子来演示如何使用穷举法解决问题。
学习路线：C++从入门到NOI学习路线
学习大纲：C++全国青少年信息学奥林匹克竞赛（NOI）入门级-大纲
一、概念
1.导入
今天我们要来学习穷举。
当然不是这个“穷举”啦，穷举法是一种基本的算法策略，它通过逐一检查所有可能的情况来寻找问题的解。
可能这么说，大家无法理解这个概念。
你有一个密码箱，密码是一个三位数，每一位都是从0到9的数字。
箱子里面有你想要用的东西，但是很巧的是你把密码忘记了。
这种情况下，我们怎样才能打开这个锁呢？
由于我们不知道密码是什么，那我们首先想要的方法就是尝试所有的可能性。也就是说，从000开始，一直试到999，总共有1000种可能的组合。
你们肯定不会想到下面这种方法的。
这种尝试000，如果不行，就尝试001；如果001也不行，就尝试002，以此类推；继续尝试，直到找到正确的密码为止的方法就是穷举法。
2.概念
穷举法：通过尝试所有可能的选项来解决问题的方法。
优化：当有额外信息时，可以通过优化搜索范围来提高解决问题的效率。
穷举法的步骤如下：
-
确定问题的范围：根据问题的要求，确定需要尝试的数值范围。
-
使用循环进行穷举：使用循环结构（如for循环）遍历范围内的每个数值。
-
将数值带入问题中进行尝试：将当前数值带入问题中，判断是否满足问题的条件。
-
如果满足条件，输出结果或进行其他操作：如果当前数值满足问题的条件，可以输出该数值作为问题的解，或进行其他操作。
-
继续循环直到穷举完所有可能的解。
二、例题讲解
1. 简单穷举
问题：1015. 鸡兔同笼问题
类型：简单穷举
题目描述：
鸡兔同笼问题：一个笼子里面有鸡若干只，兔若干只。共有头 50 个，共有腿 160 条。求鸡兔各多少只？
输入：
无。
输出：
两个整数，在一行。
鸡的只数 兔的只数。
中间空格隔开！
样例：
输入：
输出：
1.分析问题
- 已知：头50 个、腿有160个。
- 未知：鸡，兔各多少。
- 关系：鸡 头1腿2，兔 头1腿4。
2.定义变量
根据分析的已知，未知按需要定义变量。
j：鸡
t：兔
//定义鸡、兔的数量。
int j=0,t=0;
3.输入数据
无。
4.数据计算
4.1 确定问题的范围：根据问题的要求，确定需要尝试的数值范围。
t + j = 50，t * 2 + j * 4 = 140
4.2 使用循环进行穷举：使用循环结构（如for循环）遍历范围内的每个数值。
4.3 将数值带入问题中进行尝试：将当前数值带入问题中，判断是否满足问题的条件。
//四、数据计算
while(j*2+(50-j)*4!=160){
j++;
}
4.4 如果满足条件，输出结果或进行其他操作。
t=50-j;
cout<<j<<" "<<t<<endl;
完整代码如下：
#include<iostream>
using namespace std;
int main(){
// 一、分析问题
// 已知：笼子里有50只动物（鸡和兔），这些动物总共有160条腿。
// 未知：鸡和兔各有多少只？
// 二、数据定义
// 定义鸡、兔的数量。
int j = 0, t = 0;
// 三、数据输入
// （在这个简单的示例中，数据已经作为常量给出，无需用户输入）
// 四、数据计算
// 使用while循环来穷举所有可能的鸡的数量
// 每次循环增加鸡的数量，并检查当前的腿总数是否等于160
while (j * 2 + (50 - j) * 4 != 160) {
j++; // 增加鸡的数量
}
t = 50 - j; // 兔子的数量为总数减去鸡的数量
// 五、输出结果
cout << j << " " << t << endl; // 输出鸡和兔的数量
return 0; // 主函数结束，返回0表示程序正常退出
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1351. 买公园门票
类型：简单穷举
题目描述：
某公园门票价格为：成人票 8 元 / 张，儿童票 3 元 / 张；某旅游团来公园游玩，该团内有成人和儿童（成人和儿童都有），共花了 40 元买门票。
请你分别计算出成人和儿童可能的人数，按照成人从少到多，儿童从多到少的规律数出结果。
输入：
无
输出：
若干行，每行 2 个整数用空格隔开，分别代表成人和儿童可能的人数。（成人从少到多，儿童从多到少）
样例：
输入：
输出：
1.分析问题
- 已知：成人票 8 元 / 张，儿童票 3 元 / 张；共花了 40 元买门票。
- 未知：成人和儿童的人数。
- 关系：成人从少到多，儿童从多到少。
2.定义变量
无。
3.输入数据
无。
4.数据计算
4.1 确定问题的范围：根据问题的要求，确定需要尝试的数值范围。
成人票：最少1张，最多(40-3)/8张，要保证有一张儿童票。
儿童票：最少1张，最多(40-8)/3张，要保证有一张成人票。
4.2 使用循环进行穷举：使用循环结构（如for循环）遍历范围内的每个数值。
i：成人票数量。
for(int i=1;i<=(40-3)/8;i++){
}
4.3 将数值带入问题中进行尝试：将当前数值带入问题中，判断是否满足问题的条件。
j：购买成人票后剩余钱数。
如果j%3==0，说明剩余的钱刚好能买整数个儿童票，符合题意。
//四、数据计算
for(int i=1;i<=(40-3)/8;i++){
int j=40-8*i;
if(j%3==0){
}
}
4.4 如果满足条件，输出结果或进行其他操作。如果当前数值满足问题的条件，可以输出该数值作为问题的解，或进行其他操作。
//四、数据计算
for(int i=1;i<=(40-3)/8;i++){
int j=40-8*i;
if(j%3==0){
//五、输出结果
cout<<i<<" "<<j/3;
}
}
4.5 继续循环直到穷举完所有可能的解。
完整代码如下：
#include<iostream>
using namespace std;
int main(){
// 一、分析问题
// 1. 已知：成人票 8 元 / 张，儿童票 3 元 / 张；共花了 40 元买门票。
// 2. 未知：成人和儿童的人数。
// 二、数据定义
// 定义成人票和儿童票的数量。
// 由于成人票价较高，我们从成人票开始穷举。
// 三、数据输入
// （在这个简单的示例中，数据已经作为常量给出，无需用户输入）
// 四、数据计算
// 使用for循环来穷举所有可能的成人票数量
// 每次循环增加成人票的数量，并检查剩余金额是否能被3整除
for(int i = 1; i <= (40 - 3) / 8; i++) { // 穷举成人票数量
int j = 40 - 8 * i; // 剩余金额
if (j % 3 == 0) { // 如果剩余金额能被3整除
// 五、输出结果
cout << i << " " << j / 3 << endl; // 输出成人和儿童的人数
}
}
return 0; // 主函数结束，返回0表示程序正常退出
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1016. 买小猫小狗
类型：简单循环
题目描述：
某动物饲养中心用 X 元专款购买小狗(每只 A 元)和小猫(每只B 元)两种小动物。
要求专款专用，(至少猫狗各一)，正好用完。
请求出方案的总数。如没有请输出 0 。
输入：
输入一行，只有三个整数.分别为 X,A,B。( 100<X<32768，1≤A≤100，1≤B≤100 )
输出：
输出只有一行（这意味着末尾有一个回车符号），包括 1 个整数。
样例：
输入：
1700 31 21
输出：
3
1.分析问题
- 已知：小狗 A 元 / 只，小猫 B 元 / 只；共有 X 元。
- 未知：猫狗各一，购买方案总数。
- 关系：A*狗的数量+B * 猫的数量 = X。
2.定义变量
根据分析的已知，未知按需要定义变量。
A：小狗每只价格。
B：小猫每只价格。
X：有多少钱。
count：购买方案的总数。
//二、数据定义
int A,B,X,count=0;
3.输入数据
从键盘读入数据。
//三、数据输入
cin>>X>>A>>B;
4.数据计算
4.1 确定问题的范围：根据问题的要求，确定需要尝试的数值范围。
狗：最少1只，最多(X-B)/A只，要保证有一只猫。
猫：最少1只，最多(X-A)/B张，要保证有一只狗。
4.2 使用循环进行穷举：使用循环结构（如for循环）遍历范围内的每个数值。
a：狗的数量。
//四、数据计算
for(int a=1;a<=(X-B)/A;a++){
}
4.3 将数值带入问题中进行尝试：将当前数值带入问题中，判断是否满足问题的条件。
b：购买狗后剩余钱数。
如果b%B==0，说明剩余的钱刚好能买整数只猫，符合题意。
//四、数据计算
for(int a=1;a<=(X-B)/A;a++){
int b=X-A*a;
if(b%B==0){
}
}
4.4 如果满足条件，输出结果或进行其他操作。如果当前数值满足问题的条件，可以输出该数值作为问题的解，或进行其他操作。
//四、数据计算
for(int a=1;a<=(X-B)/A;a++){
int b=X-A*a;
if(b%B==0){
++count;
}
}
4.5 继续循环直到穷举完所有可能的解。
完整代码如下：
#include <iostream>
using namespace std;
int main() {
// 定义变量
// A: 小狗的价格
// B: 小猫的价格
// X: 总金额
// count: 购买方案的总数
int A, B, X, count = 0;
// 输入数据
// 用户输入总金额 X 和单价 A, B
cin >> X >> A >> B;
// 计算购买方案
// 遍历所有可能的小狗数量 a
// a 的范围是从 1 到 (X - B) / A，即在剩余金额允许的情况下最多能买多少只小狗
for (int a = 1; a <= (X - B) / A; a++) {
// 计算剩余金额是否能买整数只小猫
// b 为剩余金额，等于总金额 X 减去已经花费在 a 只小狗上的金额
int b = X - A * a;
// 如果剩余金额 b 能够整除小猫的价格 B，则这是一种有效的购买方案
if (b % B == 0) {
// 购买方案总数加 1
++count;
}
}
// 输出购买方案的总数
cout << count;
return 0;
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1220. 买糕点
类型：简单穷举
题目描述：
妈妈给了小明 n 元，给小明同学去面包店买糕点吃，小明非常喜欢吃切片面包和蛋挞，今天切片面包 x 元一件（一包），蛋挞 y 元一件（一盒）；小明想花光 n 元买这两样糕点，而且每样都至少买一件，请问，小明可以采购的方案中，能够买最多面包的方案是什么？
比如，100 元，面包 15 元/件，蛋挞 10 元/件，那么可行的购买方案有：
2 件面包 7 件蛋挞
4 件面包 4 件蛋挞
6 件面包 1 件蛋挞
而上述方案中，面包最多的购买方案是：
6 件面包 1 件蛋挞，因此输出：6 1
输入：
三个变量：n x y，分别代表总金额，面包的单价和蛋挞的单价！
输出：
两个数，分别代表采购方案中能够买到最多面包的件数和蛋挞的件数！
样例：
输入：
100 15 10
输出：
6 1
1.分析问题
- 已知：有n元,面包 x元/个,蛋挞y元/个 ；
- 未知：能够买最多面包的方案是什么？
- 关系：花光n元，每样都至少买一件。因此为了保证买的面包的数量是最多的，那么蛋挞的数量就要最少。
2.定义变量
- 定义变量 n 表示总金额，x 和 y 分别表示面包和蛋挞的价格，m 和 d 分别表示最多面包数和蛋挞数量，其中 d 初始化为 1。
//二、定义变量（已知、未知、关系）
int n,x,y,m,d=1;
3.输入数据
- 输出最多能够购买的面包数量 m 和对应的蛋挞数量 d
//三、输入已知
cin>>n>>x>>y;
4.数据计算
- 使用一个 for 循环来遍历所有可能的蛋挞数量 d，其中 d 的范围是从 1 到 (n−x)/y（即在剩余金额允许的情况下最多能买多少蛋挞）。
- 对于每个蛋挞数量 d，检查剩余金额是否能够整除面包的价格 x。如果可以，那么这是一种有效的购买方案，并记录此时的面包数量 m 和蛋挞数量 d，然后退出循环。
//四、根据关系计算
for(;d<=(n-x)/y;d++){
if((n-y*d)%x==0){
m=(n-y*d)/x;
break;
}
}
5.输出结果
- 输出最多能够购买的面包数量 m 和对应的蛋挞数量 d。
//五、输出未知
cout<<m<<" "<<d;
完整代码如下：
#include <bits/stdc++.h> // 包含所有常用的头文件
using namespace std;
int main() {
// 一、分析问题
// 已知：有 n 元，面包 x 元/个，蛋挞 y 元/个
// 未知：能够买最多面包的方案是什么？
// 关系：花光 n 元，每样都至少买一件
// 二、定义变量（已知、未知、关系）
int n, x, y, m, d = 1; // n: 总金额, x: 面包价格, y: 蛋挞价格, m: 最多面包数, d: 蛋槽数量
// 三、输入已知
cin >> n >> x >> y;
// 四、根据关系计算
// 通过循环遍历所有可能的蛋槽数量 d
for (; d <= (n - x) / y; d++) { // 确保剩余金额足够买至少一个面包
if ((n - y * d) % x == 0) { // 如果剩余金额能够整除面包价格
m = (n - y * d) / x; // 计算能够购买的面包数量
break; // 找到第一个符合条件的解就退出循环
}
}
// 五、输出未知
cout << m << " " << d; // 输出最多能够购买的面包数量和对应的蛋槽数量
return 0;
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1396. 开学大采购？
类型：简单穷举
题目描述：
新学期开始了，学校计划采购一批新的篮球和排球用来上体育课。
学校共有 n 元经费，咨询体育用品店得知篮球 x 元 / 个，排球 y 元 / 个，现要求篮球和排球都至少采购 1 个， n 元经费全部用完，且篮球和排球的总数要超过 50 个。
请问有哪些采购方案？（按照篮球从少到多，排球从多到少输出所有可行的方案）
输入：
三个整数，n、x、y 用空格隔开分别代表总经费、篮球单价、排球单价。
输出：
所有可行的采购方案，每个组方案有 2 个整数用空格隔开，第 1 个整数代表篮球的采购个数，第 2 个整数代表排球的采购个数。
样例：
输入：
1000 25 15
输出：
1 65
4 60
7 55
10 50
13 45
16 40
19 35
22 30
1.分析问题
- 已知：n元经费,篮球 x 元 / 个，排球 y 元 / 个。
- 未知：按照篮球从少到多，排球从多到少输出所有可行的方案。
- 关系：n元经费全部用完，都至少采购 1 个,且篮球和排球的总数要超过 50 个。
2.定义变量
- 定义变量 n 表示总金额，x 和 y 分别表示篮球和排球的价格，l 和 p 分别表示篮球数量和排球数量，其中 l 初始化为 1。
//二、定义变量（已知、未知、关系）
int n,x,y,l=1,p;
3.输入数据
- 从标准输入读取总金额 n，篮球的价格 x，和排球的价格 y。
//三、输入已知
cin>>n>>x>>y;
4.数据计算
- 使用一个 for 循环来遍历所有可能的篮球数量 l，其中 l 的范围是从 1 到 (n−y)/x（即在剩余金额允许的情况下最多能买多少篮球）。
- 对于每个篮球数量 l，计算剩余金额能够购买的排球数量 p。
- 检查篮球和排球的总价是否等于总金额 n，并且篮球和排球的总数是否超过 50。如果满足条件，输出篮球数量 l 和排球数量 p。
//四、根据关系计算
for(;l<=(n-y)/x;l++){
p=(n-x*l)/y;
//五、输出未知
if(l*x+p*y==n && l+p>50){
cout<<l<<" "<<p<<"\n";
}
}
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
// 一、分析问题
// 已知：有 n 元经费，篮球 x 元 / 个，排球 y 元 / 个。
// 未知：按照篮球从少到多，排球从多到少输出所有可行的方案。
// 关系：n 元经费全部用完，都至少采购 1 个，且篮球和排球的总数要超过 50 个。
// 二、定义变量（已知、未知、关系）
int n, x, y, l = 1, p; // n: 经费总额, x: 篮球价格, y: 排球价格, l: 篮球数量, p: 排球数量
// 三、输入已知
cin >> n >> x >> y;
// 四、根据关系计算
// 通过循环遍历所有可能的篮球数量 l
for (; l <= (n - y) / x; l++) { // 确保剩余金额足够买至少一个排球
p = (n - x * l) / y; // 根据剩余金额计算排球数量
// 五、输出未知
if (l * x + p * y == n && l + p > 50) { // 确保总金额正好用完且篮球和排球总数超过 50
cout << l << " " << p << "\n"; // 输出篮球数量和排球数量
}
}
return 0;
}
2. 嵌套穷举
问题：1022. 百钱百鸡问题
类型：嵌套穷举
题目描述：
用 100 元钱买 100 只鸡，公鸡，母鸡，小鸡都要有。
公鸡 5 元 1 只，母鸡 3 元 1 只，小鸡 1 元 3 只。
请问公鸡，母鸡，小鸡各应该买多少只？
输入：
无。
输出：
每种买法占一行，由 3 个数组成，顺序为 公鸡数 母鸡数 小鸡数。每个数字空格隔开。
输出时，按公鸡数从少到多，母鸡数从多到少的顺序输出，本题符合条件的第一组解为： 4 18 78 。
样例：
输入：
输出：
1.分析问题
- 已知：用 100 元钱买 100 只鸡,公鸡 5 元 1 只，母鸡 3 元 1 只，小鸡 1 元 3 只。
- 未知：找出所有解：公鸡，母鸡，小鸡各应该买多少只？
- 关系：公鸡，母鸡，小鸡都要有,按公鸡数从少到多，母鸡数从多到少的顺序输出。
2.定义变量
- 定义变量 g 表示公鸡数量，m 表示母鸡数量，x 表示小鸡数量，其中 g 初始化为 1。
//二、定义变量（已知、未知、关系）
int g=1,m,x;
3.输入数据
无。
4.数据计算
- 外层循环遍历所有可能的公鸡数量 g，其中 g 的范围是从 1 到 (100−3−1)/5（即在剩余金额允许的情况下最多能买多少公鸡）。
- 对于每个公鸡数量 g，计算可能的母鸡数量 m。
- 内层循环遍历所有可能的母鸡数量 m，其中 m 的范围是从 1 到初始计算的 m 值（即在剩余金额允许的情况下最多能买多少母鸡）。
- 对于每个母鸡数量 m，计算小鸡数量 x。
- 检查公鸡、母鸡和小鸡的总数量是否为 100。如果满足条件，输出公鸡数量 g、母鸡数量 m 和小鸡数量 x。
//四、根据关系计算
for(;g<=(100-3-1)/5;g++){
m=(100-5*g-1)/3;
for(;m>=1;m--){
x=3*(100-5*g-3*m);
//五、输出未知
if(g+m+x==100){
cout<<g<<" "<<m<<" "<<x<<"\n";
}
}
}
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
// 一、分析问题
// 已知：用 100 元钱买 100 只鸡,公鸡 5 元 1 只，母鸡 3 元 1 只，小鸡 1 元 3 只。
// 未知：找出所有解：公鸡，母鸡，小鸡各应该买多少只？
// 关系: 公鸡，母鸡，小鸡都要有,按公鸡数从少到多，母鸡数从多到少的顺序输出。
// 二、定义变量（已知、未知、关系）
int g = 1, m, x; // g: 公鸡数量, m: 母鸡数量, x: 小鸡数量
// 四、根据关系计算
// 通过循环遍历所有可能的公鸡数量 g
for (; g <= (100 - 3 - 1) / 5; g++) { // 确保剩余金额足够买至少一只母鸡和一只小鸡
m = (100 - 5 * g - 1) / 3; // 根据剩余金额计算可能的母鸡数量
// 内层循环遍历所有可能的母鸡数量 m
for (; m >= 1; m--) { // 确保母鸡数量至少为 1
x = 3 * (100 - 5 * g - 3 * m); // 根据剩余金额计算小鸡数量
// 五、输出未知
if (g + m + x == 100 ) { // 确保总数量为 100
cout << g << " " << m << " " << x << "\n"; // 输出公鸡数量、母鸡数量和小鸡数量
}
}
}
return 0;
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1024. 购买文具
类型：嵌套穷举
题目描述：
新学年就要开始了，爸爸把N元钱给了小青，让他购买一批文具，并作了以下要求：只能买圆珠笔、铅笔和铅笔芯，并且每样至少买一支，总数要超过30支，而且钱要全部花完。
当小青去到文具店时，发现圆珠笔8角钱一支、铅笔2角钱一支、铅笔芯1角钱一支。小青怎么买才能符合爸爸的要求呢？请你编个程序帮他算出符合购买要求的所有方案总数。
输入：
一个整数N，表示购买文具一共的元数。（1 <= N <= 50）
输出：
一个整数，即符合购买要求的所有方案总数。
样例：
输入：
8
输出：
135
1.分析问题
- 已知：N元钱,圆珠笔8角钱一支、铅笔2角钱一支、铅笔芯1角钱一支。
- 未知：符合购买要求的所有方案总数。
- 关系：每样至少买一支，总数要超过30支，而且钱要全部花完。
2.定义变量
- 定义变量 n 表示总金额（以角为单位），y 表示圆珠笔数量，qb 表示铅笔数量，qbx 表示铅笔芯数量，c 表示方案总数，其中 y 初始化为 1，c 初始化为 0。
//二、定义变量（已知、未知、关系）
int n,y=1,qb,qbx,c=0;
3.输入数据
- 从标准输入读取总金额 N。
- 将金额放大10倍，方便计算。
//三、输入已知
cin>>n;
n*=10;
4.数据计算
- 外层循环遍历所有可能的圆珠笔数量 y，其中 y 的范围是从 1 到 (n−2−1)/8（即在剩余金额允许的情况下最多能买多少圆珠笔）。
- 对于每个圆珠笔数量 y，计算可能的铅笔数量 qb。
- 内层循环遍历所有可能的铅笔数量 qb，其中 qb 的范围是从 1 到初始计算的 qb 值（即在剩余金额允许的情况下最多能买多少铅笔）。
- 对于每个铅笔数量 qb，计算铅笔芯数量 qbx。
- 检查圆珠笔、铅笔和铅笔芯的总数量是否超过 30 支。如果满足条件，方案总数 c 加 1。
//四、根据关系计算
for(;y<=(n-2-1)/8;y++){
qb=(n-8*y-1)/2;
for(;qb>=1;qb--){
qbx=n-8*y-2*qb;
if(y+qb+qbx>30) ++c;
}
}
5.输出结果
- 输出方案总数 c。
//五、输出未知
cout<<c;
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
// 一、分析问题
// 已知：N元钱, 圆珠笔 8 角钱一支、铅笔 2 角钱一支、铅笔芯 1 角钱一支。
// 未知：符合购买要求的所有方案总数。
// 关系: 每样至少买一支，总数要超过 30 支，而且钱要全部花完。
// 二、定义变量（已知、未知、关系）
int n, y = 1, qb, qbx, c = 0; // n: 总金额（以角为单位），y: 圆珠笔数量, qb: 铅笔数量, qbx: 铅笔芯数量, c: 方案总数
// 三、输入已知
cin >> n;
n *= 10; // 将金额转换为角
// 四、根据关系计算
// 通过循环遍历所有可能的圆珠笔数量 y
for (; y <= (n - 2 - 1) / 8; y++) { // 确保剩余金额足够买至少一支铅笔和一支铅笔芯
qb = (n - 8 * y - 1) / 2; // 根据剩余金额计算可能的铅笔数量
// 内层循环遍历所有可能的铅笔数量 qb
for (; qb >= 1; qb--) { // 确保铅笔数量至少为 1
qbx = n - 8 * y - 2 * qb; // 根据剩余金额计算铅笔芯数量
// 五、输出未知
if (y + qb + qbx > 30) { // 确保总数量超过 30 支
++c; // 符合条件，方案总数加 1
}
}
}
// 五、输出未知
cout << c; // 输出方案总数
return 0;
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1249. 搬砖问题
类型：嵌套穷举
题目描述：
36 块砖， 36 人搬。男搬 4 ，女搬 3 ，两个小儿抬一砖。
要求一次全搬完。问需男、女、小儿各若干？
注意：假设男、女、小孩都有，请按照男、女、小孩的顺序输出所有可能的人数分配，每种人数分配方案占 1 行，每个数字空格隔开。
输入：
无。
输出：
所有可能的人数分配方案，按照由小到大输出。
样例：
输入：
输出：
1.分析问题
- 已知：36 块砖， 36 人搬。男搬 4 ，女搬 3 ，两个小儿抬一砖。
- 未知：要求一次全搬完。问需男、女、小儿各若干？输出所有可能的人数分配。
- 关系：男、女、小孩都有，按照男、女、小孩的顺序由小到大输出。
2.定义变量
- 定义变量 m 表示男性人数，w 表示女性人数，c 表示小孩人数，其中 m 和 w 初始化为 1。
//二、定义变量（已知、未知、关系）
int m=1,w,c;
3.输入数据
无。
4.数据计算
- 外层循环遍历所有可能的男性人数 m，其中 m 的范围是从 1 到 (36−3−1)/4（即在剩余人数允许的情况下最多能有多少男性）。
- 内层循环遍历所有可能的女性人数 w，其中 w 的范围是从 1 到 (36−m∗4−1)/3（即在剩余人数允许的情况下最多能有多少女性）。
- 对于每个女性人数 w，计算小孩数量 c。
- 检查男性、女性和小孩的总人数是否为 36。如果满足条件，输出男性人数 m、女性人数 w 和小孩人数 c。
//四、根据关系计算
for(;m<=(36-3-1)/4;m++){
for(w=1;w<=(36-m*4-1)/3;w++){
c=(36-m*4-w*3)*2;
//五、输出未知
if(m+w+c==36){
cout<<m<<" "<<w<<" "<<c<<"\n";
}
}
}
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
// 一、分析问题
// 已知：36 块砖，36 人搬。男搬 4，女搬 3，两个小孩抬 1 块砖。
// 未知：要求一次全搬完。问需男、女、小孩各若干？输出所有可能的人数分配。
// 关系: 男、女、小孩都有，按照男、女、小孩的顺序由小到大输出。
// 二、定义变量（已知、未知、关系）
int m = 1, w, c; // m: 男性人数, w: 女性人数, c: 小孩人数
// 四、根据关系计算
// 通过循环遍历所有可能的男性人数 m
for (; m <= (36 - 3 - 1) / 4; m++) { // 确保剩余人数足够搬至少一位女性和两位小孩
// 内层循环遍历所有可能的女性人数 w
for (w=1; w <= (36 - m * 4 - 1) / 3; w++) { // 确保剩余人数足够搬至少两位小孩
c = (36 - m * 4 - w * 3) * 2; // 根据剩余人数计算小孩数量
// 五、输出未知
if (m + w + c == 36) { // 确保总人数为 36
cout << m << " " << w << " " << c << "\n"; // 输出男性人数、女性人数和小孩人数
}
}
}
return 0;
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1250. 马克思手稿的问题
类型：嵌套穷举
题目描述：
马克思手稿中有一道趣味数学题：有 30 个人，其中可能有男人、女人和小孩，在一家饭馆里吃饭共花了 50 先令。
假设每个男人各花 3先令，每个女人各花 2 先令，每个小孩各花 1先令。
问男人、女人和小孩各有几人？（注意：不一定男人、女人、小孩都有）
输入：
无。
输出：
每行 3 个数，按照男人、女人、小孩的顺序，由小到大依次输出所有可能的人数方案（男人、女人、小孩其中某些人的数量可以为 0 ）
样例：
输入：
输出：
1.分析问题
-
已知： 有 30 个人，花了 50 先令,每个男人各花 3先令，每个女人各花 2 先令，每个小孩各花 1先令。
-
未知：问男人、女人和小孩各有几人？按照男人、女人、小孩的顺序，由小到大依次输出所有可能的人数方案。
-
关系：男人、女人、小孩其中某些人的数量可以为 0 。
2.定义变量
- 定义了三个整型变量 m, w, 和 c 分别表示男人、女人和小孩的数量。
//二、定义变量（已知、未知、关系）
int m=0,w,c;
3.输入数据
无。
4.数据计算
-
外层循环遍历所有可能的男人数量，从 0 到 30。
-
内层循环遍历所有可能的女人数量，考虑到总人数不能超过 30 人，因此女人的数量最多为 30 - m。
-
根据当前的男人和女人数量计算小孩的数量。
-
判断当前组合是否使得总花费等于 50 先令。如果是，则输出男人、女人和小孩的数量。
//四、根据关系计算
for(;m<=30;++m){
for(w=0;w<=30-m;++w){
c=30-m-w;
//五、输出未知
if(50==m*3+w*2+c){
cout<<m<<" "<<w<<" "<<c<<"\n";
}
}
}
完整代码如下：
#include <bits/stdc++..h> // 包含所有标准库
using namespace std;
int main() {
// 定义变量
int m = 0, w, c; // m 表示男人数量，w 表示女人数量，c 表示小孩数量
// 使用嵌套循环来尝试所有可能的组合
for (; m <= 30; ++m) { // 循环遍历所有可能的男人数量
for (w = 0; w <= 30 - m; ++w) { // 循环遍历所有可能的女人数量
c = 30 - m - w; // 剩下的人数就是小孩的数量
// 检查当前组合是否满足总花费为 50 先令
if (50 == m * 3 + w * 2 + c) {
// 如果满足条件，则输出当前组合
cout << m << " " << w << " " << c << "\n";
}
}
}
return 0; // 正常退出程序
}
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
问题：1342. 怎样种树？
类型：嵌套穷举
题目描述：
公园准备在小山上种桃树、梨树、苹果树，为了美观，总共准备种n棵树（ n≥6 且 n 一定是 6 的倍数），要求三种树都得有，且每种树的数量都得是偶数，桃树的数量不能比梨树的数量多，梨树的数量不能比苹果树的数量多。
请问有这三种树的数量分别有哪些可能的组合方法，从少到多分别数出桃树、梨树、苹果数可能的数量组合，每行 1 个方案。
输入：
一个整数n( n≥6 且是 6 的倍数）
输出：
若干行的可能的组合方案，每行 3 个数，分别代表桃树、梨树、苹果树的可能的方案。
样例：
输入：
18
输出：
2 2 14
2 4 12
2 6 10
2 8 8
4 4 10
4 6 8
6 6 6
1.分析问题
-
已知： 准备种n棵树,三种树都得有,且每种树的数量都得是偶数,桃树的数量不能比梨树的数量多，梨树的数量不能比苹果树的数量多。
-
未知： 请问有这三种树的数量分别有哪些可能的组合方法，从少到多分别数出桃树、梨树、苹果数可能的数量组合，每行 1 个方案。
2.定义变量
- 定义变量 n（总树的数量）、t（桃树数量）、l（梨树数量）和 p（苹果树数量）。
//二、定义变量（已知、未知、关系）
int n,t=2,l,p;
3.输入数据
- 读取用户输入的总树的数量。
//三、输入已知
cin>>n;
4.数据计算
- 外层循环遍历所有可能的桃树数量，从 2 开始每次增加 2，确保桃树数量始终是偶数且不超过总数的三分之一。
- 内层循环遍历所有可能的梨树数量，从当前桃树数量开始每次增加 2，确保梨树数量大于等于桃树数量，且不超过剩余树的一半。
- 计算苹果树的数量,输出当前组合。
//四、根据关系计算
for(;t<=n/3;t+=2){
for(l=t;l<=(n-t)/2;l+=2){
p=n-t-l;
//五、输出未知
cout<<t<<" "<<l<<" "<<p<<"\n";
}
}
完整代码如下：
#include <bits/stdc++.h> // 包含所有标准库
using namespace std;
int main() {
// 定义变量
int n, t = 2, l, p; // n 是总树的数量，t 表示桃树数量，l 表示梨树数量，p 表示苹果树数量
// 输入已知的总树的数量
cin >> n;
// 使用嵌套循环来尝试所有可能的组合
for (; t <= n / 3; t += 2) { // 循环遍历所有可能的桃树数量，从 2 开始每次增加 2
for (l = t; l <= (n - t) / 2; l += 2) { // 循环遍历所有可能的梨树数量，从当前桃树数量开始，每次增加 2
p = n - t - l; // 剩下的数量就是苹果树的数量
// 输出当前组合
cout << t << " " << l << " " << p << "\n";
}
}
return 0; // 正常退出程序
}
三、总结
穷举法是一种直观且易于实现的方法，适合处理规模不大、解决方案数量有限的问题。然而，当问题规模增大时，穷举法的效率会显著降低，因此在实践中需要考虑是否采用更高效的算法或对该方法进行优化。
四、感谢
如若本文对您的学习或工作有所启发和帮助，恳请您给予宝贵的支持——轻轻一点，为文章点赞；若觉得内容值得分享给更多朋友，欢迎转发扩散；若认为此篇内容具有长期参考价值，敬请收藏以便随时查阅。
每一次您的点赞、分享与收藏，都是对我持续创作和分享的热情鼓励，也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇，共同攀登知识的高峰！
欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》
