24
24
点游戏的算法
点游戏的算法
任务说明
24 点游戏是一个大众化的益智游戏。任意给 4 个整数数，只能够用加、减、
乘、除以及适当的括号连接这四个数，无论顺序，使计算结果为 24 ，或者宣布
根本就是无解的。需要注意的是，每个数必须运算，并且只能运算一次。
二、算法说明
接下来是 24 点算法的讨论。首先想到的是用穷举表达式的方法，然后求值。
然而，由于括号的存在，使穷举表达式并非易事。实际上，括号的作用仅仅是
提高运算的优先级而已，如果我们规定符号的优先级，一样可以达到要求。具
体来说，设四张牌为 a、b、c、d，运算符为①、②、③，表达式为 a ① b ② c
③ d。如果强制规定①、②、③的优先顺序，就不必考虑括号问题了。而这 3
个运算符的运算顺序有 3！=6 种，分别是：
1．①②③ 2.①③② 3.②①③ 4.②③① 5.③①② 6.③②①
等价的表达式分别是：
1.((a①b②)c③) 2.(a①b)②(c③d) 3.(a①(b②c))③d
4.a①((b②c)③d) 5.(a①b)②(c③d) 6. a①(b②(c③d))
显然，2 和 5 是相同的，因此只考虑 5 种情况。这样，括号的问题就解决
了。
接下来，就是生成 a、b、c、d 的全排列，注意去掉其中的相同排列。去除
的方法很多，比如字典排序等，我用的是另一种方法。
用循环的嵌套生成 a、b、c、d 的 24 种全排列，记录在数组中。把每一组数
当 作 一 个 四 位 的 14 进 制 数 ， 把 这 24 个 数 全 部 转 化 为 十 进 制 （ 如
（6529）
14
=6*14
3
+5*14
2
+2*14+9）。这样，如果两个排列完全相同，则得到的
十进制数是相等的。这样，通过对这些十进制的比较，就可以比较这些排列的
相同情况。一旦遇到相同的排列，就标记上。最后生成一组没有重复的排列。
对这组排列进行以上方法的运算，就可以得到所有的结果了。注意在运算
过程中除法的特殊性——除数不能为零。因为可能会用到除法，所以要考虑精
度问题，这里通过结果减去 24 取绝对值与一个接近 0 的小数比较，如小于它，
即可判定结果是 24。
1
