Как решить задачу с перебором? Задача следующая:
"Имеется некоторое фиксированное количество монет номиналами 2,3,5. Необходимо составить алгоритм действий, который гарантированно проверит возможность получения задаваемого числа, суммированием имеющимся в наличии монет."
Думал решить через динамический массив и рекурсию, но пока плохо в этом разбераюсь. Может есть другое решение, попроще

30 Дек 2020 в 19:44
119 +1
0
Ответы
1

Для решения данной задачи можно воспользоваться методом жадного алгоритма.

Начнем с проверки возможности получения заданного числа с использованием монеты номиналом 5. Если число делится на 5 без остатка, значит задача решена, так как можно получить это число, используя только монеты номиналом 5.

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

Если оставшееся число не делится на 3 без остатка, то проверяем возможность получения числа, используя монеты номиналами 5, 3 и 2.

Повторяем шаги 2-3 до тех пор, пока не удастся получить заданное число с использованием имеющихся монет.

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

17 Апр 2024 в 21:22
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир