Scala中硬币更改的StackOverflowError？

发布时间：2020-12-16 09:29:00 所属栏目：安全来源：网络整理

导读：我正在为Scala中的 Coin (change) problem编写递归函数. 我的实现打破了StackOverflowError,我无法弄清楚它为什么会发生. Exception in thread "main" java.lang.StackOverflowError at scala.collection.immutable.$colon$colon.tail(List.scala:358) at sc

我正在为Scala中的 Coin (change) problem编写递归函数.

我的实现打破了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,0)
}

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

else if(money<0)
    combos

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

解决方法

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

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,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
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!