Facebook Twitter LinkedIn E-mail
magnify
Home 2014 六月

Scala二十四点游戏(4):算法之一

前面我们定义了表达式的算法,通常的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,等等。列出所有有效的表达式。其中我们用枚举类型将符号定义成数字常量。

 

Scala二十四点游戏(3):表达式计算(三)

在上篇中我们实现了整数的四则运算的算法,这里我们回到之前提到的 5 5 5 1 的例子,我们看看eval ( ” 5 * ( 5 – 1/5) ” )的结果是多少?

scala> eval ("5*(5-1/5)")
res15: Int = 25

结果为25,我们知道这个结果应该是24,这是因为前面我们的算法都是针对整数的, 1/5 =0 ,当然我们可以把整数改成浮点数,比如,修改eval如下:

def eval(str:String):Double = str match {
    ...
    case _ => str toDouble
}

重新计算eval (“5*(5-1/5)”)
结果为 24.0,
但是浮点数带来了误差,不是特别理想,我们前面在介绍类和对象时,使用的Rational例子,任何有理数都可以表示成分数,因此可以利用这个Rational来得到表达式计算的精确结果。

class Rational (n:Int, d:Int) {
  require(d!=0)
  private val g =gcd (n.abs,d.abs)
  val numer =n/g
  val denom =d/g
  override def toString = numer + "/" +denom
  def +(that:Rational)  =
    new Rational(
      numer * that.denom + that.numer* denom,
      denom * that.denom
    )

  def -(that:Rational)  =
    new Rational(
      numer * that.denom - that.numer* denom,
      denom * that.denom
    )

  def * (that:Rational) =
    new Rational( numer * that.numer, denom * that.denom)

  def / (that:Rational) =
    new Rational( numer * that.denom, denom * that.numer)

  def this(n:Int) = this(n,1)
  private def gcd(a:Int,b:Int):Int =
    if(b==0) a else gcd(b, a % b)
}

利用Rational类,我们修改eval定义如下:

def eval(str:String):Rational = str match {
    case Bracket(part1,expr,part2) => eval(part1 +  eval(expr) + part2)
    case Add(expr1,expr2) => eval(expr1)  +  eval(expr2)
    case Subtract(expr1,expr2) => eval(expr1)  -  eval(expr2)
    case Multiply(expr1,expr2) => eval(expr1)  * eval(expr2)
    case Divide(expr1,expr2) => eval(expr1)  /  eval(expr2)
    case _ => new Rational (str.trim toInt,1)

  }

再看看eval (“5*(5-1/5)”)的计算结果:

scala> eval ("5*(5-1/5)")
res16: Rational = 24/1

我们得出来表达式的精确结果,为分数表示,比如:

scala> eval ("4*6")
res17: Rational = 24/1

scala> eval ("4*6+3*3+5/7")
res18: Rational = 236/7

到目前为止我们有了计算四则运算的算法,下面24的算法就比较简单了,穷举法。

注:Scala中表达式计算的算法还有不少其它方法,比如对表达式的分析可以利用scala.util.parsing.combinator提供的API。

 

Scala二十四点游戏(2):表达式计算(二)

在上篇Scala二十四点游戏(1):表达式计算(一)我们使用Scala实现了四则运算,但还不支持带括号的情况,本篇我们接着看看如处理带括号的情况,
比如表达式 1+2+(3*5)+3+3*(3+(3+5))

括号的情况稍微有些复杂,一层括号比较简单,对于嵌套括号的情况,需要匹配同一层次的括号,好在我们只需要匹配最外面一层括号,其它的可以通过递归函数的方法依次匹配。这里我们定义一个方法,通过栈结构来匹配最外一层括号:

import scala.collection.mutable.Stack  

def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){
        index=index + 1
        c match{
          case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }

      }

      Some(left,right)
    }else  None
  }

这个方法匹配最外面一层括号,并给出他们在字符中的位置,我们做个简单的测试

scala> val str="1+2+(3*5)+3+3*(3+(3+5))" 
str: String = 1+2+(3*5)+3+3*(3+(3+5))

scala> val Some((left,right))=matchBracket(str)
left: Int = 4
right: Int = 8

scala> str.charAt(left)
res0: Char = (

这个函数成功找到匹配的括号。

对于每个包含括号的表达式,可以有如下形式
part1 ( expr ) part2

因此我们可以实现如下的Bracket 对象来匹配括号表达式

object Bracket{

  def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){
        index=index + 1
        c match{
          case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }

      }

      Some(left,right)
    }else  None
  }

  def apply(part1:String,expr:String,part2:String) =part1+ "(" + expr + ")"+ part2
  def unapply(str:String) :Option[(String,String,String)] ={
     Bracket.matchBracket(str) match{
      case Some((left:Int,right:Int)) =>{
        val part1 = if (left == 0) "" else str substring(0, left )
        val expr = str substring(left + 1, right)
        val part2 = if (right == (str length)-1) "" else str substring (right+1)
        Some(part1, expr, part2)
      }
      case _ => None
    }
  }
}

修改之前的eval 函数,首先匹配括号表达式:

