程序计算24点

风行水上 @ 2013-12-03 14:18:29
标签:

    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)+524 = (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点

    标签:

      分享到:
      comments powered by Disqus

      28/30ms