Условие: Сколькими способами можно разменять 5 рублей монетами 1, 2, 3 рубля?
Например: 5 = 1+1+1+1+1 = 1+1+1+2 = 1+2+2 = 2+3 = 1+1+3 = ...
АЛГОРИТМ Размен(сумма, монеты, текущий_набор)
// Базовый случай: разменяли полностью!
ЕСЛИ сумма = 0 ТО
ВЫВЕСТИ текущий_набор
ВЫЙТИ ИЗ АЛГОРИТМА
КОНЕЦ ЕСЛИ
// Отсечение: перебрали сумму
ЕСЛИ сумма < 0 ТО
ВЫЙТИ ИЗ АЛГОРИТМА
КОНЕЦ ЕСЛИ
// Перебираем монеты
ДЛЯ КАЖДОЙ монеты ИЗ монеты ВЫПОЛНЯТЬ
ДОБАВИТЬ монету В КОНЕЦ текущий_набор // берём монету
Размен(сумма - монета, монеты, текущий_набор)
УДАЛИТЬ ПОСЛЕДНИЙ ЭЛЕМЕНТ ИЗ текущий_набор // возврат
КОНЕЦ ЦИКЛА
КОНЕЦ АЛГОРИТМА
// Запуск
Размен(5, [1, 2, 3], [])
Эта задача встречается везде:
- Размен денег в магазине
- Разрезание пиццы на кусочки
- Распределение задач по дням