def eval(str:String):Int = str match {
    case Bracket(part1,expr,part2) => eval(part1 +  eval(expr) + part2)
    case Add(expr1,expr2) => eval(expr1)  +  eval(expr2)
    case Subtract(expr1,expr2) => eval(expr1)  -  eval(expr2)
    case Multiply(expr1,expr2) => eval(expr1)  * eval(expr2)
    case Divide(expr1,expr2) => eval(expr1)  /  eval(expr2)
    case _ => str toInt

 }

做些简单的测试:

scala> eval ("1+(3+(4+2)+3+(3+5)+3)+5")
res1: Int = 29

scala> eval ("1+2+(3*5)+3+3*(3+(3+5))")
res2: Int = 54

这样整数的四则运算的算法基本实现了,当然还不是很完善,比如负数,错误处理等,不过这些对我们解决24问题不是很重要,我们暂时忽略这些问题。

 

Scala课堂(4):基础(三)

这里我们转载Twitter的Scala课堂  ,转载的内容基本来自Twitter的Scala课堂中文翻译,部分有小改动.

scala> class Calculator {
     |         val brand: String = "HP"
     |         def add(m: Int, n: Int): Int = m + n
     |       }
defined class Calculator

scala> val calc = new Calculator
calc: Calculator = Calculator@6fe377b0

scala>  calc.add(1, 2)
res12: Int = 3

scala>  calc.brand
res13: String = HP

上面的例子展示了如何在类中用def定义方法和用val定义字段值。方法就是可以访问类的状态的函数。

构造函数
构造函数不是特殊的方法,他们是除了类的方法定义之外的代码。让我们扩展计算器的例子,增加一个构造函数参数,并用它来初始化内部状态。

class Calculator(brand: String) {
  /**
   * A constructor.
   */
  val color: String = if (brand == "TI") {
    "blue"
  } else if (brand == "HP") {
    "black"
  } else {
    "white"
  }

  // An instance method.
  def add(m: Int, n: Int): Int = m + n
}

注意两种不同风格的评论。

你可以使用构造函数来构造一个实例:

scala>  val calc = new Calculator("HP")
calc: Calculator = Calculator@39c8d5c4

scala>  calc.color
res14: String = black

表达式
上文的Calculator例子说明了Scala是如何面向表达式的。颜色的值就是绑定在一个if/else表达式上的。Scala是高度面向表达式的:大多数东西都是表达式而非指令

旁白: 函数 vs 方法

函数和方法在很大程度上是可以互换的。由于函数和方法是如此的相似,你可能都不知道你调用的东西是一个函数还是一个方法。而当真正碰到的方法和函数之间的差异的时候,你可能会感到困惑。

scala> class C {
     |         var acc = 0
     |         def minc = { acc += 1 }
     |         val finc = { () => acc += 1 }
     |       }
defined class C

scala>  val c = new C
c: C = C@7686da2

scala>  c.minc // calls c.minc()

scala>  c.finc // returns the function as a value:
res16: () => Unit = <function0>

当你可以调用一个不带括号的“函数”,但是对另一个却必须加上括号的时候,你可能会想哎呀,我还以为自己知道Scala是怎么工作的呢。也许他们有时需要括号?你可能以为自己用的是函数,但实际使用的是方法。

在实践中,即使不理解方法和函数上的区别,你也可以用Scala做伟大的事情。如果你是Scala新手,而且在读两者的差异解释,你可能会跟不上。不过这并不意味着你在使用Scala上有麻烦。它只是意味着函数和方法之间的差异是很微妙的,只有深入语言内部才能清楚理解它。

继承

class ScientificCalculator(brand: String) extends Calculator(brand) {
  def log(m: Double, base: Double) = math.log(m) / math.log(base)
}

参考 Effective Scala 指出如果子类与父类实际上没有区别,类型别名是优于继承的。A Tour of Scala 详细介绍了子类化。

重载方法

class EvenMoreScientificCalculator(brand: String) extends ScientificCalculator(brand) {
  def log(m: Int): Double = log(m, math.exp(1))
}

抽象类
你可以定义一个抽象类,它定义了一些方法但没有实现它们。取而代之是由扩展抽象类的子类定义这些方法。你不能创建抽象类的实例。

scala> abstract class Shape {
     |         def getArea():Int    // subclass should define this
     |       }
defined class Shape

scala> class Circle(r: Int) extends Shape {
     |         def getArea():Int = { r * r * 3 }
     |       }
defined class Circle

scala>  val s = new Shape
<console>:8: error: class Shape is abstract; cannot be instantiated
        val s = new Shape
                ^

scala>  val c = new Circle(2)
c: Circle = Circle@1fe4da96

特质(Traits)
特质是一些字段和行为的集合,可以扩展或混入(mixin)你的类中.

trait Car {
  val brand: String
}

trait Shiny {
  val shineRefraction: Int
}

class BMW extends Car {
  val brand = "BMW"
}

通过with关键字,一个类可以扩展多个特质:

class BMW extends Car with Shiny {
  val brand = "BMW"
  val shineRefraction = 12
}

参考 Effective Scala 对特质的观点

