scala 使用递归的Scala中的硬币变化算法

coin change algorithm in scala using recursion

提问by Muavia

I am trying to program the coin change problem in Scala using recursion. The code that i have written is as follows.

我正在尝试使用递归在 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)
}

On running the code, it does not terminate and keeps on calling the first recursive call. Where am I going wrong?

在运行代码时，它不会终止并继续调用第一个递归调用。我哪里错了？

采纳答案by Rex Kerr

Simply stating a value does not make Scala return it; you either need an explicit return, or it has to be the last item stated. Thus:

简单地说明一个值不会让 Scala 返回它；您要么需要明确的回报，要么必须是最后一项声明。因此：

if (capacity == 0) return 1

or

或者

if (capacity == 0) 1
else if (...)
else { ... }

回答by rkenmi

Nice and simple

好看又简单

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
}

回答by mysteriousscent

Here is my implementation: I have tested it and it works fine

这是我的实现：我已经测试过它并且工作正常

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

回答by Carlos Caldas

Just another solution

只是另一种解决方案

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
}

回答by Suat KARAKUSOGLU

Hey I just thought it would be better to see not only the amount but also the list of them, so put on top of the above example like :

嘿，我只是认为不仅要查看数量，还要查看它们的列表会更好，所以放在上面的示例之上，例如：

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

回答by Leonmax

here is a DP approach to reduce a lot of re-calculation in recursive approach

这是一种 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))
}

see DP from novice to advancedfor algorithm

看DP从新手到高级算法

回答by Prasad

Below code is similar to one of the above example except I am using match case instead of if else

下面的代码类似于上面的示例之一，除了我使用的是匹配案例而不是 if else

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