1. 项目背景与问题定义最近在百炼OJ平台刷算法题时遇到了编号2787的算24问题这是一道经典的递归算法练习题。题目要求给定4个1~13之间的整数通过加、减、乘、除和括号运算判断能否计算出24。看似简单的题目在实际编码时却遇到了不少坑特别是递归终止条件和浮点数精度处理方面。这道题在ACM/ICPC竞赛中属于中等难度考察的是对递归思想的掌握程度以及对边界条件的处理能力。我在第三次尝试时才完全通过所有测试用例期间经历了多次失败和调试。下面就把这个过程中的经验教训整理成错题本希望能帮助到同样在刷题路上的你。2. 算法核心思路解析2.1 问题抽象与数学模型题目可以抽象为给定四个数字a,b,c,d通过二元运算(-*/)和括号组合能否得到结果24。关键在于运算顺序通过括号改变优先级每个数字必须且只能使用一次除法运算必须能整除实际处理时用浮点数近似数学上四个数的运算组合可以归纳为五种基本模式((a b) c) d(a (b c)) da ((b c) d)a (b (c d))(a b) (c d)2.2 递归算法设计要点采用深度优先搜索(DFS)策略递归地尝试所有可能的运算组合。核心递归函数设计需要考虑参数当前剩余数字列表终止条件列表只剩一个数字时判断是否≈24递归过程每次从列表中取出两个数尝试四种运算特别注意浮点数比较要用相对误差法不能直接用。建议设置epsilon1e-6作为误差阈值。3. 具体实现与关键代码3.1 Python实现版本def solve24(nums): if len(nums) 1: return abs(nums[0] - 24) 1e-6 for i in range(len(nums)): for j in range(len(nums)): if i j: continue # 生成剩余数字 remaining [nums[k] for k in range(len(nums)) if k ! i and k ! j] # 尝试四种运算 for op in [,-,*,/]: if op and j i: # 加法交换律去重 continue if op * and j i: # 乘法交换律去重 continue if op / and nums[j] 0: # 除零保护 continue if op : new_num nums[i] nums[j] elif op -: new_num nums[i] - nums[j] elif op *: new_num nums[i] * nums[j] elif op /: new_num nums[i] / nums[j] if solve24(remaining [new_num]): return True return False3.2 关键优化点说明交换律去重加法和乘法满足交换律通过ji的条件避免重复计算除零保护在除法运算前检查分母是否为0浮点精度处理递归终止条件用相对误差而非绝对相等剪枝优化当找到解时立即返回不再继续搜索4. 常见错误与调试记录4.1 浮点数精度陷阱最初版本直接用nums[0] 24作为终止条件导致以下测试用例失败输入3 3 8 8 正确解(8 / (3 - (8 / 3))) 24问题出在中间结果8/3会产生无限循环小数浮点表示不精确。修改为相对误差比较后解决。4.2 运算顺序遗漏第一版代码只考虑了((a b) c) d这一种运算顺序漏掉了其他四种括号组合方式。表现为输入1 5 5 5 正确解(5 - (1 / 5)) * 5 24通过完整枚举五种运算模式解决。4.3 除零异常处理未处理除零情况时遇到以下输入会抛出异常输入1 1 1 1 正确解无解添加除零保护后程序能够正常返回False。5. 测试用例设计建议5.1 必须覆盖的边界情况正好24的情况6 6 6 6 (6*6-6-6)需要使用除法的情况3 3 8 8无解的情况1 1 1 1包含0的情况0 0 0 24大数情况13 13 13 135.2 特殊组合验证非交换律依赖(5 - 1/5)*5多层括号嵌套8/(3-(8/3))减法顺序敏感 (7-(10-7))*66. 算法复杂度分析时间复杂度O(4^3 * C(4,2)*C(3,2)) ≈ O(1000) 空间复杂度O(递归深度) ≈ O(4)虽然理论复杂度较高但由于数字固定为4个实际运行时间完全可以接受。对于n个数字的一般情况复杂度会呈指数级增长。7. 同类问题扩展掌握了这个递归框架后可以解决一系列类似问题算24的变种算36、算100等数字个数变化5个数算120运算符扩展加入平方、开方等运算目标值变化求最接近目标值的解递归算法的核心思想就是通过不断缩小问题规模将复杂问题分解为简单子问题。这道题很好地训练了递归思维和边界条件处理能力。