1
1

Постройте жадный алгоритм, который получает на вход натуральное число $%n$% и за время $%O(n)$% находит минимальное число монет номиналом 1 копейка, 5 копеек, 10 копеек и 25 копеек, с помощью которых можно выдать сдачу в $%n$% копеек. Нужно описать алгоритм, доказать его корректность и оценку на время работы.

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

задан 21 Ноя '15 23:43

10|600 символов нужно символов осталось
1

Сначала приведём пример жадного алгоритма, который выдаёт не оптимальный результат. Пусть номиналы монет равны 1, 3, 4 копейкам, и требуется выдать 6 копеек. Тогда жадный алгоритм даст 4+1+1 (три монеты), в то время как способ 3+3 позволяет обойтись двумя.

В первом случае описывать алгоритм нет необходимости -- всё и так ясно. На каждом шаге выдаётся монета максимального достоинства из возможных. То, что время работы равно $%O(n)$%, очевидно, так как даже если всё выдавать по копейке, то потребуется не более $%n$% шагов.

Обоснования требует только тот факт, что жадный алгоритм выдаёт здесь минимально возможное количество монет. Поскольку числа 5, 10, 25 кратны пяти, количество копеек будет давать тот же остаток от деления на 5, что и $%n$%. Если количество монет достоинством в 1 копейку будет равно пяти или более, то количество выдаваемых монет можно уменьшить. Это значит, что оптимальный алгоритм выдаст количество 1-копеечных монет, равное остатку от деления $%n$% на 5. Жадный алгоритм делает то же самое. Поэтому на количество 1-копеечных монет можно оба способа "сократить". После этого производим "деноминацию", деля на 5 достоинства оставшихся монет. Получается 1, 2, 5.

Теперь остаётся обосновать оптимальность жадного алгоритма для этого случая. Поскольку 1+1 можно заменить на 2, а 2+2+2 на 5+1, уменьшая число монет, при оптимальном способе 1-копеечных монет будет не более одной, а 2-копеечных не более двух. Также 2+2+1 можно заменить на 5, то есть всё вместе встретиться не может. Остаются такие случаи: только 1; только 2; 2+1; 2+2. Все остальные монеты выдаются "пятаками", а это в точности то, что делает жадный алгоритм.

ссылка

отвечен 22 Ноя '15 2:55

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×217
×134
×84
×59
×23

задан
21 Ноя '15 23:43

показан
4703 раза

обновлен
22 Ноя '15 2:55

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru