Задача
В Англии валютой являются фунты стерлингов £ и пенсы p, и в обращении есть восемь монет:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) и £2 (200p).
£2 возможно составить следующим образом:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
Сколькими разными способами можно составить £2, используя любое количество монет?
Решение
Решение у меня получилось рекурсивное.
Рассмотрим для простоты сумму монет, равную 7. Начнём с представления этой суммы монетами по 1:
- 1 1 1 1 1 1 1
Далее возьмём монету 2 и заменим ею две монеты по 1:
- 2 1 1 1 1 1
Теперь нужно найти все варианты, которые остались в комбинации с этой 2, а именно перейти в рекурсию и начать делать то же самое с 1 1 1 1 1:
- 2 (2 1 1 1)
Нужно также перебрать оставшиеся 1 1 1, поэтому попадаем на новый уровень рекурсии:
- 2 (2 (2 1))
Все варианты перебраны и мы возвращаемся обратно на самый верхний уровень.
Следующая монета это 5, представляем сумму c одной 5:
- 5 1 1
Повторяем перебор с уходом в рекурсию:
- 5 (2)
И тут надо обратить внимание, что как только мы на верхнем уровне рекурсии перебрали последовательно 2 и 5, то же самое произойдёт и в нижних уровнях, ведь это рекурсия. То есть в ранее описанном примере:
- 2 (2 1 1 1)
также произойдёт:
- 2 (5)
Комбинации монет 2 5 и 5 2 это один и тот же вариант, который должен считаться только один раз. Поэтому в верхнем уровне мы всегда рекурсивно ищем такие комбинации, в которых присутствует монета не меньшего номинала, чем текущая. То есть, из 5 1 1 мы не можем искать 5 2, т.к. 2 меньше чем 5, и комбинация 2 5 уже встречалась в предыдущих рекурсиях. Из 5 1 1 мы можем искать только 5 5, но такая комбинация уже не подходит.
Ссылка на онлайн-компилятор языка C с текстом программы
В функцию check() передаётся индекс монеты и оставшаяся сумма. Первоначально это монета с индексом 0 (и с номиналом 2) и сумма 200.
Если можно вычесть из суммы номинал монеты, это даёт нам один вариант, и далее сразу рекурсивно проверяем следующий вариант: та же монета, но сумма меньше на номинал.
После того как вернулись из рекурсии, увеличиваем индекс монеты и получаем следующий номинал и опять всё повторяем.
Подборка всех задач: