程序计算24点

24点是一个简单的智力游戏，可以用于训练四则运算能力。实践中，可以借助扑克牌来玩24点游戏。

问题描述

给定四个整数（通常小于等于10），通过四则运算计算出24来。每个数字只能用一次，且至少用一次。

基本思路

• S = f(a,b,c,d)
• a,b,c,d中必有两者先进行了某种运算
• 穷举所有可能组合，递归计算

function calculate_24(target, input){
  var result = [];

  if(input.length == 1){
    if(input[0][3] == target){ // bingo
      result.push(polish_sort(input[0]));
    }else{
      // fail
    }
    return result;
  }

  for(var i=0, ni=input.length; i<ni; i++){
    for(var j=i+1, nj=input.length; j<nj; j++){
      var x  = input[i], y = input[j];
      var s = [];
      s.push(polish_calculate([x, y, '+']));
      s.push(polish_calculate([x, y, '-']));  s.push(polish_calculate([y, x, '-']));
      s.push(polish_calculate([x, y, '*']));
      s.push(polish_calculate([x, y, '/']));  s.push(polish_calculate([y, x, '/']));

      for(var k=0, nk=s.length; k<nk; k++){
          var d = input.slice(0);
          d.splice(i,1); d.splice(j-1,1);
          d.push(s[k]);
          Array.prototype.push.apply(result, calculate_24(target, d));
      }
    }
  }
  return result;
}

去除重复

上面方法的一个重要缺陷是无法“消重”——即去除本质上一样的计算式。重复的原因之一是交换律和结合律的存在。

• 交换律：a+b+c == a+c+b
• 结合律：a+b+c == a+(b+c) == b+c+a

一些重复的例子

• 24 = ((8+2)+9)+5 和 24 = (8+2)+(9+5) 和 24 = 8+((2+9)+5)
• 24 = 8-(8*(6-8)) 和 24 = 8+(8*(8-6))
• 24 = (3+9)*(4/2) 和 24 = (3+9)/(2/4) 和 24 = ((3+9)*4)/2

去除重复的方法

为了能够消除这种重复的式子，需要研究算式的表示方法。

算式的表示方法

• infix: 即我们通常所写的式子，运算符在中间，比如 a + b
• prefix: 波兰表达式。运算符在前面，比如：+ a b
• postfix: 逆波兰表达式。运算符在后面，比如：a b +

TODO

24点计算器

参见 24点计算器 - 不仅仅是计算24点