当前位置：首页 > news >正文

C++实现24点计算器：深度优先搜索与递归算法详解

news 2026/7/31 5:49:04

1. 项目概述与核心思路

24点游戏，一个看似简单的纸牌游戏，却蕴含着丰富的算法思想和编程技巧。它的规则很简单：从一副扑克牌中随机抽取4张牌（通常用1到13的数字代表A到K），使用加、减、乘、除以及括号，将这4个数字组合成一个表达式，使得其计算结果恰好为24。这个项目，就是用C++来实现一个能够自动求解24点问题的计算器。

乍一听，这像是一个“暴力破解”的问题，把所有可能的算式都试一遍不就行了？但实际操作起来，你会发现这里面的门道很深。首先，四个数字的排列顺序有24种（4!）。其次，我们需要在数字之间插入三个运算符，每个运算符有4种选择（+， -， *， /），这就有4^3=64种组合。再者，运算的优先级可以通过括号来改变，这就涉及到不同的表达式结构（二叉树形态）。最后，除法运算必须考虑整除和浮点数精度的问题。把这些因素全部组合起来，就是一个典型的搜索与回溯问题，非常适合用来锻炼算法设计、递归应用以及对C++语言特性的掌握。

我之所以选择用C++来实现，一方面是因为C++的执行效率高，在处理这种需要大量枚举的场景时优势明显；另一方面，这个项目能很好地串联起C++的多个核心知识点：标准模板库（STL）中vector、string、algorithm的使用，递归函数的编写与调试，浮点数精度的处理，以及面向对象思想在组织代码时的应用。对于正在学习C++的朋友来说，亲手实现一遍，远比看十遍理论要来得深刻。

这个计算器的核心目标，不仅仅是找到一个解，而是尽可能找出所有可能的解法，并清晰地展示计算过程。它不仅能帮你验证自己的心算结果，更能让你直观地看到计算机是如何通过系统性的搜索来解决这类组合问题的。接下来，我会从设计思路开始，一步步拆解如何用C++构建一个健壮、高效的24点计算器。

2. 核心算法设计与数据结构选型

实现24点计算器的核心在于如何高效、无遗漏地枚举所有可能的表达式。最直观的算法是“穷举法”，但如何组织穷举，直接影响代码的清晰度和运行效率。经过多次迭代，我最终采用了基于递归和深度优先搜索（DFS）的算法，并辅以后缀表达式（逆波兰表达式）来统一处理和计算。

2.1 算法核心：递归与深度优先搜索

我们的问题可以抽象为：给定四个数字，和三个待填充的运算符位置，我们需要尝试所有数字的排列、所有运算符的组合以及所有可能的运算顺序（即括号所代表的运算优先级）。

一个非常有效的思路是将问题分解：每次从当前的数字集合中取出两个数，用四种运算符之一进行运算，将得到的结果放回集合，这样数字集合就减少了一个数。重复这个过程，直到集合中只剩下一个数，检查这个数是否等于24（考虑精度）。这个过程天然适合用递归来实现。

递归函数设计：我们设计一个递归函数solve(vector<double>& nums, vector<string>& exprs)。其中：

nums: 当前数字集合，存储double类型以支持除法。
exprs: 与nums一一对应的表达式字符串集合，记录每个数字是如何计算得来的。

递归过程：

基准情况：如果nums中只剩下一个数字，并且其值在24的误差范围内（例如fabs(num - 24) < 1e-6），则说明找到一组解，输出对应的表达式exprs[0]。
递归情况：使用两层循环，从nums中选取两个不同的索引i和j（i < j）。
- 从nums中取出这两个数a和b，以及它们对应的表达式exprA和exprB。
- 对于四种运算符（+， -， *， /），尝试用a和b进行运算。
- 对于每一种运算：
  - 合法性检查：对于减法，a - b和b - a是两种不同的情况，都需要尝试。对于除法，除数不能为0（fabs(b) < 1e-6），同样需要考虑a / b和b / a。
  - 构造新集合：从原nums和exprs中移除i和j位置的值，然后将运算结果及其对应的新表达式（如(exprA + exprB)）加入集合，形成新的nums_new和exprs_new。
  - 递归调用：以新的集合为参数，调用solve(nums_new, exprs_new)。
- 回溯：尝试完i和j的所有运算后，恢复现场，继续尝试下一对数字。

这个算法本质上是深度优先搜索，它系统地尝试了所有可能的二元运算组合顺序，相当于枚举了所有可能的二叉树形态。

