Н

Дана задача о размене денег. Предположим, что у нас есть некоторая сумма денег, и мы должны разменять ее на наименьшее количество монет различного достоинства.

Шаги решения:

1. Определить список монет с различным достоинством. Например, у нас могут быть монеты номиналом 1, 2, 5, 10, 20, 50 рублей.

2. Создать таблицу, где строки представляют всевозможные значения сумм денег от 0 до заданной суммы, а столбцы представляют номиналы монет.

3. Заполнить таблицу. Для каждой суммы денег и каждого номинала монеты определить минимальное количество монет, необходимых для размена этой суммы.

– Для первой строки таблицы (сумма 0) количество монет для всех номиналов будет равно 0.

– Для каждой следующей строки таблицы вычислить минимальное количество монет для каждого номинала монеты:

* Если номинал монеты больше текущей суммы, то сохранить предыдущее значение.

* Иначе, найти минимальное значение монеты, которое получается из разности между текущей суммой и номиналом монеты, и прибавить 1.

4. После заполнения таблицы, значение в правом нижнем углу будет представлять минимальное количество монет для размена всей суммы. Также можно вернуться по значениям в таблице от правого нижнего угла к началу и определить, какие монеты использовались для размена суммы.

5. Вернуть список монет, используемых для размена суммы.