1. 项目概述从纸牌游戏到算法挑战算24点一个很多人童年都玩过的纸牌游戏。规则很简单从一副扑克牌中随机抽取4张牌J、Q、K通常代表11、12、13使用加、减、乘、除四种基本运算通过合理的组合和括号使得这四个数字的运算结果等于24。这个游戏看似简单却蕴含着丰富的数学逻辑和算法思想。它考察的不仅仅是心算能力更是对数字敏感度、运算优先级括号和问题求解策略的综合运用。今天我们不满足于手动凑数而是要挑战用C来自动化解决这个问题。这不仅仅是一个编程练习更是一个绝佳的算法设计实战场景。它涉及的核心技术点包括穷举搜索策略的设计、表达式树的构建与遍历、浮点数精度处理、以及C标准库STL的灵活运用。对于学习C和算法的朋友来说实现一个高效的24点求解器能让你深刻理解递归、回溯、容器操作和面向对象设计。网络上能找到的许多代码要么逻辑混乱要么效率低下要么对括号的处理有缺陷。我将带你从零开始设计一个结构清晰、功能完备、且能输出所有可能解法的C程序并深入分析每一步的设计考量与源码细节。2. 核心算法设计与思路拆解2.1 问题本质与求解策略分析算24点的核心是一个表达式枚举问题。给定四个操作数a, b, c, d和四个运算符 - * /我们需要枚举所有可能的运算顺序和组合方式。这里最大的难点在于运算的优先级和括号。括号改变了默认的“先乘除后加减”的优先级使得操作数可以以不同的分组方式进行运算。例如对于数字 3, 3, 8, 8一种解法是8 / (3 - 8/3)。这里的括号至关重要。因此我们不能简单地枚举运算符排列。更通用的思路是将四个数字视为叶子节点运算符视为中间节点构建所有可能的二叉树结构每一棵树都代表一种运算顺序即隐含了括号。然后我们遍历所有树计算其值是否接近24。策略选择递归分治与回溯最直观的策略是递归分治。基本思想是从4个数字的集合中每次任选两个数字用四种运算符进行组合得到一个结果。这个结果和剩下的数字组成一个新的、数量减一的集合。然后对这个新集合重复上述过程直到集合中只剩下一个数字。检查这个数字是否等于24考虑浮点误差。这个过程天然地对应了二叉树的后序遍历先计算子树再计算根节点。2.2 数据结构与工具选型为了高效实现上述算法我们需要选择合适的C工具。数字表示double由于涉及除法结果可能是小数如8 / (3 - 8/3)所以必须使用浮点数。double类型提供了足够的精度和范围。集合管理std::vectordouble我们需要一个动态容器来存放当前待计算的数字集合。std::vector支持高效的随机访问、插入和删除在尾部非常适合我们这个需要频繁遍历和修改集合的场景。相比原生数组它更安全、更灵活。递归与回溯的实现递归函数是算法的核心。我们需要一个函数接收一个vectordouble作为当前数字集合对其进行操作。在尝试了每一对数字和每一种运算后我们需要恢复现场回溯以便尝试其他可能性。这里直接在递归调用前创建集合的副本是最清晰、不易出错的做法虽然有一定空间开销但对于最多4个数字的规模来说完全可以接受。表达式记录std::string除了计算结果我们通常还想知道具体的解法表达式。这就需要我们在递归计算的同时构建对应的表达式字符串。一个技巧是使用另一个vectorstring与数字向量并行记录每个数字对应的原始表达式初始时为数字字符串在运算时同步组合新的表达式。2.3 精度处理与去重策略浮点数精度问题这是数值计算中的经典问题。(1.0 / 3.0) * 3.0在数学上等于1但在double运算中可能等于0.9999999999。因此我们不能直接用result 24来判断而应该判断fabs(result - 24) EPSILON其中EPSILON是一个极小的正数比如1e-6。解法去重由于加法和乘法满足交换律ab与ba等价我们的递归枚举会产生大量本质上相同的表达式。例如对于数字[1, 2, 3, 4](12)(34)和(34)(12)会被枚举为不同的路径但它们是同一种解法。为了提升输出质量我们需要进行去重。 一个简单有效的去重方法是使用std::setstd::string来存储找到的表达式字符串。在输出前对表达式进行规范化处理比如通过排序消除交换律的影响后再存入集合可以自动过滤重复项。但更精细的去重涉及表达式树的规范化比较实现较为复杂。在基础版本中我们优先保证找到所有解去重可以作为优化项后续添加。3. 核心源码实现与逐行解析接下来我们进入具体的代码实现环节。我将分模块构建这个24点求解器并详细解释每一行代码的意图和背后的原理。3.1 基础框架与常量定义首先我们包含必要的头文件并定义全局常量。#include iostream #include vector #include string #include cmath #include set // 用于解法去重 const double EPSILON 1e-6; // 浮点数比较精度阈值 const double TARGET 24.0; // 目标值 using namespace std; // 为简化示例代码此处使用。大型项目建议显式指定。cmath提供fabs函数用于计算浮点数的绝对值。EPSILON是精度阀值所有与目标值的比较都应通过fabs(val - TARGET) EPSILON进行。使用using namespace std;在小型示例中方便但在实际项目中更推荐使用std::前缀以避免命名冲突。3.2 核心递归函数solve24的设计这是整个程序的心脏。函数接收当前数字列表和对应的表达式列表递归地尝试所有组合。// nums: 当前数字集合 // exprs: 与nums一一对应的表达式字符串集合 // solutions: 用于收集所有成功解法的集合 void solve24(vectordouble nums, vectorstring exprs, setstring solutions) { int n nums.size(); // 递归基如果只剩一个数字检查是否等于24 if (n 1) { if (fabs(nums[0] - TARGET) EPSILON) { solutions.insert(exprs[0]); // 找到一个解存入集合自动去重 } return; } // 枚举所有可能的数字对 (i, j) for (int i 0; i n; i) { for (int j 0; j n; j) { if (i j) continue; // 不能选同一个数字 double a nums[i]; double b nums[j]; string expA exprs[i]; string expB exprs[j]; // 创建新的数字集合和表达式集合用于下一次递归 vectordouble nextNums; vectorstring nextExprs; // 将未被选中的数字和表达式加入新集合 for (int k 0; k n; k) { if (k ! i k ! j) { nextNums.push_back(nums[k]); nextExprs.push_back(exprs[k]); } } // 尝试四种运算 // 1. 加法 a b nextNums.push_back(a b); nextExprs.push_back(( expA expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); // 回溯 nextExprs.pop_back(); // 2. 减法 a - b nextNums.push_back(a - b); nextExprs.push_back(( expA - expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); // 3. 减法 b - a (减法不满足交换律是两种不同操作) nextNums.push_back(b - a); nextExprs.push_back(( expB - expA )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); // 4. 乘法 a * b nextNums.push_back(a * b); nextExprs.push_back(( expA * expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); // 5. 除法 a / b (需判断除数不为零) if (fabs(b) EPSILON) { // 避免除零错误 nextNums.push_back(a / b); nextExprs.push_back(( expA / expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); } // 6. 除法 b / a if (fabs(a) EPSILON) { nextNums.push_back(b / a); nextExprs.push_back(( expB / expA )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); } } } }关键点解析递归基Base Case当nums中只剩一个数字时判断是否接近24。这是递归的终点。双重循环枚举数对for (int i 0; i n; i)和for (int j 0; j n; j)枚举了所有可能的数字对(nums[i], nums[j])。if (i j) continue确保不重复使用同一个数字。创建新集合nextNums和nextExprs用于存放“未被选中的数字/表达式”以及“运算产生的新数字/表达式”。这是实现回溯的关键每次递归调用都基于一个全新的集合副本调用结束后该副本的生命周期结束自然回溯到父调用的状态。我们通过pop_back()显式地移除尝试过的运算结果再尝试下一个运算这是一种清晰的回溯写法。六种运算尝试注意减法和除法不满足交换律因此a-b和b-a、a/b和b/a是两种不同的运算必须分别尝试。对于除法必须检查除数是否为零使用fabs(b) EPSILON。表达式构建每次运算不仅计算新的数字ab还构建对应的新表达式“(” expA “” expB “)”。括号是必须的它保证了表达式在字符串形式下能正确反映运算顺序。即使对于加法这种优先级明确的运算加上括号也能使表达式树的结构一目了然便于后续去重或优化。注意性能与冗余这个枚举方式包含了大量的重复计算。例如对于[a, b, c, d]先合并(a,b)再合并(c,d)与先合并(c,d)再合并(a,b)最终可能得到相同的表达式树。这是该算法产生重复解的根本原因。在基础版本中我们接受这种冗余并通过std::set在最后过滤重复的表达式字符串。3.3 辅助函数与主程序入口我们需要一个函数来启动求解过程并处理用户输入。// 主求解函数对外接口 setstring calculate24(vectordouble numbers) { setstring solutions; vectorstring expressions; // 初始化表达式向量将数字转为字符串 for (double num : numbers) { // 如果是整数去掉小数部分显示更美观 if (fabs(num - round(num)) EPSILON) { expressions.push_back(to_string((int)round(num))); } else { // 实际情况中初始数字都是整数所以这部分可能用不到 expressions.push_back(to_string(num)); } } solve24(numbers, expressions, solutions); return solutions; } int main() { cout 请输入4个数字用空格隔开如3 3 8 8: ; vectordouble nums(4); for (int i 0; i 4; i) { cin nums[i]; } setstring result calculate24(nums); if (result.empty()) { cout 这组数字无法计算出24点。 endl; } else { cout 找到 result.size() 种解法 endl; int count 1; for (const string sol : result) { cout count : sol endl; } } return 0; }代码细节calculate24函数是封装好的接口。它初始化表达式字符串向量将数字转为字符串调用核心递归函数solve24并返回存储所有不重复解法的集合。在初始化表达式时我们做了一个小优化如果数字非常接近整数比如输入的3、8我们使用to_string((int)round(num))将其转换为没有小数点的字符串如“3”使最终输出的表达式更简洁(33)*(8-4)而不是(3.0000003.000000)*(8.000000-4.000000)。main函数负责简单的I/O读取用户输入的4个数字调用求解函数并格式化输出结果。4. 算法优化与深度探讨基础版本虽然能工作但在效率和输出质量上都有提升空间。我们来探讨几个关键的优化方向。4.1 避免重复枚举的剪枝策略当前的算法对(i, j)和(j, i)进行了重复枚举。实际上对于加法和乘法(i, j)和(j, i)在数字层面是等价的。我们可以通过限制j i来避免一半的组合检查。for (int i 0; i n; i) { for (int j i 1; j n; j) { // 修改这里j 从 i1 开始 // ... 原有的取 a, b, expA, expB 的代码 ... // 将未被选中的数字加入新集合 for (int k 0; k n; k) { if (k ! i k ! j) { nextNums.push_back(nums[k]); nextExprs.push_back(exprs[k]); } } // 尝试加法ab (因为 ji这里只尝试一种顺序) nextNums.push_back(a b); nextExprs.push_back(( expA expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); // 尝试乘法a*b nextNums.push_back(a * b); nextExprs.push_back(( expA * expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); // 尝试两种减法和两种除法它们不满足交换律仍需两种 // 减法 a-b nextNums.push_back(a - b); nextExprs.push_back(( expA - expB )); solve24(nextNums, nextExprs, solutions); // ... 其他运算类似 ... } }优化效果这个简单的剪枝将数字对的枚举组合从n*n减少到C(n,2)组合数对于n4从16对减少到6对显著减少了递归调用的入口次数。但注意减法和除法仍需两种顺序因为a-b和b-a不等价。4.2 表达式树的规范化与高效去重使用std::setstring进行字符串去重是一个“事后”策略且依赖于字符串形式。更根本的方法是在构建表达式树的过程中进行规范化避免生成等价的树。表达式树的概念我们可以将每一个运算步骤看作一个二叉树节点。叶子节点是原始数字内部节点是运算符。(ab)*(c-d)对应的树结构是*为根左子树是节点子节点为a, b右子树是-节点子节点为c, d。规范化规则交换律对于加法和乘法*节点我们可以强制规定左子节点的值或表达式小于右子节点按字典序或数值序。这样ab和ba会被规范化为同一种结构。结合律对于连续的同级运算如(ab)c和a(bc)可以通过固定结合顺序如左结合来规范化。但这在递归分治算法中较难实现因为我们的算法天然生成的是二叉树。实现一个完整的表达式树规范化比较器需要自定义树节点结构并实现递归的比较函数。这超出了基础教程的范围但它是构建工业级符号计算库的基础。对于24点游戏字符串去重在大多数情况下已经足够好用。4.3 性能分析与可能的改进我们的算法时间复杂度是指数级的但对于固定的4个数字计算量是有限的。递归树的深度最大为34-3-2-1每一层的分支因子可能的运算选择是C(m,2) * 6m为当前数字个数。粗略估算最坏情况下的运算尝试次数在万次级别现代计算机可以在毫秒内完成。进一步优化思路记忆化Memoization对于相同的数字集合不考虑顺序其计算结果可能是相同的。我们可以设计一个哈希函数将排序后的数字集合映射到一个缓存unordered_map存储该集合是否已被证明无法得到24或者能得到24的所有表达式。这可以避免重复计算子问题。但由于数字是浮点数且集合很小实现高效且正确的哈希比较麻烦收益不一定高。提前剪枝在递归过程中如果当前中间结果已经明显不可能达到24例如数字太大且都是乘法或太小且都是加法可以提前终止该分支。但这需要设计启发式规则实现复杂且可能剪掉有效解因为除法和减法可以大幅改变数值需谨慎使用。5. 常见问题排查与实战技巧在实际编码和运行过程中你可能会遇到以下问题。这里给出我的排查经验和解决方案。5.1 浮点数精度导致的“无解”误判问题现象对于明显有解的数字组合如 3, 3, 8, 8程序输出“无解”。排查步骤首先检查EPSILON的值。如果设置得太小如1e-12可能会因为累积误差导致判断失败。通常1e-6是一个比较安全的选择。在递归函数中在判断n1时添加调试输出打印当前的nums[0]值。观察其与24的差距。if (n 1) { cout [DEBUG] Final value: nums[0] endl; // 调试语句 if (fabs(nums[0] - TARGET) EPSILON) { solutions.insert(exprs[0]); } return; }你可能会发现某个中间结果比如8.0 / (3.0 - (8.0/3.0))计算出来的值不是24而是23.99999999999999。这就是浮点误差。确保所有比较都使用了fabs(a-b) EPSILON而不是。5.2 递归深度过大或栈溢出问题现象程序运行崩溃或陷入疑似死循环。原因分析我们的算法递归深度最大为3不可能导致栈溢出。如果出现此问题可能是递归逻辑有误导致无法到达基态n1。检查点确保在每次递归调用时nextNums的大小比当前的nums小1。你可以在递归开头打印nums.size()来观察。检查除法运算的除数零判断if (fabs(b) EPSILON)是否遗漏。如果除数为零时仍然进行了递归可能会产生inf或nan导致后续计算异常。5.3 输出表达式冗余或可读性差问题现象解法太多且很多看起来是重复的比如((12)3)4和(1(23))4。解决方案使用set去重这是最基本也是最有效的方法如我们代码所示。优化表达式生成可以为加法和乘法节点实现规范化不生成交换律下的重复表达式。这需要修改递归函数在构建表达式字符串时对于加法和乘法强制按某种规则如字符串字典序排列expA和expB。string newExpAdd; if (expA expB) { // 按字典序排序 newExpAdd ( expA expB ); } else { newExpAdd ( expB expA ); } nextExprs.push_back(newExpAdd);这能消除一部分因交换律产生的重复。对于结合律产生的重复则需要更复杂的树结构比较。5.4 扩展支持更多运算符或数字需求如何修改代码来计算5个数字的24点或者增加乘方^运算符修改方法更多数字只需修改main函数中输入的数字个数以及递归基的判断条件。算法本身是通用的。但要注意数字个数增加会带来组合爆炸递归深度和分支因子剧增可能需要更强的剪枝或启发式搜索。更多运算符在递归函数中增加新的运算分支即可。例如增加乘方// 乘方 a^b // 注意需处理0^0、负数指数等边界情况这里简化处理 if (a 0 || (fabs(b - round(b)) EPSILON int(round(b)) % 2 0)) { // 粗略判断底数非负或指数为偶数避免复数或未定义 double powResult pow(a, b); if (!isinf(powResult) !isnan(powResult)) { nextNums.push_back(powResult); nextExprs.push_back(( expA ^ expB )); solve24(nextNums, nextExprs, solutions); nextNums.pop_back(); nextExprs.pop_back(); } }增加运算符会显著增加解的空间也可能产生更多无效分支如结果溢出需要仔细处理边界条件。通过这个项目我们不仅实现了一个有趣的游戏求解器更实践了递归、回溯、浮点数处理、STL容器应用等核心编程技能。最重要的是我们经历了从问题分析、算法设计、代码实现到调试优化的完整开发流程。你可以尝试在此基础上继续打磨比如实现一个带图形界面的24点游戏或者将算法封装成类使其更加健壮和易用。编程的乐趣就在于这种将想法一步步变为现实的过程。