Подсчет монет
maximsidorovСпособы размена монет
Рассмотрим реализацию алгоритма подсчёта количества способов размена заданной суммы с использованием заданных номиналов монет.
Введение
Алгоритм подсчёта числа способов размена монет решает задачу подсчёта количества способов представить заданную сумму денег с помощью различных номиналов монет. Это классическая динамически-программная задача, которая часто используется в комбинаторике и экономических моделях.
Функция changes
Функция changes вычисляет количество способов разменять заданную сумму (amount) с использованием доступных номиналов монет (coins).
Параметры:
amount: целое число — сумма, которую нужно разменятьcoins: массив целых чисел — номиналы доступных монет
Возвращает:
- Число типа
Int128— количество способов размена
function changes(amount::Int, coins::Array{Int})::Int128
# Создаём массив для хранения количества способов разменять каждую сумму от 0 до amount
# Индексация начинается с 1, поэтому размер массива — amount + 1
ways = zeros(Int128, amount + 1)
# Для суммы 0 есть один способ — не использовать ни одной монеты
ways[1] = 1
# Проходим по каждой монете
for coin in coins
# Для каждой суммы от `coin` до `amount`
for j in coin+1:amount+1
# Обновляем количество способов: добавляем способы получить сумму (j - coin)
ways[j] += ways[j - coin]
end
end
# Возвращаем число способов разменять сумму `amount`
return ways[amount + 1]
end
# Примеры использования функции
@show changes(100, [1, 2, 5, 10]); # Размен 100 рублей с помощью 1, 2, 5, 10-рублёвых монет
@show changes(100_000, [1, 5, 10]); # Размен 100 000 рублей
Основная часть
Что делает программа?
Программа считает, сколькими различными способами можно разменять определённую денежную сумму, используя ограниченный набор монет.
Например, сколько существует комбинаций монет номиналом 1, 2, 5, и 10, чтобы получить любую сумму до 100 рублей?
Как она работает? Пошаговое объяснение:
Шаг 1: Инициализация
Мы создаём массив ways, где ways[i] будет содержать количество способов составить сумму (i - 1) (из-за индексации с единицы в Julia).
На старте предполагаем, что есть один способ получить сумму 0 (взять 0 монет):
Шаг 2: Динамическое обновление значений
Для каждой монеты мы последовательно обновляем значения ways. Если у нас есть монета номиналом, например, 5 рублей, то:
- сумма 5 может быть разменяна как 0 + 5 → увеличиваем
ways[6]наways[1] - сумма 10 как 5 + 5 → увеличиваем
ways[11]наways[6], и т.д.
Шаг 3: Почему такой порядок циклов важен?
Цикл проходит по монетам, а внутри него — по суммам. Такой порядок гарантирует, что мы не учитываем одну и ту же комбинацию монет дважды (например, 5+10 и 10+5 считаются за одинаковые способы).
Результат работы программы
Программа выводит результаты вызовов функции через макрос @show, который автоматически печатает выражение и его значение.
Заключение
Мы рассмотрели реализацию алгоритма подсчёта способов размена денег. Этот алгоритм широко применяется в задачах комбинаторики, финансового моделирования и тестирования систем оплаты.
Пример разработан с использованием материалов Rosetta Code