注意：这里有一个关键优化点。由于加法和乘法满足交换律（a+b = b+a,a*b = b*a），为了避免生成大量本质上相同的表达式（如(1+2)+3和(2+1)+3），我们可以在选取i和j时，或者在进行运算时，做一些限制。例如，只尝试a + b而不尝试b + a，前提是我们在递归前已经对数字进行了排序。但这会稍微增加代码复杂度。在初版实现中，为了逻辑清晰，我们可以先允许重复，后续再优化。

2.2 数据结构：为什么选择`vector`和`string`？

vector<double>和vector<string>：这是存储动态数组的首选。在递归过程中，我们需要频繁地增删元素（取出两个数，放入一个结果）。vector的push_back和erase操作在尾部高效，虽然中间删除不是其强项，但由于我们的数组规模最大为4，性能影响可忽略不计。其线性存储特性也便于我们使用索引进行遍历。
string：用于构建表达式。使用string可以方便地使用+进行拼接，清晰地记录运算过程。在输出最终表达式时，我们通常会给每一步运算加上括号，以确保运算顺序明确，这正是string的用武之地。
algorithm头文件：我们会用到next_permutation函数。虽然我们的递归算法已经涵盖了数字的不同运算顺序，但初始数字的排列不同，也会影响递归搜索的路径。一种更彻底的枚举方式是，先获取4个数字的所有排列（4! = 24种），对每一种排列都执行上述递归搜索。这样可以确保万无一失，代码逻辑也更直观。next_permutation正是生成全排列的利器。

2.3 表达式表示与计算：后缀表达式的优势

在递归过程中，我们直接拼接中缀表达式字符串（如(1 + (2 * 3))）。这种方式直观，但在计算中间结果时，我们需要将字符串解析成值。我们有两种选择：

在递归时，直接对double类型的数字进行运算，并同步构建表达式字符串。这是我们上面采用的方法，计算和表达式构建分离，逻辑清晰。
统一使用表达式树或后缀表达式来管理和计算。

这里我提一下后缀表达式。后缀表达式（例如1 2 3 * +对应中缀1 + (2 * 3)）的最大优点是无须括号，运算顺序唯一，易于用栈来求值。我们可以在递归时，不直接计算数值，而是构建一个后缀表达式列表，在需要判断结果是否为24时，再用一个独立的evaluate函数来计算这个后缀表达式的值。这样做的好处是将“表达式组合”和“表达式求值”完全解耦，evaluate函数可以独立测试，并且可以避免浮点数运算在递归过程中累积误差。对于追求架构清晰和模块化的实现，这是一个值得考虑的方案。但在本文的示例中，我们将采用第一种更直接的方法，以聚焦于核心算法逻辑。

3. 分步实现与关键代码解析

理论说得再多，不如一行代码。接下来，我们进入实战环节，一步步搭建这个24点计算器。我会将完整的程序分解成几个逻辑模块，并详细解释每一部分的作用和编写时的思考。

3.1 程序框架与输入处理

首先，我们搭建程序的基本骨架，处理用户输入。

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; const double TARGET = 24.0; const double EPSILON = 1e-6; // 用于浮点数比较的精度阈值 // 函数声明 bool solve(vector<double>& nums, vector<string>& exprs); bool calculate(double a, double b, double& result, char op); void findSolutions(const vector<double>& numbers); int main() { vector<double> numbers(4); cout << "请输入4个数字（1-13之间，用空格隔开）: "; for (int i = 0; i < 4; ++i) { cin >> numbers[i]; } // 验证输入 for (double num : numbers) { if (num < 1 || num > 13) { cout << "输入数字应在1到13之间。" << endl; return 1; } } cout << "\n正在计算... 所有可能的24点解法如下：\n" << endl; findSolutions(numbers); return 0; }

关键点解析：

EPSILON：这是处理浮点数相等比较的生命线。由于计算机中浮点数的精度问题，(1.0/3.0)*3.0的结果可能不等于1.0，而是一个极其接近1.0的数。直接使用==比较会失败。我们判断两个浮点数a和b是否“相等”的标准是fabs(a - b) < EPSILON。1e-6（即0.000001）是一个常用的经验值。
findSolutions：这是对外的核心接口。它接收初始的4个数字，负责准备数据、调用求解逻辑并控制输出。我们将求解的核心递归过程封装在solve函数中。

3.2 核心递归求解函数`solve`

