StackOverflowError Scala中的硬幣更改？

Question

我正在爲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, coins, 0) 
} 

編輯：我剛剛加入else if語句可在混合：

else if(money<0) 
    combos 

它擺脫了錯誤，但我的輸出是1500東西:(瓦特我的邏輯有錯誤嗎？

Answer 1

這是基於你的代碼正確的解決方案：

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 
} 

Answer 2

的@Eastsun的解決方案是好的，但在金錢= 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 
} 

Answer 3

可以省略cnt參數，實際上這個參數是從來沒有累積過的。該復發函數總是返回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 
} 

Answer 4

第一種方案中the accepted answer有多餘的最後一個參數as noted by Paaro所以我想擺脫它。第二個解決方案使用了map，我想避免它，因爲它在第一週還沒有被覆蓋，或者我假設你正在使用Scala課程。另外，作者正確指出，第二種解決方案會慢一些，除非它使用一些記憶。最後，Paaro's solution似乎有一個不必要的嵌套函數。

因此，這裏是我結束了：

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) 

沒有必要對大括號在這裏，你可以看到。

我想知道是否可以進一步簡化。

Answer 5

這裏是一個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 from novice to advanced的算法