В СССР были монеты достоинством 1, 2, 3, 5, 10, 15, 20, 50 копеек и один рубль. Автомат разменивает любую монету, начиная с 5 копеек, на четыре монеты. На какое наибольшее число монет можно наверняка разменять монету, достоинством 1 рубль?

задан 19 Июн '17 1:32

3

Пожалуй, 46 можно гарантировать, а больше не получится. Для каждой монеты последовательно определим минимальное число монет, получаемых в результате размена: 5-4; 10(3+3+3+1)-4; 15(10+2+2+1)-7; 20(15+2+2+1)-10; 50(15+15+10+10)-22; 100(50+20+20+10)-46.

(19 Июн '17 2:22) Urt

@Urt, большое спасибо! Правда, не совсем ясно, как толковать слово "наверняка" в условии...

(20 Июн '17 1:16) Аллочка Шакед
2

@Аллочка Шакед: по-моему, трактовка тут вполне однозначная. Мы опускаем рубль, нам автомат что-то выдаёт по своему усмотрению. Продолжаем размен дальше, пока это возможно. В конце получается какое-то значение для данного способа размена, когда дальше разменивать уже нельзя. Минимум значений по всем таким способам и есть ответ. Других трактовок вроде как не просматривается.

(20 Июн '17 1:33) falcao

@falcao а автомат типа живой человек он может на свое усматрение чтото делать? По моему любой автомат программируют люди и он следует тому алгоритму который в него заложен. Минимум значений невозможно узнать если присутствует фактор рандомности. Да и вообще я задачу по другому понял, куда логичнее и интереснее найти наибольшее число монет.

(21 Июн '17 9:35) night-raven
10|600 символов нужно символов осталось
0

У меня получилось улучшить результат @Urt. Я написал программу которая нашла оптимальное решение. Вообщем чтобы получить наибольшее кол-во монет нам нужно использовать автомат для размена монет наибольшее возможное кол-во раз.

Кидаем в автомат рубль. Он нам выдает $%\{ 10,20,20,50\} $%. Далее размениваем $%10$% копеек на $%\{ 1,1,3,5\} $%, теперь меняем $%5$% копеек. Итого, после размена $%10$% копеек имеем $%\{ 1,1,1,1,1,2,3\} $% монет.

Далее меняем $%20$% копеек на $%\{ 5,5,5,5\} $%. Повторив для каждой пятерки получим $%12$% монет в одну копейку и $%4$% монет в две копейки. Итого, после размена $%20$% копеек имеем $%16$% монет. Со второй двадцаткой поступаем аналогично.

Осталось разменять $%50$% копеек. Кидаем в автомат и получаем $%\{ 5,5,20,20\} $%. Меняем пятерки и двадцатки по схеме выше. В итоге, чтобы получить наибольшее кол-во монет нам нужно разменять $%19$% пятерок плюс $%3 $% монеты которые мы не можем разменять. Получаем оптимальное решение: $$(1112) \cdot 19 + (113) = 59 \times 1 + 19 \times 2 + 1 \times 3 = 100$$

Что дает $%59 + 19 + 1 = 79$% монет.

alt text

ссылка

отвечен 21 Июн '17 5:52

1

Автомат меняет монеты по своему усмотрению, поэтому размен 10 на 1 1 3 5 - это просто удача, позволяющая получить больше монет чем при другом варианте ответа автомата. Вопрос стоял не в том, какое число самое большое из возможных, а какое число монет можно гарантировать!

(21 Июн '17 8:50) knop

Нигде не сказано, что автомат должен следовать определенному порядку раздачи монет при размене. Ну я так и понял задачу что нужно описать схему позволяющую получить с рубля наибольшее кол-во монет следуя протоколу размена. Вообще условие "На какое наибольшее число монет можно наверняка..." неоднозначно задано что подразумевается под наверняка? Чтобы знать наверняка автомат должен всегда следовать определенному алгоритму. То есть алгоритм должен быть детерминованным иначе как именно автомат разменяет определенную монету нам будет известно лишь с некой вероятностью.

(21 Июн '17 9:27) night-raven

@void_pointer, см. об источнике этой задачи и обсуждение вариантов и деталей здесь. Задача для учеников 5-го класса. При постановке на максимум числа монет ответ 79 получается также элементарно.

(21 Июн '17 10:24) Urt
1

@void_pointer: слово "наверняка" означает вполне понятную вещь -- при любой работе автомата (в том числе самой "худшей" для нас) мы можем получить такое-то число монет.

(21 Июн '17 10:58) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,399
×1,114
×370
×211
×98

задан
19 Июн '17 1:32

показан
925 раз

обновлен
21 Июн '17 10:58

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

по почте:

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

по RSS:

Ответы

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

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