解24点

http://rosettacode.org/wiki/24_game_Player

上面链接里的暴力解法相似的输出项太多了，我总结了相互间不重复的表达式88种（4个数字加减乘除）：

MAN4D4S = [
        # '((%d %s %d) %s %d) %s %d' 48
        # +++
        '%d + %d + %d + %d',
        # ++-
        '%d + %d + %d - %d',
        # ++*
        '(%d + %d + %d) * %d',
        '(%d + %d) * %d + %d',
        '%d * %d + %d + %d',
        # ++/
        '(%d + %d + %d) / %d',
        '(%d + %d) / %d + %d',
        '(%d / %d) + %d + %d',
        # +--
        '%d + %d - %d - %d',
        # +-*
        '(%d + %d - %d) * %d',
        '(%d + %d) * %d - %d',
        '(%d - %d) * %d + %d',
        '%d * %d + %d - %d',
        # +-/
        '(%d + %d - %d) / %d',
        '(%d + %d) / %d - %d',
        '(%d - %d) / %d + %d',
        '%d / %d + %d - %d',
        # +**
        '(%d + %d) * %d * %d',
        '(%d * %d + %d) * %d',
        '%d * %d * %d + %d',
        # +*/
        '(%d + %d) * %d / %d',
        '(%d * %d + %d) / %d',
        '%d * %d / %d + %d',
        '(%d / %d + %d) * %d',
        # +//
        '(%d + %d) / %d / %d',
        '(%d / %d + %d) / %d',
        '%d / %d / %d + %d',
        # ---
        '%d - %d - %d - %d',
        # --*
        '(%d - %d - %d) * %d',
        '(%d - %d) * %d - %d',
        '%d * %d - %d - %d',
        # --/
        '(%d - %d - %d) / %d',
        '(%d - %d) / %d - %d',
        '%d / %d - %d - %d',
        # -**
        '(%d - %d) * %d * %d',
        '(%d * %d - %d) * %d',
        '%d * %d * %d - %d',
        # -*/
        '(%d - %d) * %d / %d',
        '(%d * %d - %d) / %d',
        '%d * %d / %d - %d',
        '(%d / %d - %d) * %d',
        # -//
        '(%d - %d) / %d / %d',
        '(%d / %d - %d) / %d',
        '%d / %d / %d - %d',
        # ***
        '%d * %d * %d * %d',
        # **/
        '%d * %d * %d / %d',
        # *//
        '%d * %d / %d / %d',
        # ///
        '%d / %d / %d / %d',
        
        # '(%d %s (%d %s %d)) %s %d' +8
        '(%d - %d * %d) * %d',
        '(%d - %d / %d) * %d',
        '%d / (%d + %d) * %d',
        '%d / (%d - %d) * %d',
        '(%d - %d * %d) / %d',
        '(%d - %d / %d) / %d',
        '%d / (%d + %d) / %d',
        '%d / (%d - %d) / %d',

        # '(%d %s %d) %s (%d %s %d)' +14
        '%d * %d + %d * %d',
        '%d * %d + %d / %d',
        '%d / %d + %d / %d',
        '%d * %d - %d * %d',
        '%d * %d - %d / %d',
        '%d / %d - %d * %d',
        '%d / %d - %d / %d',
        '(%d + %d) * (%d + %d)',
        '(%d + %d) * (%d - %d)',
        '(%d - %d) * (%d - %d)',
        '(%d + %d) / (%d + %d)',
        '(%d + %d) / (%d - %d)',
        '(%d - %d) / (%d + %d)',
        '(%d - %d) / (%d - %d)',
        
        # '%d %s ((%d %s %d) %s %d)' +14
        '%d - ((%d + %d) * %d)',
        '%d - ((%d + %d) / %d)',
        '%d - ((%d - %d) * %d)',
        '%d - ((%d - %d) / %d)',
        '%d - (%d * %d * %d)',
        '%d - (%d * %d / %d)',
        '%d - (%d / %d / %d)',
        '%d / (%d + %d + %d)',
        '%d / (%d + %d - %d)',
        '%d / (%d - %d - %d)',
        '%d / (%d * %d + %d)',
        '%d / (%d * %d - %d)',
        '%d / (%d / %d + %d)',
        '%d / (%d / %d - %d)',
        
        # '%d %s (%d %s (%d %s %d))' +4
        '%d - (%d / (%d + %d))',
        '%d - (%d / (%d - %d))',
        '%d / (%d - %d * %d)',
        '%d / (%d - %d / %d)'
      ]

