P1236 算24点
题目描述
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算 \(24\) 点”。您作为游戏者将得到 \(4\) 个 \(1 \sim 9\) 之间的自然数作为操作数，而您的任务是对这 \(4\) 个操作数进行适当的算术运算，要求运算结果等于 \(24\)。
您可以使用的运算只有：\(\verb!+!,\verb!-!,\verb!*!,\verb!/!\)，您还可以使用 \(\verb!()!\) 来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，\((2\times 2)/4\) 是合法的，\(2\times (2/4)\) 是不合法的）。下面我们给出一个游戏的具体例子：
若给出的 \(4\) 个操作数是：\(1\)、\(2\)、\(3\)、\(7\)，则一种可能的解答是 \(1+2+3\times 7=24\)。
输入格式
只有一行，四个 \(1\) 到 \(9\) 之间的自然数。
输出格式
如果有解的话，只要输出一个解。输出的是三行数据，分别表示运算的步骤。
- 其中第一行是输入的两个数和一个运算符和运算后的结果；
- 第二行是第一行的结果和一个输入的数据、运算符、运算后的结果，或者是另外两个数的输出结果；
- 第三行是前面的结果第二行的结果或者剩下的一个数字、运算符和 \(\verb!=24!\)。如果两个操作数有大小的话则先输出大的。
如果没有解则输出 No answer!。
如果有多重合法解，输出任意一种即可。
注：所有运算结果均为正整数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
感谢 chenyy 提供 special judge
\(\text{upd 2022.8.1}\)：新增加一组 Hack 数据。
Tip
📌 题目分析
给定数据：
要求利用加减乘除（+, -, *, /）和括号，把这四个数计算成 24。如果可以，输出具体的三个计算步骤（每次选两个数计算）；如果不行，输出 No answer!。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么使用 DFS 与回溯
这道题看起来像是需要解析复杂的数学表达式和括号，但实际上，不管括号怎么加，计算的本质永远是：每次从当前的数字集合中挑出两个数，进行一次运算，然后把结果放回集合中。
- 初始状态：4 个数。
- 第一步：挑 2 个数算出一个结果，把它们从集合中删掉，加上新结果，变成 3 个数。
- 第二步：从 3 个数里挑 2 个算出一个结果，集合变成 2 个数。
- 第三步：从 2 个数里挑 2 个算出一个结果，集合变成 1 个数。
- 最后检查这仅剩的 1 个数是不是 24 即可。
这种“尝试一种可能 -> 往下深入 -> 行不通就退回来（回溯）换一种”的模式，天然适合 DFS。
2️⃣ 状态的记录与剪枝
在 DFS 的过程中，我们不仅要传递当前的数字集合，还要传递操作路径（步骤），因为题目要求输出运算的具体过程。
对于加法和乘法，满足交换律（a + b = b + a），为了不输出重复或者避免多余计算，我们可以强制规定一下顺序，并且在保存路径时统一把较大的数字放在前面（这也是题目的特殊要求）。
3️⃣ 题目的特殊限制
洛谷的这道题有几个非常严苛的隐藏坑点，我们必须特别处理：
* 只允许正整数： 题目提示“所有运算结果均为正整数”。这意味着减法必须是 a - b > 0，不能出现 0。除法必须能整除，即 a % b == 0。
* 大数在前： 输出步骤时，如果有大小之分，必须先输出大的数。所以无论是 +, -, *, /，我们在记录步骤时，统一写成 max(a, b) 运算符 min(a, b)。
* 找到即止： 只要找到一种合法方案，立刻打印并结束程序（或者通过标记位直接层层 return），不需要打印所有解。
4️⃣ 时间复杂度
每一次递归选取两个数字： * 从 4 个选 2 个有 6 种选法，4 种运算； * 从 3 个选 2 个有 3 种选法，4 种运算； * 从 2 个选 2 个有 1 种选法，4 种运算。
总的计算分支非常小（约几千次），对于 C++ 来说，耗时无限接近于 0 毫秒。
Tip
这题虽然代码量看着大，其实只要思路想清楚了，框架搭好了，很多代码都是重复的，所以这道题并不能难，大体上还是回溯总结的那个框架
💻 C++代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 用于记录每一步的运算过程
struct Step {
int a, b;
char op;
int res;
};
bool found_ans = false;
// DFS 核心函数
void dfs(vector<int> nums, vector<Step> steps) {
if (found_ans) return; // 如果已经找到答案，直接剪枝退出
// 边界条件：当集合里只剩下 1 个数时，检查是不是 24
if (nums.size() == 1) {
if (nums[0] == 24) {
// 按要求输出三行步骤
for (int i = 0; i < steps.size(); i++) {
cout << steps[i].a << steps[i].op << steps[i].b << "=" << steps[i].res << "\n";
}
found_ans = true;
}
return;
}
int n = nums.size();
// 遍历当前集合中任意两个不同的数字
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int a = nums[i];
int b = nums[j];
// 构建下一层的数字集合
vector<int> next_nums;
for (int k = 0; k < n; k++) {
if (k != i && k != j) next_nums.push_back(nums[k]);
}
// 1. 加法 (+)
// 加法有交换律，规定 i < j 避免重复计算，同时记录步骤时保证大数在前
if (i < j) {
next_nums.push_back(a + b);
steps.push_back({max(a, b), min(a, b), '+', a + b});
dfs(next_nums, steps);
steps.pop_back(); // 回溯
next_nums.pop_back();
}
// 2. 乘法 (*)
// 同加法，大数在前
if (i < j) {
next_nums.push_back(a * b);
steps.push_back({max(a, b), min(a, b), '*', a * b});
dfs(next_nums, steps);
steps.pop_back();
next_nums.pop_back();
}
// 3. 减法 (-)
// 题目要求中间结果均为正整数，所以要求 a > b
if (a > b) {
next_nums.push_back(a - b);
steps.push_back({a, b, '-', a - b});
dfs(next_nums, steps);
steps.pop_back();
next_nums.pop_back();
}
// 4. 除法 (/)
// 必须能够整除，且结果必须为正整数
if (b != 0 && a % b == 0) {
next_nums.push_back(a / b);
steps.push_back({a, b, '/', a / b}); // 能整除说明 a >= b，天然是大数在前
dfs(next_nums, steps);
steps.pop_back();
next_nums.pop_back();
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> nums(4);
for (int i = 0; i < 4; i++) {
cin >> nums[i];
}
vector<Step> path;
dfs(nums, path);
// 搜遍了也没找到
if (!found_ans) {
cout << "No answer!\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 大小数字颠倒导致 WA
题目明确规定：“如果两个操作数有大小的话则先输出大的”。
如果你写出了 3*7=21，在洛谷这道题里就是错的，必须输出 7*3=21。在构建 Step 结构体时，使用 max 和 min 直接格式化是最佳防坑手段。
❌ 2. 负数和零的干扰
这是洛谷数据的一个老坑（后来补充的数据）。
普通的算 24 点可能允许中间出现 0（比如 10 - 10 = 0），但这道题说“所有运算结果均为正整数”。
如果你让 a - b == 0，然后带着 0 往下走，不仅不符合题意，还可能在下一次当作除数引发运行时错误（RE）。严格限制 a > b 即可。
❌ 3. 除法用成了浮点除
千万不要引入 double 或 / 1.0。
题目要求只能在整数域进行除法，比如 (2*2)/4 是通过先算乘法后算除法得到的，不是先让 2/4 变成 0.5。限制条件必定是 a % b == 0 才能进行分支搜索。
🚀 一句话总结
Warning
如果看懂了上面的做法，可以看看我的做法，只是有略微不同，思路是一样的
看过我三连击的解题方法，应该知道我喜欢拿string装数据，我这道题也是拿string装一些过程变量，而不是拿结构体
#include <bits/stdc++.h>
using namespace std;
vector<string> ans;
bool found = false;
string make_expr(int a, char op, int b, int c) {
return to_string(a) + op + to_string(b) + "=" + to_string(c);
}
void dfs(vector<int> nums, vector<string> steps) {
if (found) return;
int n = nums.size();
if (n == 1) {
if (nums[0] == 24) {
ans = steps;
found = true;
}
return;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = nums[i], y = nums[j];
vector<int> rest;
for (int k = 0; k < n; k++) {
if (k != i && k != j) rest.push_back(nums[k]);
}
// 1. 加法：大的在前
{
int a = max(x, y), b = min(x, y);
int z = a + b;
if (z > 0) {
auto nxt = rest;
nxt.push_back(z);
auto s = steps;
s.push_back(make_expr(a, '+', b, z));
dfs(nxt, s);
if (found) return;
}
}
// 2. 乘法：大的在前
{
int a = max(x, y), b = min(x, y);
int z = a * b;
if (z > 0) {
auto nxt = rest;
nxt.push_back(z);
auto s = steps;
s.push_back(make_expr(a, '*', b, z));
dfs(nxt, s);
if (found) return;
}
}
// 3. 减法：大的减小的，结果必须为正
{
int a = max(x, y), b = min(x, y);
int z = a - b;
if (z > 0) {
auto nxt = rest;
nxt.push_back(z);
auto s = steps;
s.push_back(make_expr(a, '-', b, z));
dfs(nxt, s);
if (found) return;
}
}
// 4. 除法：大的除以小的，必须整除且结果为正
{
int a = max(x, y), b = min(x, y);
if (b != 0 && a % b == 0) {
int z = a / b;
if (z > 0) {
auto nxt = rest;
nxt.push_back(z);
auto s = steps;
s.push_back(make_expr(a, '/', b, z));
dfs(nxt, s);
if (found) return;
}
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> nums(4);
for (int i = 0; i < 4; i++) cin >> nums[i];
dfs(nums, {});
if (!found) {
cout << "No answer!\n";
} else {
for (auto &s : ans) cout << s << '\n';
}
return 0;
}