Алгоритм изменения монеты в скале с использованием рекурсии

Question

Я пытаюсь запрограммировать проблему замены монет в 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)
}

При запуске кода он не завершается и продолжает вызывать первый рекурсивный вызов. Куда я иду не так?

Answer 1

Простое указание значения не заставляет Scala возвращать его; Вам либо нужен явный возврат, либо это должен быть последний заявленный элемент. Таким образом:

if (capacity == 0) return 1

или же

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

Answer 2

Красиво и просто

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
}

Answer 3

Вот моя реализация: я проверил, и она отлично работает

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

Answer 4

Просто другое решение

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
}

Answer 5

Эй, я просто подумал, что было бы лучше увидеть не только сумму, но и их список, поэтому поместите поверх приведенного выше примера, например:

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

Answer 6

Вот мой код: он не оптимизирован, но работает во всех тестовых случаях.

Идея состоит в том, чтобы вычесть первую монету списка из денег, пока она не станет 0. Как только она станет 0, она вернет 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)
    }
})

Answer 7

Код ниже похож на один из приведенных выше примеров, за исключением того, что я использую регистр соответствия вместо 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)
  }

Answer 8

Вот подход 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 от новичка до продвинутого алгоритма

Answer 9

Это будет обрабатывать случай, когда деньги равны нулю, но не отрицательные монеты...

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

    def loop(money: Int, coins: List[Int]): Int = {
      if(money == 0) {
        1
      } else if(money > 0 && !coins.isEmpty) {
        loop(money - coins.head, coins) + loop(money, coins.tail)
      } else {
        0
      }
    }

    if(money == 0) {
      0
    } else {
      loop(money: Int, coins: List[Int])
    }

}