TUZ_7-02_Точный размен монет с учетом имеющихся номиналов
7.2. Точный размен монет с учетом имеющихся номиналов
Пусть дано положительное целое число – некоторая сумма денег – и массив номиналов монет в порядке убывания
и нужно выразить эту сумму в номиналах монет. Гарантируется, что наименьший номинал монеты в массиве равен 1.
Например, если сумма равна 583 и в нашем распоряжении имеются монеты с номиналами [142, 73, 45, 17, 13, 7, 1],
то эту сумму можно выразить в виде набора монет как [142, 142, 142, 142, 13, 1, 1].
Ваша задача: написать функцию, которая принимает положительное целое число и массив номиналов монет
и возвращает массив номиналов монет, общая стоимость которых в точности равна введенной сумме.
В табл. 7.2 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 7.2. Некоторые ожидаемые результаты для задачи размена монет с учетом имеющихся номиналов |
| Amount, coins |
Ожидаемый результат |
583
142, 73, 45, 17, 13, 7, 1 |
142, 142, 142, 142, 13, 1, 1 |
26
142, 45, 7, 1 |
7, 7, 7, 1, 1, 1, 1, 1 |
174
94, 73, 17, 13, 7, 4, 3, 1 |
94, 73, 7 |
1
142, 3, 1 |
1
|