У вас есть неограниченное количество монет достоинством 25, 10, 5 и 1 цент. Напишите код, определяющий количество способов представления n центов

Это рекурсивная задача, поэтому давайте разберемся, как рассчитать makeChange(n), основываясь на предыдущих решениях (подзадачах). Пусть n = 100. Мы хотим вычислить количество способов представления 100 центов.

Нам известно, что для получения 100 центов мы можем использовать монеты 0, 1, 2, 3 или 4 четвертака (25 центов):

			makeChange(100)=
makeChange(100, используя 0 четвертаков) +
makeChange(100, используя 1 четвертак)   +
makeChange(100, используя 2 четвертака)  +
makeChange(100, используя 3 четвертака)  +
makeChange(100, используя 4 четвертака)

Двигаемся дальше: попробуем упростить некоторые из этих задач. Например, makeChange(100, используя 1 четвертак) = makeChange(75, используя 0 четвертаков). Это так, потому что если мы должны использовать один четвертак для представления 100 центов, оставшиеся варианты соответствуют различным представлениям 75 центов.

Мы можем применить эту же логику для makeChange(100, используя 2 четвертака), makeChange(100, используя 3 четвертака) и makeChange(100, используя 4 четвертака).
Приведенное ранее выражение можно свести к следующему:

			makeChange(100)=
makeChange(100, используя 0 четвертаков) +
makeChange(75, используя 0 четвертаков)  +
makeChange(50, используя 0 четвертаков)  +
makeChange(25, используя 0 четвертаков)  +
1

Заметьте, что последнее выражение — makeChange(100, используя 4 четвертака) — равно 1.

Что делать дальше? Теперь мы израсходовали все четвертаки и можем использовать следующую самую крупную монету — 10 центов.

Подход, использованный для четвертаков, подойдет и для 10–центовых монет. Мы применим его для четырех частей приведенного выше выражения. Так, для первой части:

			makeChange(100, используя 0 четвертаков)  =
makeChange(100, используя 0 четвертаков, 0 монет в 10 центов)  +
makeChange(100, используя 0 четвертаков, 1 монету в 10 центов) +
makeChange(100, используя 0 четвертаков, 2 монеты в 10 центов) +
…
makeChange(100, используя 0 четвертаков, 10 монет в 10 центов)
makeChange(75, используя 0 четвертаков)  =
makeChange(75, используя 0 четвертаков, 0 монет в 10 центов)  +
makeChange(75, используя 0 четвертаков, 1 монету в 10 центов) +
makeChange(75, используя 0 четвертаков, 2 монеты в 10 центов) +
…
makeChange(75, используя 0 четвертаков, 7 монет в 10 центов)
makeChange(50, используя 0 четвертаков)  =
makeChange(50, используя 0 четвертаков, 0 монет в 10 центов)  +
makeChange(50, используя 0 четвертаков, 1 монету в 10 центов) +
makeChange(50, используя 0 четвертаков, 2 монеты в 10 центов) +
…
makeChange(50, используя 0 четвертаков, 5 монет в 10 центов)
makeChange(25, используя 0 четвертаков)  =
makeChange(25, используя 0 четвертаков, 0 монет в 10 центов)  +
makeChange(25, используя 0 четвертаков, 1 монету в 10 центов) +
makeChange(25, используя 0 четвертаков, 2 монеты в 10 центов)

После этого можно перейти к монеткам в 5 и 1 цент. В результате мы получим древовидную рекурсивную структуру, где каждый вызов расширяется до четырех или больше вызовов.

Базовый случай для нашей рекурсии — полностью сведенное (упрощенное) выражение. Например, makeChange(50, используя 0 четвертаков, 5 монет в 10 центов) полностью сводится к 1, так как 5 монет по 10 центов дает ровно 50 центов.

Рекурсивный алгоритм будет иметь примерно такой вид:

			public int makeChange(int n, int denom)  {
    int next_denom = 0;
    switch (denom)  {
        case 25:
            next_denom =10;
            break;
        case 10:
            next_denom =5;
            break;
        case 5:
            next_denom =1;
            break;
        case 1:
            return 1;
    }

    int ways = 0;
    for (int I = 0; I * denom<= n; i++){
        ways += makeChange (n – 1 * denom , next_denom);
    }
    return ways;
}

System.out.writeln(makeChange(100, 25));

Хотя мы реализовали код, опираясь на монеты, используемые в США, его можно легко адаптировать для любой другой валюты.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»

Рекурсия и динамикаПодписаться

5К открытий5К показов