什么时候应该使用特质而不是抽象类? 如果你想定义一个类似接口的类型,你可能会在特质和抽象类之间难以取舍。这两种形式都可以让你定义一个类型的一些行为,并要求继承者定义一些其他行为。一些经验法则:

  • 优先使用特质。一个类扩展多个特质是很方便的,但却只能扩展一个抽象类。
  • 如果你需要构造函数参数,使用抽象类。因为抽象类可以定义带参数的构造函数,而特质不行。例如,你不能说trait t(i: Int) {},参数i是非法的。

你不是问这个问题的第一人。可以查看更全面的答案: stackoverflow: Scala特质 vs 抽象类 , 抽象类和特质的区别, and Scala编程: 用特质,还是不用特质?

类型
此前,我们定义了一个函数的参数为Int,表示输入是一个数字类型。其实函数也可以是泛型的,来适用于所有类型。当这种情况发生时,你会看到用方括号语法引入的类型参数。下面的例子展示了一个使用泛型键和值的缓存。

trait Cache[K, V] {
  def get(key: K): V
  def put(key: K, value: V)
  def delete(key: K)
}

方法也可以引入类型参数。

def remove[K](key: K)
 

Scala课堂(3):基础(二)

这里我们转载Twitter的Scala课堂  ,转载的内容基本来自Twitter的Scala课堂中文翻译,部分有小改动.

部分应用(Partial application)
你可以使用下划线“_”部分应用一个函数,结果将得到另一个函数。Scala使用下划线表示不同上下文中的不同事物,你通常可以把它看作是一个没有命名的神奇通配符。在{ _ + 2 }的上下文中,它代表一个匿名参数。你可以这样使用它:

scala>  def adder(m: Int, n: Int) = m + n
adder: (m: Int, n: Int)Int

scala> val add2 = adder(2, _:Int)
add2: Int => Int = <function1>

scala> add2(3)
res7: Int = 5

你可以部分应用参数列表中的任意参数,而不仅仅是最后一个。

柯里化函数
有时会有这样的需求:允许别人一会在你的函数上应用一些参数,然后又应用另外的一些参数。

例如一个乘法函数,在一个场景需要选择乘数,而另一个场景需要选择被乘数。

scala> def multiply(m: Int)(n: Int): Int = m * n
multiply: (m: Int)(n: Int)Int

你可以直接传入两个参数。

scala>  multiply(2)(3)
res8: Int = 6

你可以填上第一个参数并且部分应用第二个参数。

scala> val timesTwo = multiply(2) _
timesTwo: Int => Int = <function1>

scala>  timesTwo(3)
res9: Int = 6

你可以对任何多参数函数执行柯里化。例如之前的adder函数

scala>  (adder _).curried
res10: Int => (Int => Int) = <function1>

可变长度参数
这是一个特殊的语法,可以向方法传入任意多个同类型的参数。例如要在多个字符串上执行String的capitalize函数,可以这样写:

scala> :paste
// Entering paste mode (ctrl-D to finish)

def capitalizeAll(args: String*) = {
  args.map { arg =>
    arg.capitalize
  }
}

// Exiting paste mode, now interpreting.

capitalizeAll: (args: String*)Seq[String]

scala>  capitalizeAll("rarity", "applejack")
res11: Seq[String] = ArrayBuffer(Rarity, Applejack)

 

Scala课堂(2):基础(一)

这里我们转载Twitter的Scala课堂  ,转载的内容基本来自Twitter的Scala课堂中文翻译,部分有小改动.

表达式

scala> 1 + 1
res0: Int = 2

res0是解释器自动创建的变量名称,用来指代表达式的计算结果。它是Int类型,值为2。

Scala中(几乎)一切都是表达式。


你可以给一个表达式的结果起个名字赋成一个不变量(val)。

scala>  val two = 1 + 1
two: Int = 2

变量
如果你需要修改这个名称和结果的绑定,可以选择使用var

scala>  var name = "steve"
name: String = steve

scala>  name = "marius"
name: String = marius

函数
你可以使用def创建函数.

scala> def addOne(m: Int): Int = m + 1
addOne: (m: Int)Int

在Scala中,你需要为函数参数指定类型签名。

scala> val three = addOne(2)
three: Int = 3

如果函数不带参数,你可以不写括号。

scala> def three() = 1 + 2
three: ()Int

scala> three()
res0: Int = 3

scala> three
res2: Int = 3

匿名函数
你可以创建匿名函数。

scala> (x: Int) => x + 1
res3: Int => Int = <function1>

这个函数为名为x的Int变量加1。

scala> res3(1)
res4: Int = 2

你可以传递匿名函数,或将其保存成不变量。

scala> val addOne = (x: Int) => x + 1
addOne: Int => Int = <function1>

scala>  addOne(1)
res5: Int = 2

如果你的函数有很多表达式,可以使用{}来格式化代码,使之易读。

def timesTwo(i: Int): Int = {
  println("hello world")
  i * 2
}

对匿名函数也是这样的

scala>  { i: Int =>
     |   println("hello world")
     |   i * 2
     | }
res6: Int => Int = <function1>

在将一个匿名函数作为参数进行传递时,这个语法会经常被用到