8

Scala でコイン (変更) 問題の再帰関数を作成しています。

私の実装は 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 が指摘したように冗長な最後のパラメーターがあるため、それを取り除きたいと思いました。2 番目の解決策はmap、第 1 週または皆さんが受講していると思われる Scala コースでまだカバーされていなかったため、回避したかった使用方法です。また、2番目の解決策は、著者が正しく指摘しているように、メモ化を使用しない限り、かなり遅くなります。最後に、Paaro のソリューションには、不要なネストされた関数があるようです。

だからここに私が終わったものがあります：

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

これは、再帰的アプローチで多くの再計算を減らす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 に答える
1

@Eastsun ソリューションは優れていますが、money=0 の場合は 0 ではなく 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)
  if(money>0) recurs(money, coins, 0) else 0
}
于 2013-09-20T17:27:23.797 に答える