用上面的字典就不需要分步求解了，我做成了Gem

gem install 24games

下面是分步思路

“舍弃相似项、变换表达式”

定义操作符优先级：

@@ops_pri = {"**" => 0,"*" => 1,"/"  => 1,"+" => 2,"-" => 2 }

依照操作符的优先级判断是否加括号。

5种执行流：

"i_i_i_i" => a op b op c op d     |e.g. (a+b)*c+d : (2+5)*3+3
"i_i_(i_i)" => a op b op (c op d) |e.g. (a-b)/(c/d) : (13-7)/(2/8)
"i_(i_i)_i" => a op (b op c) op d |e.g. (a-b/c)*d : (13-10/2)*3
"i_(i_i_i)" => a op (b op c op d) |e.g. a/(b/c/d): 6/(2/2/4)
"i_(i_(i_i))" => a op (b op (c op d))  |e.g. a/(b-c/d) : 8/(3-8/3)

为什么是5种，有另外一种思路：4张扑克，依次夹入3个操作符

第1个操作符，可以把4张扑克分割成“3张1张”、“2张2张”、“1张3张”三种形式；

“2张2张”的场合，后两个操作符分别夹到每个“2张”中间；

“3张”的场合，可以被第二个操作符继续分割成“2张1张”或者“1张2张”，最后在“2张”中间夹入第三个操作符；

总结起来五种流程。

iiii => i iii => i i ii => i i i i

iiii => i iii => i ii i => i i i i

iiii => ii ii =>  i i i i

iiii => iii i => i ii i => i i i i

iiii => iii i => ii i i => i i i i

把三步走并成表达式，并加上括号，一个项就出炉了。

给表达式加括号是一个小课题。它基于三个条件：上一次操作符、本次操作符、本次操作之于上次操作的位置。如果本次操作符的优先级高于上一次，或者同级条件下，准备减去或者除以上一次表达式，需给上一次表达式加上括号。

如果三步走的结果等于24，我们就该将它存入结果集了。我用了一个Hash作为结果集，KEY由操作符组和执行流组成，VALUE放这次计算的卡片组。Hash能够把1234相乘的24种排列组合并成一种解法。

“合并相似项”


操作符流合并
    合并工作的大头。 遵循（"+" > "-" > "*" > "/" > "**"）。分别在确定操作符组和执行流两个阶段进行过滤，要时刻清醒条件语句依靠基准的先后顺序。

e.g. a*(b*c)/d,a*(b/c*d),a/b*c*d,a*b/(c/d)...... 都取"**/"操作符组+"i_i_i_i"执行流；


运算合并
    0点的运算合并。如果0点的牌面用来被做+、-运算，都等同于“不参与计算”。取+0。
    1点的运算合并。如果1点的牌面用来被做*、/、**运算，都等同于“不参与计算”。取*1。
    2点的运算合并。2点的牌面被2点“*”或者“**”，取*2；4点的牌面被2点“-”或者“/”，取-2。


避免除法磨损
    e.g. 3388,利用分式能得出8/(3-8/3)=24，但是，电脑算除法若产生的结果大于1且小数除不尽，会产生偏差。考虑到这一点，需要把 8/(3-8/3) 通分成 8*3/(3*3-8) 处理（计算时按"4个操作符"+"i_i_(i_i_i)"执行流）。