24点算法，如何给出所有不同的答案

问题描述

问 题

比如 2，4，6，Q(12) 这4个数，可能的答案有：

2 + 4 + 6 + 12 = 24
4 × 6 ÷ 2 + 12 = 24
12 ÷ 4 × (6 + 2) = 24

但要过滤掉雷同的答案，比如：

(12 + 6) + (4 + 2) = 24 (用交换律、结合律给出的不同答案是雷同的)
12 + 6 ÷ 2 * 4 = 24 (加减法或乘除法顺序颠倒)

还有无用的数怎么组合都是雷同的，比如：4，5，5，6 这四个数，以下两个答案只能算一个：

4 * 6 + 5 - 5 = 24
4 * 6 * 5 / 5 = 24

感觉挺复杂的，一时想不到一个好办法来处理。

补充

搜到一个算24点的页面：http://www.dffyw.com/tool/24.htm ，但是它会把所有的雷同情况都列出来，比如输入 2，4，6，12 这4个数，会有394种答案，其实不同的答案并没多少。

再补充

我自己穷举了下，2，4，6，12应该有以下10种不雷同的解答：

12+(6+(3*2))=24
(6*(3*2))-12=24
3*(12-(6-2))=24
6+(12*(3/2))=24
(2*(12+3))-6=24
12+(3*(6-2))=24
(3*(12-2))-6=24
6+(2*(12-3))=24
(12/2)+(6*3)=24
(12*3)-(6*2)=24

应该没有更多的吧。

再补充

带1和2的情况要特殊考虑，例如：A、J、K、Q

12*((13*1)-11)=24
12*((13/1)-11)=24

用1来做乘除法时，属于雷同的解答。又例如：2、2、3、3

(2+2)*(3+3)=24
2*2*(3+3)=24

2+2和2*2应被视为雷同的步骤。

解决方案

题主所说的雷同，可以理解为用字母替换数字后得到的代数式等价。也就是说，当得到一个24点算式后，把它用代数变换导出的所有算式均不视为新发现。比如：

算式	对应代数式	雷同？
4 × 6 ÷ 2 + 12 = 12 + 6 ÷ 2 × 4	$$a\ b / c + d = d + \frac{b}{c} a$$	雷同
4 × 6 + 5 - 5 = 4 × 6 × 5 / 5	$$a\ b + c - c = a\ b\ c / c$$	雷同
12 ÷ 4 × (6 + 2) = 4 × 6 ÷ 2 + 12	$$\frac{a}{b}(c + d) \ne b\ c / d + a$$	不雷同

因此得到算法：

1. 构造所有的数字算式

2. 筛选出计算结果是24的算式

3. 将算式中的数字用符号替换，并对得到的代数式做等价判断，每个等价类选出一个代表

4. 输出代表代数式对应的数字算式

这种穷举构造法的复杂度至少是指数级的，因此不适用于数字较多的情况。

Mathematica 实现

Mathematica 的符号代数功能非常适合处理这类题目。

Clear[game24]
game24[input_List, result_: 24] := Block[{add, sub, mul, div},
  With[{
    oprules = {add -> Plus, sub -> Subtract, mul -> Times, 
      div -> Divide},
    specifics = {div[x_, 1] :> x, mul[x_, 1] :> x, mul[1, x_] :> x, 
      add[2, 2] -> mul[2, 2]}},
   Map[RightComposition[
     Hold, ReplaceAll[oprules], ToString[#, InputForm] &,
     StringDelete[{"Hold[", "]"}], 
     StringReplace[{"*" -> "\[Times]", "/" -> "\[Divide]"}]],
    Union[
     Select[result == (# /. oprules) &]@
      Groupings[Permutations@input, {add, sub, mul, div} -> 2],
     SameTest -> (0 === 
         Simplify[
          sub[#1, #2] //. specifics /. 
           Prepend[oprules, k_Integer :> ToString[k]]] &)]]]]

1. 用符号add、sub、mul、div分别对应加减乘除四则运算，构建二叉树代表算式。Groupings函数生成了所有可能的表达式二叉树。

2. Select筛选出计算结果符合要求的。

3. Union负责除去雷同的算式。它的SameTest选项计算两个代数式的差化简后是否为0。注意这里通过把数字转为字符进行符号化了，而且对数字1、2进行了特殊处理（specifics）。

4. 最后Map负责把每个算式转成字符串输出。

测试：

这篇关于24点算法，如何给出所有不同的答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！