Рекурсия · 19 из 19
Чем набрать сумму
В бабушкиной шкатулке монеты старого образца, по нескольку каждого номинала. Внук спрашивает, сколькими способами из них набирается ровно рубль — и какими именно.
Что сделать
Найдите все способы набрать сумму монетами из бабушкиной шкатулки.
Что приходит
summa— какую сумму набрать, от нуляnominaly— кортеж номиналов по убыванию, без повторов; каждого сколько угодно
Что вернуть
Список разложений — каждое по невозрастанию, сначала начинающиеся с крупного; отличные только порядком — одно; сумма ноль — [[]].
Допишите функцию razlozhit в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
6 копеек монетами 5, 2 и 1: [5, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1] и [1, 1, 1, 1, 1, 1] — пять способов.
razlozhit(6, (5, 2, 1))
[[5, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
Функция принимает сумму (целое, не меньше нуля) и кортеж номиналов (целые больше нуля, идут по убыванию, без повторов). Возвращает список разложений. Разложение — список номиналов, дающих в сумме заданное число; номиналы в нём идут по невозрастанию, и каждый номинал можно брать сколько угодно раз. Разложения, отличающиеся только порядком монет, считаются одним. Порядок разложений — порядок перебора: сначала те, что начинаются с более крупного номинала. Для суммы ноль возвращается список с одним пустым разложением.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.