给定一个数组，用(+,,*,/)计算出结果为N的表达式

我得解法只是简单的暴力求解&＃xff0c;尝试每一种可能性&＃xff0c;把符合条件的结果找出来。应该是有更加高效的算法&＃xff0c;至少可以用到剪枝&＃xff1b;仅仅是暴力求解&＃xff0c;似乎没有拿来做得理由&＃xff0c;主要是为了用scala尝试functional的解法&＃xff0c;通过构建基础的组件&＃xff08;函数&＃xff09;&＃xff0c;将它们组合&＃xff0c;最后得到结果&＃xff1b;

完整的代码如下&＃xff1a;

object App extends App {abstract trait Op {def value: Intdef expression: Stringdef isValid: Boolean}object Op {def list(x: Op, y: Op) &＃61; List(Add(x, y), Sub(x, y), Mul(x, y), Div(x, y))}case class Add(left: Op, right: Op) extends Op {override def value: Int &＃61; left.value &＃43; right.valueoverride def expression: String &＃61; "(" &＃43; left.expression &＃43; " &＃43; " &＃43; right.expression &＃43; ")"override def isValid: Boolean &＃61; left.value <&＃61; right.value}case class Sub(left: Op, right: Op) extends Op {override def value: Int &＃61; left.value - right.valueoverride def expression: String &＃61; "(" &＃43; left.expression &＃43; " - " &＃43; right.expression &＃43; ")"override def isValid: Boolean &＃61; left.value > right.value}case class Mul(left: Op, right: Op) extends Op {override def value: Int &＃61; left.value * right.valueoverride def expression: String &＃61; left.expression &＃43; " * " &＃43; right.expressionoverride def isValid: Boolean &＃61; left.value <&＃61; right.value && left.value !&＃61; 1 && right.value !&＃61; 1}case class Div(left: Op, right: Op) extends Op {override def value: Int &＃61; left.value / right.valueoverride def expression: String &＃61; left.expression &＃43; " / " &＃43; right.expressionoverride def isValid: Boolean &＃61; right.value !&＃61; 0 && left.value % right.value &＃61;&＃61; 0 && right.value !&＃61; 1}case class Val(override val value: Int) extends Op {override def expression: String &＃61; s"$value"override def isValid: Boolean &＃61; true}def splitArray(array: List[Int]): List[(List[Int], List[Int])] &＃61;array match {case Nil &＃61;> throw new RuntimeException("no empty array allowed here.")case x :: y :: Nil &＃61;> List((List(x), List(y)))case h :: tail &＃61;>(List(h), tail) :: (for {(x, y) <- splitArray(tail)} yield (h :: x, y))}def express(nums: List[Int]): List[Op] &＃61;nums match {case Nil &＃61;> throw new RuntimeException("empty list")case x :: Nil &＃61;> List(Val(x))case _ &＃61;>for {(left, right) <- splitArray(nums)x <- express(left)y <- express(right)op <- Op.list(x, y)if op.isValid} yield op}def choices(nums: List[Int]): List[List[Int]] &＃61; {def go(lists: List[List[Int]], i: Int, used: Set[Int]): List[List[Int]] &＃61;if (i &＃61;&＃61; nums.length) listselse {for {x <- numsif (!used(x))subChoice <- go(lists &＃43;&＃43; lists.map(x :: _), i &＃43; 1, used &＃43; x)} yield {subChoice}}go(List(Nil), 0, Set.empty).toSet.toList}def countDown(nums: Array[Int], res: Int): List[Op] &＃61; {for {list <- choices(nums.toList)if (!list.isEmpty)op <- express(list)if (op.value &＃61;&＃61; res)} yield op}choices(Array(1, 3, 10).toList).foreach(println)//  splitArray(Array(1, 3, 7, 10, 25, 50).toList).foreach(println)val opList &＃61; countDown(Array(1, 3, 7, 10, 25, 50), 765)opList.foreach(op &＃61;> println(op.expression))
}

1. 之所以使用Op trait&＃xff0c;主要有两个作用&＃xff0c;a. 我们不仅仅是关心最后的值&＃xff0c;是否等于765&＃xff0c;也关心这个表达式本身&＃xff1b;2. 判断这个表达式是否有效&＃xff0c;计算出的结果是否是整数&＃xff1b;

2. choices(list), 返回用list元素的所有可能的组合&＃xff0c;比如choicee(list(1, 2)) &＃61;> [], [1], [2], [1, 2], [2, 1]&＃xff1b;接下来可以用每个组合去求出Op。 这个方法的时间复杂度即为n!, 所以可以看出这个算法只能是玩玩而已&＃xff1b;

3. 然后用上面求出的组合&＃xff0c;去计算表达式&＃xff0c;a. 要过滤掉过的集合&＃xff0c;因为我们没有用来表示空的Op&＃xff0c;b. 对于只有一个元素的集合&＃xff0c;只有一种可能性&＃xff0c;就是该元素本身&＃xff0c; Val(x); c. 当有多个元素的时候&＃xff0c;需要把该集合切分成两边&＃xff0c;递归计算Op&＃xff0c;然后把Op合并&＃xff1b;

Just For Fun.