1. 项目概述从纸牌游戏到算法挑战“24点”这个游戏相信很多人小时候都玩过。一副扑克牌随机抽出四张用加、减、乘、除四则运算把牌面上的数字算成24。规则简单却非常考验心算能力和数字敏感度。但今天我们不打算只停留在“心算”的层面。作为一名C开发者我打算把这个游戏变成一个算法项目用代码来“暴力破解”所有可能的解法。这个项目的核心就是实现一个通用的24点算法求解器。给定任意四个数字不限于1-13程序能够自动找出所有可能的运算组合使其结果等于24。这听起来像是一个简单的穷举问题但其中涉及到的细节却相当丰富如何枚举所有数字的排列如何枚举所有运算符的组合如何处理运算的优先级即括号如何避免浮点数计算带来的精度误差如何优雅地输出人类可读的表达式这些都是我们需要一一攻克的难点。通过这个项目我们不仅能重温C的语法和标准库更能深入练习递归、回溯、排列组合、表达式求值等核心算法思想。它像是一个微型的“算法游乐场”麻雀虽小五脏俱全。无论你是想巩固C基础还是为算法面试做准备亦或是单纯享受解决一个经典问题的乐趣这个项目都值得一试。接下来我将带你从零开始一步步拆解并实现一个功能完整、鲁棒性强的C 24点求解器。2. 核心思路与算法设计实现24点算法的核心在于“穷举”所有可能性但如何高效、无遗漏地穷举并优雅地处理运算细节是设计的关键。最直观的思路是回溯法Backtracking这也是力扣第679题“24点游戏”的标准解法思路。不过我们将实现一个更通用、更面向教学的版本。2.1 问题抽象与数学模型首先我们把问题抽象一下。我们有四个操作数a, b, c, d和三个运算符从{, -, *, /}中选取。我们需要找到一种方式用三个运算符将四个操作数连接起来使得整个表达式的值等于24。由于运算符有优先级并且我们可以任意添加括号来改变运算顺序因此可能的表达式结构远不止简单的线性组合((a op1 b) op2 c) op3 d。实际上对于四个数字所有可能的运算表达式结构可以归结为有限的几种二叉树形态。每一种形态对应一种括号的添加方式。经过归纳对于n个数字可能的二叉树形态是卡特兰数。对于4个数字主要有以下5种基本的运算顺序括号添加方式((a op1 b) op2 c) op3 d(a op1 (b op2 c)) op3 da op1 ((b op2 c) op3 d)a op1 (b op2 (c op3 d))(a op1 b) op2 (c op3 d)我们的算法需要覆盖这几种结构。2.2 算法选型递归回溯法我们选择递归回溯法作为核心算法。其基本思想是从四个数字的列表中每次选取两个数字。对这两个数字尝试所有可能的运算加、减、乘、除注意减和除有顺序且除数不能为0。将运算结果放回数字列表替换掉原来的两个数字。此时列表数字个数减1。在新的列表3个数字上递归调用求解过程。如果递归到列表只剩一个数字则判断它是否非常接近24考虑浮点误差。如果是则根据递归路径还原出整个表达式。回溯尝试完一种运算后需要恢复数字列表尝试下一个运算或下一对数字。这个方法的精妙之处在于它通过递归合并数字自然地涵盖了所有可能的运算顺序和括号组合无需显式地枚举那5种二叉树结构。因为无论原始的运算顺序如何最终都会通过两两合并的方式归约为一个数。2.3 关键考量与设计决策在实现回溯算法前有几个关键点必须提前决定精度处理这是核心难点。由于涉及除法结果可能是浮点数。我们不能直接用判断是否等于24。通常的做法是定义一个极小的误差范围EPSILON如1e-6当abs(result - 24) EPSILON时即认为找到解。除零处理当尝试除法运算时必须判断除数是否为零在浮点数比较中是否小于一个极小值。运算的可逆性与去重加法和乘法满足交换律。这意味着对于数字a和bab和ba在结果上是等价的。为了避免生成大量重复的表达式我们可以在选取两个数字时约定一个顺序例如只处理i j的情况但在进行非交换运算减和除时两种顺序a-b和b-a都需要尝试。表达式生成为了最终能输出像(12)*(34)这样的表达式而不仅仅是结果我们需要在递归过程中记录操作步骤。一种高效的方式是不直接存储字符串拼接耗时且内存占用大而是存储一个“表达式树”的节点结构最后再统一生成字符串。基于以上分析我们的算法框架就清晰了。接下来我们将进入具体的实现环节。3. 核心数据结构与工具函数实现在动手写核心回溯函数之前我们需要搭建一些“基础设施”包括表示数字和表达式的数据结构以及一些工具函数。3.1 表达式节点的设计为了能够最终输出表达式我们设计一个ExprNode结构体。它既可以代表一个原始数字也可以代表一个由两个子表达式通过运算符合并而成的中间结果。#include iostream #include vector #include string #include cmath #include algorithm // 定义运算类型枚举 enum class Op { ADD, SUB, MUL, DIV, NUM }; struct ExprNode { double value; // 节点的数值 Op op; // 操作类型如果是数字则为Op::NUM ExprNode* left; // 左子表达式 ExprNode* right; // 右子表达式 // 构造函数用于创建数字节点 ExprNode(double val) : value(val), op(Op::NUM), left(nullptr), right(nullptr) {} // 构造函数用于创建操作符节点 ExprNode(Op opType, ExprNode* l, ExprNode* r, double val) : value(val), op(opType), left(l), right(r) {} // 递归释放内存 ~ExprNode() { delete left; delete right; } // 生成表达式字符串 std::string toString() const { if (op Op::NUM) { // 如果是整数则输出整数形式否则保留小数 if (std::abs(value - std::round(value)) 1e-6) { return std::to_string(static_castint(std::round(value))); } else { // 简单处理实际可格式化输出 return std::to_string(value).substr(0, std::to_string(value).find(.)3); } } std::string leftStr left-toString(); std::string rightStr right-toString(); // 根据运算符生成字符串并处理括号简化版本可能需要更精细的括号逻辑 switch(op) { case Op::ADD: return ( leftStr rightStr ); case Op::SUB: return ( leftStr - rightStr ); case Op::MUL: return ( leftStr * rightStr ); case Op::DIV: return ( leftStr / rightStr ); default: return ; } } };注意这个toString()方法生成的括号是最保守的每个操作都加了括号可能会产生像((12)*(34))这样的结果虽然正确但不够简洁。一个更高级的实现需要根据运算符优先级判断是否需要为子表达式加括号但这会大大增加复杂度。对于教学和功能演示保守的括号策略是可接受的。3.2 工具函数计算与精度比较我们需要一个函数来执行运算并处理除零错误和精度问题。const double EPSILON 1e-6; // 判断两个浮点数是否“相等” bool isEqual(double a, double b) { return std::abs(a - b) EPSILON; } // 执行运算如果运算非法如除零返回false bool applyOp(Op op, double a, double b, double result) { switch (op) { case Op::ADD: result a b; return true; case Op::SUB: result a - b; return true; case Op::MUL: result a * b; return true; case Op::DIV: if (isEqual(b, 0)) { return false; // 除数为零 } result a / b; return true; default: return false; } } // 判断一个数字列表是否包含24的解 bool solve24(std::vectorExprNode* nums, std::vectorstd::string solutions); // 先声明核心函数下一节实现有了这些基础组件我们就可以着手实现最核心的回溯函数了。4. 核心回溯算法的实现与解析这是整个项目的引擎。我们将实现一个递归函数solve24它接受一个ExprNode指针的向量代表当前待合并的数字/表达式并尝试所有可能的合并方式。4.1 递归函数设计与实现bool solve24(std::vectorExprNode* nums, std::vectorstd::string solutions) { // 基准情况如果只剩一个数字检查是否为24 if (nums.size() 1) { if (isEqual(nums[0]-value, 24)) { solutions.push_back(nums[0]-toString()); return true; // 找到一个解 } return false; // 不是24 } int n nums.size(); bool found false; // 枚举所有不同的数字对 (i, j) for (int i 0; i n; i) { for (int j 0; j n; j) { if (i j) continue; // 不能选同一个数字 ExprNode* a nums[i]; ExprNode* b nums[j]; // 枚举所有可能的运算 for (Op op : {Op::ADD, Op::SUB, Op::MUL, Op::DIV}) { // 对于减法和除法需要考虑顺序但我们可以通过交换a,b来覆盖另一种顺序 // 这里我们先尝试 a op b double resultVal; if (!applyOp(op, a-value, b-value, resultVal)) { continue; // 运算非法如除零跳过 } // 创建新的表达式节点 ExprNode* newExpr new ExprNode(op, a, b, resultVal); // 准备新的数字列表移除a和b加入newExpr std::vectorExprNode* nextNums; for (int k 0; k n; k) { if (k i || k j) continue; nextNums.push_back(nums[k]); } nextNums.push_back(newExpr); // 递归求解 if (solve24(nextNums, solutions)) { found true; } // 回溯关键步骤删除newExpr但注意不能删除a和b // 因为a和b是当前层nums中的元素还需要用于后续循环。 // newExpr在递归过程中可能已被加入solution但其字符串已被保存。 // 为了防止内存泄漏我们需要在这里删除它因为本次尝试已经结束。 // 但是如果solution中保存的字符串依赖于这个节点直接删除会有问题。 // 因此更安全的做法是不在此处删除而是在整个求解结束后统一清理。 // 我们修改策略将newExpr从nextNums中移除并删除。 // 实际上因为nextNums是局部变量递归返回后即被销毁我们需要手动删除newExpr。 delete newExpr; // 递归调用后newExpr已无用除非解被记录 // 注意如果解被记录我们其实不应该删除它否则solution里的字符串指针会悬空。 // 这是一个设计矛盾。解决方案是ExprNode的toString()生成完整字符串不依赖后续节点状态。 // 只要toString()在递归返回前被调用并生成了字符串我们就可以安全地删除节点。 // 在我们的设计中solution保存的是字符串副本所以可以删除节点。 } // 对于减法和除法还需要尝试 b op a (即交换顺序) // 但注意加法乘法交换后是相同操作无需重复。 // 减法a-b 和 b-a 不同除法a/b 和 b/a 不同。 // 我们可以在循环中处理但为了清晰这里列出需要额外处理的情况 // 当 op 是 SUB 或 DIV 时除了 a op b还应尝试 b op a。 // 但我们可以通过在外层循环中当op是SUB或DIV时再交换a,b角色计算一次来实现。 // 为了代码简洁我们调整思路在选取i,j时已经覆盖了所有无序对。 // 对于非交换运算我们通过改变applyOp的参数顺序来覆盖两种情况。 // 所以上面的循环已经覆盖了 a op b。对于 b op a我们可以通过交换applyOp的参数来模拟。 // 更简单的方式是在循环内部当op是SUB或DIV时显式地尝试两种顺序。 // 我们重构一下循环 } } // 为了清晰我们将重构后的完整代码放在下一小节。 return found; }上面的代码框架揭示了逻辑但在处理非交换运算和内存管理上有些混乱。让我们重构一个更清晰、正确的版本。4.2 重构后的核心回溯函数bool solve24Helper(std::vectorExprNode* nums, std::vectorstd::string solutions) { if (nums.size() 1) { if (isEqual(nums[0]-value, 24)) { solutions.push_back(nums[0]-toString()); return true; } return false; } int n nums.size(); bool found false; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i j) continue; ExprNode* a nums[i]; ExprNode* b nums[j]; // 尝试所有运算 for (Op op : {Op::ADD, Op::SUB, Op::MUL, Op::DIV}) { // 情况1: a op b std::vectorstd::pairdouble, ExprNode* trials; // 存储(结果, 表达式节点) double result; if (applyOp(op, a-value, b-value, result)) { ExprNode* newExpr new ExprNode(op, a, b, result); trials.emplace_back(result, newExpr); } // 情况2: 对于减法和除法尝试 b op a (如果顺序不同) if (op Op::SUB || op Op::DIV) { // 注意对于SUBb op a 就是 b - a与 a - b 不同。 // 对于DIVb op a 就是 b / a与 a / b 不同。 // 但需要检查除数不为零对于DIVa作为除数 if (op Op::DIV isEqual(a-value, 0)) { // 除数为零跳过 } else { double resultRev; // 注意参数顺序b, a if (applyOp(op, b-value, a-value, resultRev)) { // 创建节点时左右子节点顺序也要对应 b 和 a ExprNode* newExprRev new ExprNode(op, b, a, resultRev); trials.emplace_back(resultRev, newExprRev); } } } // 对本次尝试的每种可能结果进行递归 for (auto trial : trials) { ExprNode* newExpr trial.second; // 构建新的数字列表 std::vectorExprNode* nextNums; for (int k 0; k n; k) { if (k i || k j) continue; nextNums.push_back(nums[k]); } nextNums.push_back(newExpr); // 递归 if (solve24Helper(nextNums, solutions)) { found true; } // 重要递归返回后删除本次创建的表达式节点。 // 因为solution中已经保存了表达式字符串的副本节点可以销毁。 // 如果解被找到该节点已被记录在solution的某个表达式中但那是字符串与节点对象无关。 delete newExpr; } } } } return found; }这个版本更清晰地处理了非交换运算的两种顺序并确保了内存的合理管理。但还有一个问题它可能会生成大量重复的表达式例如(ab)c和(ba)c在数学上等价但我们的算法会视为两个不同的表达式因为选取数字的顺序和构建树的顺序不同。为了提升效率和输出简洁性我们需要考虑去重。4.3 表达式去重优化去重是一个复杂的问题因为等价的表达式形式多样。一个相对简单实用的方法是对最终找到的表达式字符串进行去重。我们在收集解时使用一个std::unordered_setstd::string来过滤重复的字符串。但字符串去重并不完美因为(12)3和1(23)在字符串上不同但结果相同。更彻底的去重需要规范化表达式树比如通过排序对于可交换运算符和比较树结构这属于进阶优化。对于本项目我们采用字符串去重它简单且能过滤掉大量明显重复的解。我们修改入口函数std::vectorstd::string solve24(const std::vectordouble numbers) { std::vectorExprNode* numNodes; for (double num : numbers) { numNodes.push_back(new ExprNode(num)); } std::vectorstd::string rawSolutions; solve24Helper(numNodes, rawSolutions); // 清理初始的数字节点 for (auto node : numNodes) { delete node; } // 字符串去重 std::unordered_setstd::string uniqueSet(rawSolutions.begin(), rawSolutions.end()); std::vectorstd::string solutions(uniqueSet.begin(), uniqueSet.end()); return solutions; }至此算法的核心部分已经完成。接下来我们需要构建一个用户友好的界面来测试它。5. 程序封装、测试与性能考量一个完整的程序不仅要有核心算法还需要有良好的输入输出和错误处理。5.1 主函数与输入处理#include iostream #include vector #include string #include sstream #include unordered_set int main() { std::cout 24点求解器 (输入四个数字用空格分隔输入q退出):\n; std::string line; while (std::cout std::getline(std::cin, line)) { if (line q || line Q) { break; } std::istringstream iss(line); std::vectordouble numbers; double num; while (iss num) { numbers.push_back(num); } if (numbers.size() ! 4) { std::cout 请输入恰好4个数字。\n; continue; } std::cout 正在计算 numbers[0] , numbers[1] , numbers[2] , numbers[3] 的24点解法...\n; auto solutions solve24(numbers); if (solutions.empty()) { std::cout 未找到解法。\n; } else { std::cout 找到 solutions.size() 种解法:\n; for (size_t i 0; i solutions.size(); i) { // 去掉最外层可能多余的括号如果表达式本身已用括号包裹 std::string expr solutions[i]; if (expr.front() ( expr.back() )) { // 简单判断可能不总是准确。更严谨的做法需要解析表达式。 // 这里仅做演示性处理。 std::cout i 1 : expr.substr(1, expr.size() - 2) \n; } else { std::cout i 1 : expr \n; } } } std::cout std::endl; } std::cout 程序结束。\n; return 0; }5.2 编译与运行示例将以上所有代码段整合到一个.cpp文件中例如24point.cpp。使用C编译器进行编译。建议使用C11或更高标准。# 使用g编译 g -stdc11 -o 24point 24point.cpp # 运行程序 ./24point运行示例24点求解器 (输入四个数字用空格分隔输入q退出): 6 6 6 6 正在计算 6, 6, 6, 6 的24点解法... 找到 1 种解法: 1: (6(6(66))) 1 2 3 4 正在计算 1, 2, 3, 4 的24点解法... 找到 42 种解法: 1: (1*(2*(3*4))) 2: (1*((2*3)*4)) 3: (1*(2*(4*3))) ... (以下省略) 1 1 1 1 正在计算 1, 1, 1, 1 的24点解法... 未找到解法。5.3 算法复杂度与性能分析我们的回溯算法会枚举所有可能性。对于4个数字第一次选择有C(4,2)6种数字对选法考虑顺序则是P(4,2)12但我们通过内外循环i, j且i ! j实现了P(4,2)12种有序对。对于每一对数字尝试4种运算对于减法和除法还有两种顺序所以最多有4 2 6种运算尝试实际上加法乘法只有一种顺序但代码中统一处理了。合并后得到3个数字继续递归。递归树的总深度为34-3-2-1。这是一个指数级枚举但因为数字规模很小4所以实际计算量非常小在现代计算机上几乎是瞬间完成。理论上所有可能的表达式树形态是有限的总计算次数是可接受的。性能瓶颈与优化点去重字符串去重和集合操作在解很多时会成为瓶颈。如果只关心是否有解可以在找到第一个解后立即返回。表达式生成toString()递归调用和字符串拼接在深度递归时有一定开销。如果不需要输出表达式只判断是否有解可以大幅提升速度。剪枝可以加入一些启发式规则提前终止不可能的分支。例如在递归过程中如果当前结果已经远远超过24比如大于24*10且后续都是乘法或加法可能就无法回到24了。但剪枝逻辑需要仔细设计避免错误剪掉有效解。对于这个练习项目当前的实现已经足够高效和清晰。6. 常见问题、调试技巧与扩展方向在实际编写和运行过程中你可能会遇到一些问题。这里总结一些常见情况和处理技巧。6.1 浮点数精度问题这是此类问题最棘手的部分。我们使用了EPSILON 1e-6来比较浮点数。但这个值是否合适问题如果运算链很长累积的误差可能会超过1e-6。例如(1.0/3.0)*3.0*8.0理论上等于8但浮点计算可能得到7.999999999。调试如果怀疑是精度问题导致找不到解可以尝试将EPSILON调大例如1e-5。在递归底部打印出最终结果的值观察它与24的差距。考虑使用分数有理数来精确表示所有中间结果。这需要实现一个分数类并重载四则运算可以彻底避免精度问题但代码复杂度会显著增加。实操心得在大多数情况下1e-6对于4个数字、3次运算的精度是足够的。如果遇到极端的数字组合可以尝试1e-5。如果项目要求绝对精确那么实现分数类是唯一的出路。6.2 内存泄漏检查我们的代码中手动new和delete了ExprNode。虽然在小程序中问题不大但良好的习惯是确保所有new都有对应的delete。检查点确保在递归返回后对本次创建的newExpr执行了delete见solve24Helper中循环末尾的delete newExpr。工具在Linux/macOS下可以使用valgrind在Windows下可以使用Visual Studio的内存诊断工具来检测内存泄漏。现代C改进可以使用std::unique_ptrExprNode来管理节点内存让智能指针自动处理释放代码更安全。但这需要修改数据结构和函数签名。6.3 表达式输出不美观我们的toString()方法会给每个操作都加上括号导致输出像((12)*(34))。优化实现一个更智能的toString()根据运算符优先级决定是否添加括号。规则如下当前节点运算符为ADD或SUB如果左子节点运算符是MUL或DIV则需要给左子表达式加括号。如果右子节点运算符是MUL或DIV或者右子节点运算符是SUB对于当前节点是ADD时或ADD/SUB对于当前节点是SUB时则需要给右子表达式加括号。当前节点运算符为MUL如果左子节点运算符是DIV则需要给左子表达式加括号。如果右子节点运算符是DIV则需要给右子表达式加括号。当前节点运算符为DIV如果左子节点运算符是ADD或SUB则需要加括号。右子表达式几乎总是需要加括号除非它是一个单独的数字因为a/(b*c)和a/b*c不同。建议初次实现可以不考虑这个优化优先保证功能正确。美观化输出可以作为一项有趣的扩展练习。6.4 项目扩展方向这个基础项目有很多可以扩展和深化的方向支持更多数字和运算符修改程序使其能处理任意N个数字目标值为M。运算符可以扩展乘方、开方等。图形化界面GUI使用Qt、SFML或甚至控制台图形库做一个交互式的24点游戏。Web后端将算法封装成REST API用FlaskPython或Spring BootJava提供Web服务前端输入数字后端返回所有解。算法竞赛优化针对LeetCode 679题实现一个只返回布尔值是否有解的版本专注于极致的性能优化和剪枝。表达式树可视化将找到的解法表达式树用Graphviz等工具生成图片直观展示运算结构。实现这个24点求解器的过程是一次对递归、回溯、浮点数处理、表达式管理和C面向对象编程的全面练习。它从一个小游戏出发触及了算法设计与实现的多个核心层面。希望这份详细的解析和实现指南能帮助你不仅完成代码更理解其背后的每一个设计决策和潜在陷阱。
