1. 项目概述从纸牌游戏到算法挑战24点一个看似简单的纸牌游戏却成了无数程序员入门算法时绕不开的经典练手项目。规则很简单从一副扑克牌中随机抽取4张牌J、Q、K通常视为11、12、13使用加、减、乘、除四种基本运算通过添加括号改变运算顺序使得最终计算结果等于24。这个游戏考验的不仅是心算能力更是对运算优先级和组合可能性的深刻理解。用C来实现它就远不止是“写个计算器”那么简单了它是一次对穷举、递归、表达式解析和数据结构设计的综合演练。我最初接触这个项目是在大学的数据结构课上。当时觉得不就是四个数三个运算符嘛能有多复杂真动手写起来才发现坑一个接一个如何高效地枚举所有数字排列如何无遗漏地生成所有可能的运算顺序即括号组合如何处理除法带来的浮点数精度问题如何优雅地输出人类可读的表达式而不是一堆逆波兰式这些问题恰恰是24点算法从“玩具代码”升级为“工业级练习”的关键。对于正在学习C、准备面试尤其是那些常问“八股文”和算法题的岗位、或者想用VSCode/Visual Studio做个有趣小项目的朋友来说彻底吃透这个项目其价值远超实现功能本身。它能帮你巩固STL容器如vector,set、理解递归与回溯的精髓、练习字符串处理并深刻意识到浮点数比较中的“陷阱”。接下来我就结合自己踩过的坑和优化心得带你从零开始用C构建一个健壮、高效且可扩展的24点求解器。2. 核心算法思路穷举法的艺术与科学实现24点算法的核心毫无争议是穷举法但“怎么穷举”却大有学问。最笨的办法是暴力枚举所有数字、运算符和括号的组合但那样计算量会爆炸。我们需要一个系统性的、无遗漏且避免大量重复计算的策略。2.1 核心思路分治与递归主流且清晰的思路是采用分治递归的策略。将4个数字的求解问题逐步化简为更小规模的问题从4个数中任选两个数用加、减、乘、除四种运算符连接得到一个中间结果。将这个中间结果和剩下的两个数组成一个新的3个数集合。对这个新的3个数集合重复步骤1任选两个数进行运算得到一个新的2个数集合。最后对这两个数进行运算检查结果是否等于24考虑精度。在整个过程中需要记录下每一步的运算表达式。这个递归过程天然地涵盖了所有可能的运算顺序即括号组合。例如对于数字(a, b, c, d)先算ab得到e再算e*c得到f最后算f/d对应的表达式就是((ab)*c)/d。2.2 关键考量排列、组合与去重这里有几个必须处理的细节数字的全排列数字[1, 2, 3, 4]和[4, 3, 2, 1]在运算中是不同的因为减法和除法不满足交换律。因此我们不能只固定数字顺序必须枚举所有可能的排列Permutation。C中可以使用std::next_permutation来优雅地实现。运算符的重复组合三个运算位置每个位置有4种运算符可选所以是4^3 64种组合。可以用三层循环或递归来枚举。运算的合法性除法运算时除数不能为0在浮点数比较中通常判断其绝对值是否小于一个极小的数如1e-6。此外因为中间结果可能是浮点数后续运算也必须用浮点数进行。表达式去重由于加法和乘法满足交换律ab和ba在数学上是等价的但我们的算法可能会生成两者。我们需要一种方法来识别并去重例如通过规范化表达式如确保数字按某种顺序出现或使用std::set存储结果字符串。注意很多初学者会试图直接枚举所有可能的带括号的表达式字符串这是一个复杂度极高且容易出错的方法。递归分治是更优雅、更接近问题本质的数学模型。2.3 算法复杂度浅析假设有n个数本题n4。数字排列数n! 24。运算符组合数4^(n-1) 64。递归过程中选择两个数的方式也有多种。粗略估算总的计算量在万次级别对于现代计算机来说瞬间即可完成这也解释了为什么这个算法是可行的。但如果数字增多如6个数字算24点穷举法就会面临挑战可能需要引入剪枝等优化策略。3. 详细设计与实现步骤有了清晰的思路我们就可以开始动手编码了。我将项目分解为几个核心模块并会给出关键代码和解释。3.1 数据结构与工具函数设计首先我们需要定义一些核心的数据类型和工具函数。#include iostream #include vector #include cmath #include algorithm #include string #include set const double TARGET 24.0; const double EPSILON 1e-6; // 用于浮点数比较的精度阈值 // 工具函数判断两个浮点数是否相等考虑精度 bool isZero(double x) { return std::fabs(x) EPSILON; } // 工具函数判断两个浮点数是否相等用于比较结果和24 bool isEqual(double a, double b) { return std::fabs(a - b) EPSILON; }这里的关键是EPSILON。由于浮点数计算有精度损失直接使用比较(1.0/3.0)*3.0和1.0可能会失败。我们必须定义一个允许的误差范围。3.2 递归求解函数这是整个算法的核心引擎。函数接收一个存储数字和对应表达式的向量尝试所有合并可能递归求解。bool solve24(std::vectorstd::pairdouble, std::string nums, std::setstd::string solutions) { int n nums.size(); if (n 1) { // 递归终点只剩一个数判断是否等于24 if (isEqual(nums[0].first, TARGET)) { solutions.insert(nums[0].second); // 存储有效表达式 return true; } return false; } bool found false; // 枚举所有可能的数字对 (i, j) for (int i 0; i n; i) { for (int j i 1; j n; j) { double a nums[i].first; double b nums[j].first; std::string expA nums[i].second; std::string expB nums[j].second; // 生成新的数字和表达式列表用于下一次递归 std::vectorstd::pairdouble, std::string nextNums; for (int k 0; k n; k) { if (k ! i k ! j) { nextNums.push_back(nums[k]); } } // 尝试六种运算ab, a-b, b-a, a*b, a/b, b/a // 注意减法和除法有两种顺序对应不同的表达式 // 加法 nextNums.push_back({a b, ( expA expB )}); if (solve24(nextNums, solutions)) found true; nextNums.pop_back(); // 乘法 nextNums.push_back({a * b, ( expA * expB )}); if (solve24(nextNums, solutions)) found true; nextNums.pop_back(); // 减法 a-b nextNums.push_back({a - b, ( expA - expB )}); if (solve24(nextNums, solutions)) found true; nextNums.pop_back(); // 减法 b-a nextNums.push_back({b - a, ( expB - expA )}); if (solve24(nextNums, solutions)) found true; nextNums.pop_back(); // 除法 a/b (b不能为0) if (!isZero(b)) { nextNums.push_back({a / b, ( expA / expB )}); if (solve24(nextNums, solutions)) found true; nextNums.pop_back(); } // 除法 b/a (a不能为0) if (!isZero(a)) { nextNums.push_back({b / a, ( expB / expA )}); if (solve24(nextNums, solutions)) found true; nextNums.pop_back(); } } } return found; }代码解读与心得nums向量存储的是pairdouble, string不仅记录当前数值还记录生成这个数值的表达式字符串。这是最终能输出可读表达式的关键。递归终点是只剩一个数时判断其是否接近24。在枚举数字对时j从i1开始避免重复计算(i,j)和(j,i)但减法和除法我们仍然考虑了两种顺序因为它们是不同的运算。每次尝试一种运算后将新结果压入nextNums进行递归递归返回后要pop_back()这是经典的回溯操作确保状态正确恢复。除法运算前必须检查除数是否为零isZero。3.3 驱动函数与主流程递归函数准备好了我们需要一个驱动函数来准备初始数据并处理数字的全排列。std::setstd::string get24Solutions(const std::vectordouble numbers) { std::setstd::string solutions; std::vectorstd::pairdouble, std::string startNums; for (double num : numbers) { startNums.push_back({num, std::to_string((int)num)}); // 初始表达式就是数字本身 } // 关键为了覆盖所有数字顺序需要对初始数组进行全排列 std::sort(startNums.begin(), startNums.end()); // 先排序以便next_permutation生成所有排列 do { solve24(startNums, solutions); } while (std::next_permutation(startNums.begin(), startNums.end(), [](const auto a, const auto b) { return a.first b.first; })); // 按数值排序 return solutions; }为什么需要全排列假设输入是[1, 2, 3, 4]。如果不排列我们的递归只会尝试以这个固定顺序为基础的所有运算组合。但(1-2)3*4和4*3(1-2)是不同的顺序后者需要数字4在第一位。std::next_permutation帮我们枚举了所有可能的初始顺序确保无遗漏。3.4 主函数与交互最后一个简单的主函数来完成输入输出。int main() { std::vectordouble input(4); std::cout 请输入4个数字用空格隔开如1 2 3 4: ; for (int i 0; i 4; i) { std::cin input[i]; } auto solutions get24Solutions(input); if (solutions.empty()) { std::cout 这组数字无法计算出24点。 std::endl; } else { std::cout 找到 solutions.size() 种解法 std::endl; for (const auto sol : solutions) { // 去掉最外层可能多余的括号让表达式更简洁 std::string cleanExp sol; if (cleanExp.front() ( cleanExp.back() )) { // 简单判断实际可能需要更复杂的括号匹配检查 cleanExp cleanExp.substr(1, cleanExp.length() - 2); } std::cout cleanExp 24 std::endl; } } return 0; }4. 高级优化与功能扩展一个基础的求解器已经完成。但要让代码更健壮、更高效、更像一个“项目”我们还需要考虑以下方面。4.1 表达式去重与规范化目前的代码使用std::setstd::string存储结果能去除完全相同的表达式字符串。但(ab)c和a(bc)在数学上等价字符串却不同。更彻底的规范化需要构建表达式树将字符串解析成二叉树叶子节点是数字内部节点是运算符。定义排序规则对于加法、乘法节点强制其左子树代表的数值或哈希值小于右子树从而统一ab和ba。树哈希或序列化将规范化后的树转换成一个唯一的字符串或哈希值用于set去重。 这是一个中等难度的挑战涉及递归树比较和哈希函数设计能极大提升对数据结构和算法的理解。4.2 性能分析与剪枝对于4个数当前算法性能足够。但我们可以思考优化提前终止在递归过程中如果中间结果出现无穷大如除以一个极小的数、NaN或者明显不可能得到24例如所有数都很大且相乘远大于24可以提前返回false节省计算资源。记忆化搜索Memoization对于相同的数字集合顺序无关其计算结果可能是相同的。我们可以用一个哈希表缓存(数字集合, 目标值)到bool的结果。但由于数字是浮点数且集合比较成本不低对于n4的情况引入缓存的收益可能不如其开销。这在数字更多时如6个数字算24点会变得非常有用。4.3 支持更多运算符与规则24点有很多变种算法可以轻松扩展支持乘方^在递归尝试运算的地方加入pow(a, b)和pow(b, a)注意指数不能过大以及结果可能为非整数。支持括号外的数字拼接有些玩法允许将1和2拼成12。这需要在递归的每一层除了四则运算增加一个“数字拼接”的选项将两个整数a和b组合成a*10 b如果b在0-9之间。这要求我们区分整数和浮点数并调整表达式生成逻辑。设定不同目标值将TARGET定义为变量即可求解“算N点”问题。4.4 图形化界面GUI集成这是让项目从“命令行工具”升级为“小游戏”的关键一步。你可以选择Qt功能强大跨平台C原生支持适合打造复杂的桌面应用。你可以用QPushButton表示扑克牌QLabel显示表达式和结果。简单的图形库如SFML或SDL2它们更专注于绘图和事件处理适合做更游戏化的界面比如模拟发牌、动画效果。WebAssembly使用Emscripten将你的C核心算法编译成Wasm然后搭配HTML/JavaScript编写界面可以轻松部署到网页上分享。集成思路保持上面的算法核心get24Solutions函数不变。GUI部分负责随机生成或接收用户输入的4个数字。调用算法核心获取解。将解表达式字符串渲染到屏幕上。处理用户交互如“换一组”、“显示答案”。5. 常见问题与调试技巧实录在实际编写和运行过程中你几乎一定会遇到下面这些问题。5.1 浮点数精度问题这是最大的坑没有之一。问题表现理论上应该等于24的表达式程序判断为不等于。例如对于(5 - (1/5)) * 5计算1/50.2,5-0.24.8,4.8*524。但在浮点数中1.0/5.0的结果并非精确的0.2而是一个近似值0.2000000000000000111...导致最终结果可能是23.999999999999996。解决方案如前所述永远不要用直接比较浮点数。使用一个极小的误差范围EPSILON。// 错误做法 if (result 24.0) { ... } // 正确做法 if (std::fabs(result - 24.0) 1e-6) { ... }在我们的代码中isEqual函数封装了这个逻辑。EPSILON的值通常取1e-6或1e-9根据精度要求调整。5.2 递归深度与栈溢出问题表现程序运行崩溃或陷入死循环如果逻辑有误导致递归无法终止。分析与解决对于4个数递归深度最多为3层4-3-2-1完全不可能栈溢出。但如果你的递归逻辑写错了比如没有正确减少数字集合的大小就可能导致无限递归。调试技巧在递归函数入口打印当前数字集合的大小和内容这是最直观的调试方法。5.3 表达式重复输出问题表现控制台输出了大量看起来数学上等价的表达式如((12)3)*4和(1(23))*4。原因我们的算法是基于递归顺序生成表达式字符串的运算结合律的不同导致了字符串形式的差异。当前方案使用std::set可以去除完全相同的字符串但无法处理因结合律、交换律造成的等价表达式。进阶方案如前文“表达式规范化”所述需要实现表达式树的构建和规范化比较。这是一个很好的编程练习但如果你只是需要一种解法当前的去重方式在大多数情况下已经足够清晰。5.4 除零错误问题表现当中间结果作为除数且为0时可能产生inf或NaN导致后续比较出错。解决方案在每次进行除法运算前必须判断除数是否为零使用isZero函数。我们的代码中已经做了这个检查。5.5 使用VSCode/Visual Studio进行调试如果你在配置C环境尤其是VSCode时遇到问题如“error: microsoft visual c 14.0 or greater is required”这通常意味着缺少编译工具链。对于Windows用户最省事的方法是直接安装Visual Studio社区版免费并勾选“使用C的桌面开发”工作负载。它会安装完整的MSVC编译器、调试器和标准库。如果只想用VSCode需要单独安装MSVC Build Tools或MinGW-w64。推荐后者它是一个GCC的Windows移植版。安装后需要在VSCode的c_cpp_properties.json和tasks.json中正确配置编译器路径。对于Mac/Linux用户通常系统自带或可以通过包管理器如apt,brew,yum轻松安装GCC或Clang。调试技巧在递归函数中关键位置设置断点观察nums向量的变化是理解算法流程最有效的方式。可以重点关注递归进入和返回时nums里元素的数量和值是否符合预期。6. 项目总结与延伸思考走完整个实现流程你会发现24点算法项目就像一个微型的算法竞赛题它麻雀虽小五脏俱全。它强迫你严谨地处理浮点数、全面地考虑边界条件、灵活地运用递归和回溯、并设计合适的数据结构来存储中间状态。我个人在多次实现和教学过程中最大的体会是清晰的思路比过早的优化更重要。一开始就想着如何高效去重、如何剪枝很容易把代码写得复杂难懂。正确的做法是先写出一个正确但可能有点“笨”的版本就像本文最初给出的版本让它能跑通输出结果。然后再针对具体问题比如输出太多重复解分析原因逐个击破进行优化和重构。这种“先实现再优化”的迭代式开发在解决更复杂的工程问题时同样适用。这个项目还可以作为起点向多个方向延伸算法方向尝试实现表达式树的规范化与去重挑战自己。工程方向用Qt写一个带计时、计分、历史记录功能的完整24点游戏。算法学习用同样的递归分治思路去尝试解决“括号生成”、“布尔表达式求值”等问题你会发现它们的内核是相通的。最后代码的健壮性来自于对细节的打磨。多测试几组边界数据四个相同的数字、包含1的数字组合、包含大数的组合。看看你的程序是否能正确判断“无解”输出的表达式是否准确无误。当你亲手完成这一切并看到程序飞快地列出所有解法时那种成就感正是编程最纯粹的乐趣之一。