18

再帰を使用してScalaのコイン交換問題をプログラムしようとしています。私が書いたコードは次のとおりです。

def countChange(money: Int, coins: List[Int]): Int = {
  def ways(change: List[Int], size: Int, capacity: Int): Int = {
    if(capacity == 0) 1
    if((capacity < 0) || (size <= 0)) 0

    //println and readLine to check and control each recursive call.

    println("calling ways(",change, change.length-1, capacity,") + ways(",change,   change.length, capacity - change(change.length - 1),")")
    readLine()
    //

    ways(change, change.length-1, capacity) + ways(change, change.length, capacity - change(change.length - 1))
  }
  ways(coins, coins.length, money)
}

コードを実行すると、コードは終了せず、最初の再帰呼び出しを呼び出し続けます。どこが間違っているのですか？

4

8 に答える 8

103

素晴らしくてシンプル

def countChange(money: Int, coins: List[Int]): Int = {
  if(money == 0)
    1
  else if(money > 0 && !coins.isEmpty)
    countChange(money - coins.head, coins) + countChange(money, coins.tail)
  else
    0
}
于 2014-11-01T06:04:10.540 に答える
20

これが私の実装です：私はそれをテストしました、そしてそれはうまく働きます

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

  def count(capacity: Int, changes: List[Int]): Int = {
    if (capacity == 0)
      1
    else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else
      count(capacity, changes.tail) 
        + count(capacity - changes.head, changes)
  }

  count(money, coins.sortWith(_.compareTo(_) < 0))
}
于 2013-06-27T15:19:55.487 に答える
12

ちょうど別の解決策

def countChange(amount: Int, coins: List[Int]): Int = coins match {
  case _ if amount == 0 => 1
  case h :: t if amount > 0 => countChange(amount - h, h :: t) + countChange(amount, t)
  case _ => 0
}
于 2016-11-06T04:25:36.797 に答える
8

値を指定するだけでは、Scalaはその値を返しません。明示的な返品が必要であるか、最後に記載されているアイテムである必要があります。したがって：

if (capacity == 0) return 1

また

if (capacity == 0) 1
else if (...)
else { ... }
于 2012-09-27T20:50:12.607 に答える
3

ちょっと私はちょうど量だけでなくそれらのリストも見る方が良いと思ったので、上記の例の上に次のように置きます：

def moneyChanges(money: Int, coins: List[Int]) : Option[List[Seq[Int]]]= {
  var listOfChange=List[Seq[Int]]()
  def changeMoney(capacity: Int, changes: List[Int], listOfCoins: Option[Seq[Int]]): Int = {
    if (capacity == 0) {
      listOfChange = listOfCoins.get :: listOfChange
      1
    } else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else {
      changeMoney(capacity, changes.tail, listOfCoins) +
      changeMoney(capacity - changes.head, changes, 
      Some(changes.head +: listOfCoins.getOrElse(Seq())))
    }
  }

  changeMoney(money, coins.sortWith(_.compareTo(_) < 0), None)
  Some(listOfChange)
}
于 2013-12-14T13:38:40.490 に答える
0

これは、再帰的アプローチで多くの再計算を減らすための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-29T06:08:57.287 に答える
0

以下のコードは、ifelseの代わりにmatchcaseを使用していることを除いて、上記の例の1つに似ています。

def countChange(money: Int, coins: List[Int]): Int = {
    def change(m: Int, coinList: List[Int], count: Int): Int =
      m match {
        case _ if m < 0 => count
        case _ if coinList.isEmpty => {
          m match {
            case 0 => count + 1
            case _ => count
          }
        }
        case _ => change(m, coinList.tail, count) + change(m - coinList.head, coinList, count)
      }
    change(money, coins, 0)
  }
于 2016-06-23T11:01:23.647 に答える
0

これが私のコードです。最適化されていませんが、すべてのテストケースで機能します。

アイデアは、リストの最初のコインをお金から0になるまで引くことです。0になると、1が返されます。これは、1つの解決策が可能であることを意味します。異なる再帰から来るすべてのソリューションを追加するために、私は使用しfoldLeftました。

（を使用してリストを反復するfoldLeftので、最初に1になり、次に再帰になり、（1、2）リストを繰り返します）

                    [4, (1, 2)].  
             /(1 as cn)       \ (2 as cn)
            [3, (1, 2)].                 [2, (2)]
         /(-1)       \(-2)                \
      [2, (1, 2)].     [1, (2)].          [0, (2)]   
       /.(-1)    \(-2) 
     [1, (1, 2)].   [0, (2)]
      /. (-1)  \(-2)
    [0, (1, 2)].  [-1, (2)]

def countChange(money: Int, coins: List[Int]): Int = coins.foldLeft(0)((accum, cn) =>
  (money, cn) match {
    case (money, _) if money < 0 => 0
    case (0, _) => 1
    case (curr_money, curr_coin) =>
      val (before_curr_coin, after_curr_coin) = coins.span(_ != curr_coin)
      accum + countChange(curr_money - curr_coin, after_curr_coin)
  })
于 2020-09-09T17:16:48.597 に答える