Ещё раз о количестве способов набрать сдачу в n рублей из заданного набора монет/купюр
Вот известная задача: «Имеется неограниченное количество монет достоинством 1, 2, 5 и 10 рублей. Определить, сколькими способами можно ими выдать сдачу в n рублей».
Я, бывший преподаватель информатики, хочу рассказать профессионалам, экспертам, знатокам и гуру о придуманной мной (если это не «изобретение велосипеда») идее решения задачи без перебора всех возможных вариантов (без четырёх вложенных циклов).
Возможно, эта идея будет полезна в других задачах.
Итак.
При n = 7 все варианты следующие:
1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 2 + 2
1 + 2 + 2 + 2
1 + 1 + 5
2 + 5
Среди них можно выделить те, в которых минимальным слагаемым является 1. Их – 5. В оставшемся шестом варианте минимальным слагаемым является 2. Вариантов, в которых минимальным слагаемым является 5 и 10, в данном случае нет.
При n = 10 все варианты следующие (без знака +):
1111111111, 111111112, 11111122, 1111222, 112222, 111115, 11125, 1225, 22222, 55, 10,
то есть
количество вариантов с минимальным слагаемым 1 равно 8;
количество вариантов с минимальным слагаемым 2 равно 1;
количество вариантов с минимальным слагаемым 5 равно 1;
количество вариантов с минимальным слагаемым 10 равно 1.
Подумав (😊), можем сказать, что при n = 11:
· количество вариантов с минимальным слагаемым 1 будет таким же, как общее число всех вариантов для n = 10 (так как разность 11 – 10 не превышает 1);
· количество вариантов с минимальным слагаемым 2 будет равно сумме количеств с минимальными слагаемыми 2, 5 и 10 для n = 9 (так как разность 11 – 9 не превышает 2);
· количество вариантов с минимальным слагаемым 5 будет равно сумме количеств с минимальными слагаемыми 5 и 10 для n = 6 (так как разность 11 – 6 не превышает 5);
· количество вариантов с минимальным слагаемым 10 будет равно такому же количеству для n = 1 (так как разность 11 – 1 не превышает 10).
Приведённые рекуррентные зависимости применимы для всех значений n, но с некоторыми исключениями – при n = 1 количество вариантов с минимальным слагаемым 1, при n = 2 количество вариантов с минимальным слагаемым 2, при n = 5 количество вариантов с минимальным слагаемым 5 и при n = 10 количество вариантов с минимальным слагаемым 10 будет равно 1 (в перечисленных случаях соответствующие слагаемые появляются впервые).
Допустим, что максимальное значение n равно 99.
В программе, реализующей описанную идею для такого случая, можно использовать двумерный массив из 109 строк и пяти столбцов (10 начальных строк массива являются условными для рекуррентного расчёта значений при n = 1..99).
Вся программа на так называемом «школьном алгоритмическом языке» (система программирования КуМир):
алг
нач цел таб м[-9:99, 1:5], цел n, j
| Нули, в том числе в фиктивных строках
нц для n от -9 до 99
нц для j от 1 до 5
м[n, j] := 0
кц
кц
| Расчёты
нц для n от 1 до 99
если n = 1
то
м[n, 1] := 1
иначе | Рекуррентная зависимость
м[n, 1] := м[n - 1, 5]
все
если n = 2
то
м[n, 2] := 1 иначе
м[n, 2] := м[n - 2, 2] + м[n - 2, 3] + м[n - 2, 4]
все
если n = 5
то
м[n, 3] := 1
иначе
м[n, 3] := м[n - 5, 3] + м[n - 5, 4]
все
если n = 10
то
м[n, 4] := 1
иначе
м[n, 4] := м[n - 10, 4]
все
| Последний столбец
м[n, 5] := м[n, 1] + м[n, 2] + м[n, 3] + м[n, 4]
кц
| Вывод всех значений
нц для n от 1 до 99
вывод нс, n, " | ", м[n, 5]
кц
кон
Конечно, вместо массива из 109 строк можно использовать 10-строковый массив и после расчёта значений для очередной строки переписать массив, отбросив «хвостовую» строку.
Спасибо.
