Сколькими способами можно дать сдачу? Реализация на Scala

January 29, 2019 14:13

Задание: написать функцию, которая посчитает, сколькими способами можно дать сдачу если имеется список монет, при условии, что количество каждой монеты не ограничено. Реализовать функцию подсчета на языке программирования Scala. 

Рассуждение: для начала давайте сразу исключим очевидные варианты - если денег отрицательное количество - нужно вернуть 0, то есть нельзя дать сдачу, то же самое касается и случая, когда список монет пуст. Если количество денег равно нулю, то вернуть сдачу можно только одним способом. Во всех остальных случаях воспользуемся рекурсией. Общее число способов размена какой-либо суммы равно числу способов разменять эту сумму без привлечения монет первого типа плюс число способов размена в предположении.

Реализация:

// T(n, k) = T(n - k0, k) + T(n, {k1..k})

def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0 || coins.isEmpty) 0
    else if (money == 0) 1
    else countChange(money - coins.head, coins) + countChange(money, coins.tail)  
}

countChange(100, List(10, 20, 30))