Сколько монет различных номиналов потребуется для получения сдачи в n рублей, если у вас есть монеты в номиналах

Тема урока: Подсчет монет для получения сдачи

Пояснение: Для решения этой задачи нам необходимо определить, сколько монет различных номиналов понадобится для получения сдачи в заданном количестве рублей. У нас есть монеты в номиналах 1 рубль, 2 рубля, 5 рублей и 10 рублей. Наша цель - использовать минимальное количество монет.

Для решения этой задачи мы можем использовать жадный алгоритм. Мы начинаем со сдачи в размере n рублей и постепенно вычитаем из этого значения монеты максимального номинала, пока не получим сдачу равную нулю. При этом мы подсчитываем количество использованных монет каждого номинала.

Например, если мы должны выдать сдачу в 2 рубля, мы начинаем со значения 2 и вычитаем монеты максимального номинала (10 рублей нет в нашем наборе). Первое вычитание - монета номиналом в 1 рубль, остаток составляет 1 рубль. Второе вычитание - монета номиналом в 1 рубль, остаток равен 0 рублей. Таким образом, для получения сдачи в 2 рубля нам понадобится 2 монеты по 1 рублю.

Например: Допустим, нам нужно получить сдачу в 7 рублей. Программа должна выполнить следующие шаги:
1. Вычитаем 5 (максимальный номинал). Остаток составляет 2 рубля.
2. Вычитаем 2 (максимальный номинал). Остаток равен 0 рублей.
3. Для получения сдачи в 7 рублей потребуется 2 монеты по 5 рублей и 1 монета по 2 рубля.

Совет: При решении подобных задач полезно начать с монеты максимального номинала и продолжать с использованием монет с наивысшим номиналом, пока не достигнем желаемой сдачи. Это поможет нам использовать минимальное количество монет.

Дополнительное задание: Сколько монет различных номиналов потребуется для получения сдачи в 17 рублей?