返回首页 Scala 二十四点游戏

算法之一

前面我们定义了表达式的算法,通常的 24 点常用的算法,尽管都是穷举,也有几个常用的不同的算法,其中之一有人称为动态规划算法:

把多元运算转化为两元运算,先从四个数中取出两个数进行运算,然后把运算结果和第三个数进行运算, 再把结果与第四个数进行运算。在求表达式的过程中,最难处理的就是对括号的处理,而这种思路很好的避免了对括号的处理。基于这种思路的一种算法: 因为能使用的 4 种运算符 – * / 都是2元运算符,所以本文中只考虑 2 元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。

由上所述,构造所有可能的表达式的算法如下:

(1) 将 4 个整数放入数组中

(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,

(2.1) 对 – * / 每一个运算符,

(2.1.1) 根据此排列的两个数字和运算符,计算结果

(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中

(2.1.3) 对新的数组,重复步骤 2

(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉

可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。

在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。

在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。

括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。

使用这个算法的一个 Scala 实现如下:

def solve(vs: List[Int],n: Int = 24){
    def isZero(d: Double) = Math.abs(d) < 0.00001

    //解析为恰当的中缀表达式
    def toStr(any: Any): String = any match {
        case (v: Double,null,null,null) => v.toInt.toString
        case (_,v1: (Double,Any,Any,Any),v2: (Double,Any,Any,Any),op) => 
               if(op=='-'&&(v2._4=='+'||v2._4=='-'))
                   "%s%c(%s)".format(toStr(v1),op,toStr(v2))
               else if(op=='/'){
                   val s1 = if(v1._4=='+'||v1._4=='-') "("+toStr(v1)+")" else toStr(v1)
                   val s2 = if(v2._4==null) toStr(v2) else "("+toStr(v2)+")"
                   s1 + op + s2
               }
               else if(op=='*'){
                   val s1 = if(v1._4=='+'||v1._4=='-') "("+toStr(v1)+")" else toStr(v1)
                   val s2 = if(v2._4=='+'||v2._4=='-') "("+toStr(v2)+")" else toStr(v2)
                   s1 + op + s2
               }
               else toStr(v1) + op + toStr(v2)
    }

    //递归求解
    val buf = collection.mutable.ListBuffer[String]()
    def solve0(xs: List[(Double,Any,Any,Any)]): Unit = xs match {
        case x::Nil => if(isZero(x._1-n) && !buf.contains(toStr(x))){ buf += toStr(x); println(buf.last)}
        case _      => for{ x @ (v1,_,_,_) <- xs;val ys = xs diff List(x)
                              y @ (v2,_,_,_) <- ys;val rs = ys diff List(y)
                         }{   solve0((v1+v2,x,y,'+')::rs)
                              solve0((v1-v2,x,y,'-')::rs)
                              solve0((v1*v2,x,y,'*')::rs)
                              if(!isZero(v2)) solve0((v1/v2,x,y,'/')::rs)
                         }
    }
    solve0(vs map {v => (v.toDouble,null,null,null)})
}

测试如下:

scala> solve(List(5,5,5,1))
(5-1/5)*5
5*(5-1/5)

scala> solve(List(3,3,8,8))
8/(3-8/3)

这个算法的来源于网上,很简短的代码就实现了算 24 的算法,Scala 还是比较强大的:-)

不过我们这里还是采用另外一种方法,来介绍Scala编程的多个方面。

这个算法就是列出 4 个数字加减乘除的各种可能性。我们可以将表达式分成以下几种:首先我们将 4 个数设为 a,b,c,d,,将其排序列出四个数的所有排序序列组合(共有 24 种组合)。再进行符号的排列表达式,其中算术符号有+,—,*,/,(,)。其中有效的表达式有 a*(b-c/b),a*b-c*d,等等。列出所有有效的表达式。其中我们用枚举类型将符号定义成数字常量。

上一篇: 表达式计算(三) 下一篇: List 简介