这是整个程序的心脏，实现了我们之前描述的DFS算法。

bool solve(vector<double>& nums, vector<string>& exprs) { int n = nums.size(); if (n == 1) { // 基准情况：只剩一个数，判断是否等于24 if (fabs(nums[0] - TARGET) < EPSILON) { // 输出时去掉最外层可能多余的括号 string finalExpr = exprs[0]; // 一个简单的优化：如果表达式首尾已经是括号，且是完整的，可以保留。 // 这里为了简洁，直接输出。 cout << finalExpr << " = 24" << endl; return true; // 找到一个解 } return false; } bool found = false; // 遍历所有不同的数字对 (i, j) for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) continue; double a = nums[i], b = nums[j]; string exprA = exprs[i], exprB = exprs[j]; // 尝试四种运算符 for (char op : {'+', '-', '*', '/'}) { // 对于减法和除法，需要考虑顺序，a op b 和 b op a 可能不同 // 我们通过交换a,b和exprA,exprB来模拟，这里先处理 a op b double result; if (!calculate(a, b, result, op)) { continue; // 运算非法（如除零），跳过 } // 构造新的数字集合和表达式集合 vector<double> newNums; vector<string> newExprs; for (int k = 0; k < n; ++k) { if (k == i || k == j) continue; newNums.push_back(nums[k]); newExprs.push_back(exprs[k]); } // 加入运算结果 newNums.push_back(result); // 构建新的表达式，总是加上括号以确保优先级清晰 string newExpr = "(" + exprA + " " + op + " " + exprB + ")"; newExprs.push_back(newExpr); // 递归求解 if (solve(newNums, newExprs)) { found = true; } } // 额外处理：对于减法和除法，显式地交换操作数再试一次 // 因为 calculate 函数内我们固定了 a op b 的顺序 // 所以对于 ‘-‘ 和 ‘/‘，我们需要手动尝试 b op a if (true) { // 这里可以优化，仅对非交换运算符操作 // 为了逻辑完整，我们在这里重新调用calculate，但交换a,b和exprA,exprB // 更清晰的做法是在calculate函数内部处理非交换性，见下一节。 } } } return found; }

代码细节与陷阱：

递归终止条件：n == 1是递归的出口。这里必须使用浮点数比较，fabs(nums[0] - TARGET) < EPSILON。
新集合的构建：这是最容易出错的地方。我们需要创建一个新的newNums和newExprs，包含未被选中的n-2个旧元素，以及1个运算结果新元素。注意循环变量k要跳过i和j。
表达式括号：新的表达式newExpr我们统一用括号包裹(exprA op exprB)。这虽然可能导致最终表达式有冗余的外层括号（例如((1+2)+3)），但保证了在任何运算顺序下，表达式字符串都能正确反映计算顺序，不会产生歧义。输出时可以做一些美化，但求解阶段以正确性为第一要务。
返回值：solve函数返回bool，表示在当前路径下是否找到了解。这个返回值主要用于控制递归流程，当found为true时，我们继续搜索其他解，因为题目要求找出所有解。

3.3 运算执行函数`calculate`

这个函数封装了基本的算术运算，并处理了除零等非法情况。

bool calculate(double a, double b, double& result, char op) { const double ZERO_EPS = 1e-10; // 判断为零的更严格阈值 switch (op) { case '+': result = a + b; return true; case '-': result = a - b; return true; case '*': result = a * b; return true; case '/': if (fabs(b) < ZERO_EPS) { // 除数接近0 return false; } result = a / b; return true; // 扩展点：可以在这里加入乘方、开方等运算 default: return false; } }

关键点：

除零判断：同样使用浮点数比较fabs(b) < ZERO_EPS。这里ZERO_EPS可以比EPSILON更小，因为我们对“零”的判断需要更严格。
参数传递：结果通过引用double& result返回，函数本身返回操作是否成功的布尔值。这种设计清晰地将结果和状态分离。
非交换性处理：当前的calculate只计算a op b。为了处理减法和除法的非交换性，我们有两个选择：
1. 在solve函数的循环中，当运算符是-或/时，额外调用一次calculate(b, a, result, op)。
2. 修改calculate函数或调用逻辑，使其能处理非交换性。一个简洁的方法是：在solve中，不仅遍历运算符，也遍历“有序操作数对”。即，对于选出的(i, j)，我们既尝试nums[i] op nums[j]，也尝试nums[j] op nums[i]。但要注意，加法和乘法交换后是重复的，需要避免。一个常见的实现技巧是，在递归前先对数字排序，然后只考虑i < j的情况，并且在运算符循环中，对减法和除法特殊处理两种顺序。为了保持代码初次实现的清晰度，我们可以先允许生成一些重复的表达式（例如(a-b)和(b-a)都会出现），后续再优化去重。

3.4 驱动函数`findSolutions`与全排列枚举

solve函数假设数字的顺序是固定的。为了找到所有解，我们必须考虑4个数字的所有排列。

void findSolutions(const vector<double>& numbers) { bool solutionFound = false; vector<double> nums = numbers; vector<string> exprs; // 初始化表达式向量，每个数字最初就是它自己 for (double num : nums) { // 将整数转换为字符串，避免显示为“4.000000” if (fabs(num - round(num)) < EPSILON) { exprs.push_back(to_string((int)round(num))); } else { // 理论上输入是整数，但这里保持通用性 exprs.push_back(to_string(num)); } } // 关键：对输入数字进行排序，然后使用next_permutation遍历所有排列 sort(nums.begin(), nums.end()); sort(exprs.begin(), exprs.end()); // 表达式向量需要同步排序 do { // 对于每一种排列，调用solve函数 // 注意：我们需要使用当前排列下的nums和exprs的副本进行递归 vector<double> currentNums = nums; vector<string> currentExprs = exprs; if (solve(currentNums, currentExprs)) { solutionFound = true; } } while (next_permutation(nums.begin(), nums.end()) && next_permutation(exprs.begin(), exprs.end())); // 保持两个向量排列同步 if (!solutionFound) { cout << "这组数字无法计算出24点。" << endl; } }

实现要点：

表达式初始化：exprs初始化为数字对应的字符串。这里做了一个优化：如果数字是整数（如4.0），我们将其转换为"4"而不是"4.000000"，使输出更美观。round函数配合EPSILON进行判断。
全排列遍历：sort+do...while(next_permutation(...))是C++中生成全排列的标准范式。next_permutation会生成当前序列的下一个字典序排列，当所有排列生成完毕后返回false。
排列同步：这是一个极易忽略的bug点！nums排序并产生排列时，exprs必须保持与nums完全相同的顺序变化，因为exprs[i]始终需要对应nums[i]。所以我们需要对exprs也进行同步的排序和排列生成。
副本传递：在do...while循环内，我们将nums和exprs的副本传递给solve函数。因为solve函数会修改传入的向量，如果我们直接传递原向量，它的状态会被破坏，影响下一次排列的迭代。

4. 编译、运行与测试案例

将上述所有代码模块组合在一起，就得到了一个完整的24点计算器程序。我们将其保存为24point.cpp。

4.1 编译与运行

在命令行中，使用g++编译器进行编译：

g++ -std=c++11 -o 24point 24point.cpp

-std=c++11：确保支持to_string等C++11特性。
-o 24point：指定生成的可执行文件名为24point。

运行程序：

./24point

然后根据提示输入四个数字。

4.2 测试案例与结果分析

让我们用几组经典的数字来测试一下。

测试1：经典有解案例6, 6, 6, 6

请输入4个数字（1-13之间，用空格隔开）: 6 6 6 6 正在计算... 所有可能的24点解法如下： (6 + (6 + (6 + 6))) = 24 (6 + ((6 + 6) + 6)) = 24 ((6 + 6) + (6 + 6)) = 24 ((6 + (6 + 6)) + 6) = 24 (((6 + 6) + 6) + 6) = 24 ... (可能还有其他等价形式)

程序输出了多个解法，它们本质上都是6+6+6+6=24，只是加法的结合顺序不同。这印证了我们算法会枚举所有可能的表达式结构。

测试2：涉及多种运算的案例3, 3, 8, 8

输入: 3 3 8 8 输出: (8 / (3 - (8 / 3))) = 24

这是24点游戏中一个著名的“难题”。我们的程序成功找到了这个需要用到除法且运算顺序巧妙的解。

测试3：无解案例1, 1, 1, 1

输入: 1 1 1 1 输出: 这组数字无法计算出24点。

结果符合预期。

测试4：包含浮点数运算的案例5, 5, 5, 1

输入: 5 5 5 1 输出: (5 * (5 - (1 / 5))) = 24

这里1 / 5 = 0.2,5 - 0.2 = 4.8,5 * 4.8 = 24。程序正确处理了浮点数除法。

4.3 当前实现的局限性

表达式去重：如上所述，当前算法会输出大量通过交换律结合律得到的等价表达式。对于追求简洁输出的用户，这是一个需要改进的地方。去重策略可以是在递归过程中，通过规则限制（如对已排序的数字只进行a op b且当op可交换时要求a >= b），或者是在最终输出后，对表达式字符串进行规范化处理后再进行去重。
性能：对于绝大多数4张牌的24点问题，这个算法的速度已经足够快（毫秒级）。但它的时间复杂度是指数级的。如果推广到5张牌或更多，性能会急剧下降。不过，这已经超出了本项目的范围。
表达式美化：输出的表达式包含了所有括号，有时看起来不够简洁。可以编写一个函数，在输出前尝试去除不必要的括号。例如，如果子表达式是单个数字，或者外层运算符的优先级高于或等于内层运算符，则可以省略括号。这是一个字符串解析和语法分析的小课题，可以作为扩展练习。

5. 扩展思考与优化方向

一个基础版本完成之后，我们可以从多个角度对它进行扩展和深化，这不仅能提升程序的实用性，更是极好的C++和算法练习。

5.1 算法优化：剪枝与去重

剪枝（Pruning）：在递归过程中，如果中间结果已经明显不可能达到24，可以提前终止该分支的搜索，节省时间。例如：

如果中间结果大于24很多，并且后续都是乘法或加法（正数），那么结果只会更大，可以剪枝。但减法或除法可能使其变小，所以剪枝条件要谨慎。
更实用的剪枝是避免除零和避免除出非整数（如果限定所有中间结果必须是整数的话，但24点通常允许小数）。在我们的通用解法中，实现剪枝会显著增加代码复杂度，对于4个数字的场景收益不大，但作为一种算法思想值得了解。

表达式去重：这是提升输出体验最直接的需求。一个相对简单有效的去重方法是：

在递归过程中规范化：在构建表达式字符串newExpr时，不直接拼接(exprA op exprB)，而是先对exprA和exprB按某种规则排序。例如，如果运算符op是+或*，我们保证exprA字符串的字典序大于等于exprB（假设exprA和exprB已经是规范化的），然后再拼接。这需要递归地保证所有子表达式都是规范化的。
最终结果哈希去重：用一个unordered_set<string>来存储所有找到的规范化表达式字符串。在输出解之前，先检查是否已经存在于集合中。这种方法实现简单，但可能无法识别数学上等价但字符串不同的表达式（如(a+b)+c和a+(b+c)），除非我们在存入集合前也对表达式进行标准化展开。

5.2 功能扩展：支持更多运算符与规则

24点游戏有很多变种，我们的计算器可以很容易地扩展。

乘方与开方：在calculate函数中添加^（乘方）和sqrt（开平方）运算。注意，乘方不满足交换律，且可能产生复数（如负数的分数次幂），需要增加处理逻辑。开方可以视为一元运算符，这会改变我们递归的结构（从二元运算变为一元运算），需要调整算法。
允许数字拼接：有些玩法允许将两个数字拼接成一个数，如3和3可以拼成33。这需要在递归时，增加一个“拼接”的操作选项，将两个数字a和b组合成a * 10 + b（如果b是个位数）。这大大增加了搜索空间。
设定不同目标值：不只是24，可以允许用户输入一个目标值T，计算如何用四个数字得到T。只需修改代码中的TARGET常量为一个变量即可。

5.3 工程化改进：使用类进行封装

当功能逐渐增多时，面向过程的代码会变得难以维护。我们可以用C++的类来重新组织代码。

class TwentyFourSolver { private: double target; double epsilon; vector<string> solutions; unordered_set<string> solutionSet; // 用于去重 bool calculate(double a, double b, double& res, char op); void solveRecursive(vector<double>& nums, vector<string>& exprs); string normalizeExpression(const string& expr); // 表达式规范化函数 public: TwentyFourSolver(double t = 24.0, double e = 1e-6) : target(t), epsilon(e) {} vector<string> findAllSolutions(const vector<double>& numbers); void setTarget(double t) { target = t; } };

将递归函数、计算函数设为私有成员，将状态（如目标值、精度、解集合）封装在类内部。findAllSolutions作为公共接口。这样主函数会变得非常清晰：

int main() { TwentyFourSolver solver; vector<double> input = {3, 3, 8, 8}; auto results = solver.findAllSolutions(input); for (const auto& expr : results) { cout << expr << endl; } return 0; }