8

我正在为Scala中的Coin (change) 问题编写递归函数。

我的实现因 StackOverflowError 而中断，我无法弄清楚它为什么会发生。

Exception in thread "main" java.lang.StackOverflowError
    at scala.collection.immutable.$colon$colon.tail(List.scala:358)
    at scala.collection.immutable.$colon$colon.tail(List.scala:356)
    at recfun.Main$.recurs$1(Main.scala:58) // repeat this line over and over

这是我的电话：

  println(countChange(20, List(1,5,10)))

这是我的定义：

def countChange(money: Int, coins: List[Int]): Int =  {

  def recurs(money: Int, coins: List[Int], combos: Int): Int = 
  {    
      if (coins.isEmpty)
          combos
      else if (money==0)
          combos + 1
      else
          recurs(money,coins.tail,combos+1) + recurs(money-coins.head,coins,combos+1)

  }
  recurs(money, coins, 0)
}

编辑：我刚刚在混合中添加了 else if 语句：

else if(money<0)
    combos

它摆脱了错误，但我的输出是 1500 东西 :( 我的逻辑有什么问题？

4

6 回答 6

20

如Paaro所述，已接受答案中的第一个解决方案具有多余的最后一个参数，因此我想摆脱它。我想避免使用第二种解决方案，因为它尚未在第 1 周或我假设您正在学习的 Scala 课程中涵盖。此外，正如作者正确指出的那样，第二种解决方案会慢得多，除非它使用一些记忆。最后，Paaro 的解决方案似乎有一个不必要的嵌套函数。 map

所以这就是我最终的结果：

def countChange(money: Int, coins: List[Int]): Int =
  if (money < 0)
    0
  else if (coins.isEmpty)
    if (money == 0) 1 else 0
  else
    countChange(money, coins.tail) + countChange(money - coins.head, coins)

如您所见，这里不需要大括号。

我想知道它是否可以进一步简化。

于 2013-12-27T00:25:18.310 回答
17

这是基于您的代码的正确解决方案：

def countChange(money: Int, coins: List[Int]): Int = {
  def recurs(m: Int, cs: List[Int], cnt: Int): Int =
      if(m < 0) cnt  //Not a change, keep cnt
      else if(cs.isEmpty) {
        if(m == 0) cnt + 1 else cnt // plus cnt if find a change
      }
      else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt)
  recurs(money, coins, 0)
}

无论如何，有一个简短的解决方案（但效率不高，您可以缓存中间结果以使其高效。）

def countChange(m: Int, cs: List[Int]): Int = cs match {
  case Nil => if(m == 0) 1 else 0
  case c::rs => (0 to m/c) map (k => countChange(m-k*c,rs)) sum
}
于 2013-04-07T13:14:09.937 回答
3

可以省略 cnt 参数，实际上它是从不累加的。recurs 函数总是返回 0 或 1，因此优化的算法将是：

def countChange(money: Int, coins: List[Int]): Int = {
  def recurs(m: Int, cs: List[Int]): Int =
      if(m < 0) 0  //Not a change, return 0
      else if(cs.isEmpty) {
        if(m == 0) 1 else 0 // 1 if change found, otherwise 0
      }
      else recurs(m, cs.tail) + recurs(m-cs.head, cs)
  if(money>0) recurs(money, coins) else 0
}
于 2013-09-27T23:15:17.050 回答
1

@Eastsun 解决方案很好，但是当 money=0 时它会失败，因为它返回 1 而不是 0，但您可以轻松修复它：

def countChange(money: Int, coins: List[Int]): Int = {
  def recurs(m: Int, cs: List[Int], cnt: Int): Int =
      if(m < 0) cnt  //Not a change, keep cnt
      else if(cs.isEmpty) {
        if(m == 0) cnt + 1 else cnt // plus cnt if find a change
      }
      else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt)
  if(money>0) recurs(money, coins, 0) else 0
}
于 2013-09-20T17:27:23.797 回答
1

这是一种DP方法，可以减少递归方法中的大量重新计算

object DP {
  implicit val possibleCoins = List(1, 5, 10, 25, 100)
  import collection.mutable.Map

  def countChange(amount: Int)(implicit possibleCoins: List[Int]) = {
    val min = Map((1 to amount).map (_->Int.MaxValue): _*)
    min(0) = 0
    for {
      i <- 1 to amount
      coin <- possibleCoins
      if coin <= i && min(i - coin) + 1 < min(i)
    } min(i) = min(i-coin) + 1
    min(amount)
  }

  def main(args: Array[String]) = println(countChange(97))
}

看DP从新手到高级算法

于 2015-04-27T16:14:54.123 回答
0

来自https://github.com/pathikrit/scalgos/blob/9e99f73b4241f42cc40a1fd890e72dbeda2df54f/src/main/scala/com/github/pathikrit/scalgos/DynamicProgramming.scala#L44的想法

case class Memo[K,I,O](f: I => O)(implicit i2k:I=>K ) extends (I => O) {
  import scala.collection.mutable.{Map => Dict}
  val cache = Dict.empty[K, O]
  override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}
def coinchange(s: List[Int], t: Int) = {
  type DP = Memo[ (Int, Int), (List[Int], Int),Seq[Seq[Int]]]
  implicit def encode(key: (List[Int], Int)):(Int,Int) = (key._1.length, key._2)

  lazy val f: DP = Memo {
    case (Nil, 0) => Seq(Nil)
    case (Nil, _) => Nil
    case (_, x) if x< 0  => Nil
    case (a :: as, x) => f(a::as, x - a).map(_ :+ a) ++ f(as, x)
  }

  f(s, t)
}
于 2019-01-23T16:37:02.387 回答