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

1. 项目概述与核心思路24点游戏一个看似简单的纸牌游戏却蕴含着丰富的算法思想和编程技巧。它的规则很简单从一副扑克牌中随机抽取4张牌通常用1到13的数字代表A到K使用加、减、乘、除以及括号将这4个数字组合成一个表达式使得其计算结果恰好为24。这个项目就是用C来实现一个能够自动求解24点问题的计算器。乍一听这像是一个“暴力破解”的问题把所有可能的算式都试一遍不就行了但实际操作起来你会发现这里面的门道很深。首先四个数字的排列顺序有24种4!。其次我们需要在数字之间插入三个运算符每个运算符有4种选择 - * /这就有4^364种组合。再者运算的优先级可以通过括号来改变这就涉及到不同的表达式结构二叉树形态。最后除法运算必须考虑整除和浮点数精度的问题。把这些因素全部组合起来就是一个典型的搜索与回溯问题非常适合用来锻炼算法设计、递归应用以及对C语言特性的掌握。我之所以选择用C来实现一方面是因为C的执行效率高在处理这种需要大量枚举的场景时优势明显另一方面这个项目能很好地串联起C的多个核心知识点标准模板库STL中vector、string、algorithm的使用递归函数的编写与调试浮点数精度的处理以及面向对象思想在组织代码时的应用。对于正在学习C的朋友来说亲手实现一遍远比看十遍理论要来得深刻。这个计算器的核心目标不仅仅是找到一个解而是尽可能找出所有可能的解法并清晰地展示计算过程。它不仅能帮你验证自己的心算结果更能让你直观地看到计算机是如何通过系统性的搜索来解决这类组合问题的。接下来我会从设计思路开始一步步拆解如何用C构建一个健壮、高效的24点计算器。2. 核心算法设计与数据结构选型实现24点计算器的核心在于如何高效、无遗漏地枚举所有可能的表达式。最直观的算法是“穷举法”但如何组织穷举直接影响代码的清晰度和运行效率。经过多次迭代我最终采用了基于递归和深度优先搜索DFS的算法并辅以后缀表达式逆波兰表达式来统一处理和计算。2.1 算法核心递归与深度优先搜索我们的问题可以抽象为给定四个数字和三个待填充的运算符位置我们需要尝试所有数字的排列、所有运算符的组合以及所有可能的运算顺序即括号所代表的运算优先级。一个非常有效的思路是将问题分解每次从当前的数字集合中取出两个数用四种运算符之一进行运算将得到的结果放回集合这样数字集合就减少了一个数。重复这个过程直到集合中只剩下一个数检查这个数是否等于24考虑精度。这个过程天然适合用递归来实现。递归函数设计我们设计一个递归函数solve(vectordouble nums, vectorstring exprs)。其中nums: 当前数字集合存储double类型以支持除法。exprs: 与nums一一对应的表达式字符串集合记录每个数字是如何计算得来的。递归过程基准情况如果nums中只剩下一个数字并且其值在24的误差范围内例如fabs(num - 24) 1e-6则说明找到一组解输出对应的表达式exprs[0]。递归情况使用两层循环从nums中选取两个不同的索引i和ji j。从nums中取出这两个数a和b以及它们对应的表达式exprA和exprB。对于四种运算符 - * /尝试用a和b进行运算。对于每一种运算合法性检查对于减法a - b和b - a是两种不同的情况都需要尝试。对于除法除数不能为0fabs(b) 1e-6同样需要考虑a / b和b / a。构造新集合从原nums和exprs中移除i和j位置的值然后将运算结果及其对应的新表达式如(exprA exprB)加入集合形成新的nums_new和exprs_new。递归调用以新的集合为参数调用solve(nums_new, exprs_new)。回溯尝试完i和j的所有运算后恢复现场继续尝试下一对数字。这个算法本质上是深度优先搜索它系统地尝试了所有可能的二元运算组合顺序相当于枚举了所有可能的二叉树形态。注意这里有一个关键优化点。由于加法和乘法满足交换律ab ba,a*b b*a为了避免生成大量本质上相同的表达式如(12)3和(21)3我们可以在选取i和j时或者在进行运算时做一些限制。例如只尝试a b而不尝试b a前提是我们在递归前已经对数字进行了排序。但这会稍微增加代码复杂度。在初版实现中为了逻辑清晰我们可以先允许重复后续再优化。2.2 数据结构为什么选择vector和stringvectordouble和vectorstring这是存储动态数组的首选。在递归过程中我们需要频繁地增删元素取出两个数放入一个结果。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(vectordouble nums, vectorstring exprs); bool calculate(double a, double b, double result, char op); void findSolutions(const vectordouble numbers); int main() { vectordouble 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(vectordouble nums, vectorstring 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; // 运算非法如除零跳过 } // 构造新的数字集合和表达式集合 vectordouble newNums; vectorstring 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)。这虽然可能导致最终表达式有冗余的外层括号例如((12)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。为了处理减法和除法的非交换性我们有两个选择在solve函数的循环中当运算符是-或/时额外调用一次calculate(b, a, result, op)。修改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 vectordouble numbers) { bool solutionFound false; vectordouble nums numbers; vectorstring 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的副本进行递归 vectordouble currentNums nums; vectorstring 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进行判断。全排列遍历sortdo...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 -stdc11 -o 24point 24point.cpp-stdc11确保支持to_string等C11特性。-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 ... (可能还有其他等价形式)程序输出了多个解法它们本质上都是666624只是加法的结合顺序不同。这印证了我们算法会枚举所有可能的表达式结构。测试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_setstring来存储所有找到的规范化表达式字符串。在输出解之前先检查是否已经存在于集合中。这种方法实现简单但可能无法识别数学上等价但字符串不同的表达式如(ab)c和a(bc)除非我们在存入集合前也对表达式进行标准化展开。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; vectorstring solutions; unordered_setstring solutionSet; // 用于去重 bool calculate(double a, double b, double res, char op); void solveRecursive(vectordouble nums, vectorstring exprs); string normalizeExpression(const string expr); // 表达式规范化函数 public: TwentyFourSolver(double t 24.0, double e 1e-6) : target(t), epsilon(e) {} vectorstring findAllSolutions(const vectordouble numbers); void setTarget(double t) { target t; } };将递归函数、计算函数设为私有成员将状态如目标值、精度、解集合封装在类内部。findAllSolutions作为公共接口。这样主函数会变得非常清晰int main() { TwentyFourSolver solver; vectordouble input {3, 3, 8, 8}; auto results solver.findAllSolutions(input); for (const auto expr : results) { cout expr endl; } return 0; }5.4 可视化与交互界面对于一个完整的“计算器”项目拥有一个图形界面是终极形态。你可以使用Qt成熟的C跨平台GUI框架可以构建出非常专业的桌面应用程序。你可以设计输入框、按钮和一个显示结果的文本框。简单的命令行交互增强即使不涉及GUI也可以让程序支持多次计算、从文件读取多组测试数据、统计成功率等使其更像一个工具。实现这个24点计算器的过程是一次对递归、回溯、浮点数处理、STL应用和问题建模的全面演练。它麻雀虽小五脏俱全。当你能够独立完成它并对其进行扩展和优化时你对C编程和算法思维的理解必定会上一个坚实的台阶。