Обмен денег
Эта задача была взята из CourseraСпециализация по структурам данных и алгоритмам, а именно изКурса по набору инструментов для алгоритмов, неделя 3: >Жадные алгоритмы, которые я недавно завершил. Если вы проходите этот курс или планируете его пройти, пожалуйста, не заглядывайте вперед на решение, так как оно будет противоречить Кодексу чести и не принесет вам никакой пользы.
Введение проблемы
В этой задаче вы разработаете алгоритм оптимального обмена денег.
описание проблемы
Задача. Цель этой задачи — найти минимальное количество монет, необходимое для замены входного значения (целого числа) на монеты номиналом 1, 5 и 10.
Формат ввода: ввод состоит из одного целого числа m
Ограничения: 1 ≤ m ≤ 10^3
Формат вывода: Выведите минимальное количество монет достоинством 1, 5, 10, что изменяет m.
Ограничения по времени: C: 1 сек, C++: 1 сек, Java: 1,5 сек. , Python: 5 сек. C#: 1,5 секунды, Haskell: 2 секунды, JavaScript: 3 секунды, Ruby: 3 секунды, Scala: 3 секунды.
Ограничение памяти: 512 МБ
Образец 1
Ввод:
2
Вывод:
2
Объяснение:
2 = 1 + 1.
Образец 2.
Ввод:
28
Вывод:
6
Объяснение:
28 = 10 + 10 + 5 + 1 + 1 + 1.
Что делать
Чтобы разработать жадный алгоритм для этой задачи, поэкспериментируйте с небольшими значениями m (рассмотрите, например, примеры тестов).
Мое решение:
Объяснение:
Ну, это очень простой алгоритм, на самом деле. Нет необходимости реализовывать сложный алгоритм, этот наивный алгоритм прекрасно справляется со своей задачей. Если вы этого не понимаете, просто ответьте на эту статью, и я обязательно дам вам ответ и, надеюсь, удовлетворительное объяснение.
Если вы можете придумать какой-либо другой способ улучшить этот алгоритм или указать на то, что, по вашему мнению, я сделал неправильно, мы будем добро пожаловать, чтобы связаться со мной, ответив этому и указывая на ошибки. Если вам нравится это решение, нажмите кнопку «Рекомендовать» ниже, это много значит для меня. Спасибо.
