Cross3

и я хрен его знаю по какой причине автор, я и еще черт знает сколько народу (у поста на данный момент рейтинг 229, что по нынешним временам уже горячее) в субботу вечером задались этим вопросом, но факт остается фактом, задача была поставлена, надо решать.

В силу нежелания упарываться в глухую математику, автором было принято решение накидать пару строк кода и, взяв попкорн, наслаждаться тем как впахивают роботы, а не человек. Или проще говоря забрутфорсить.
Конкретно, от бездушной машины требовалось дать ответ на вопрос: "А при каком наборе из 3/4/5/6 номиналов копеечных монет достижение любой суммы от 1 копейки до 99 копеек, в среднем, потребует наименьшее количество презренного метала?". Ну вот такой маленький этюдик на тему "А что если бы хоть что-то в этом мире решалось не от балды, а исходя из сурового математического моделирования".
И автор это запрогал. Ну вот так, прикиньте, просто взял и запрогал. Натурально. На шарпе. И пост об этом написал. И скриншот кода приложил. И даже результаты своего исследования в пост включил. Со всем этим, кстати, вы можете ознакомиться, перейдя в головной пост. Но, как мы все понимаем, я бы не занимался сейчас этим словоблудием, если бы не

А именно в одном из первых комментов его алгоритм был взвешен, был измерен, возможно даже был понят, но в конечном итоге признан пользователем @TackleTart негодным. Ошибку он в нем нашел, короче, которая была автором тут же признана. Что естественным образом помножило все удовольствие (ну большую его часть) от поста на ноль.
А потом я спать пошел.
Ну ночь уже была, не осуждайте.
Но утром я естественно первым делом вспомнил, что в интернете кто-то не прав и отправился смотреть что изменилось в посте за ночь. В посте не изменилось ничего. "Ну ясен пень, Cross3" - скажете вы - "ты ж не один ночью спал". "Нет" - гордо отвечу я вам - "я этой ночью спал один". Прошу прощения, отвлекся.
Ну в общем, задача была не решена, опубликованные данные были не верны, и я понял, что

И я ее решил.
О чем и сообщил в комментах автору исходного поста. Оказалось, что он тоже исправил свой код и собирался пилить об этом новый пост. Но, по уже сложившейся доброй традиции

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

Так вот собственно пост (наконец-то да?).
По результатам работы программы получились следующие оптимальные номиналы монет:
набор из 3х монет - 1копейка 12копеек 19копеек, среднее количество монет для сумм 1..99 - 5,20;

набор из 4х монет - 1коп 5коп 18коп 25коп, среднее - 3,93;

набор из 5и монет - 1коп 5коп 16коп 23коп 33коп, среднее - 3,32;

набор из 6и монет - 1коп 4коп 6коп 21коп 30коп 37коп, среднее - 2,95.

Присутствие монеты в 1к во всех наборах вас удивлять не должно, ибо диапазон [1:99] как бы намекает, что одну копейку тоже надо как-то заплатить.
Как видите, наборы сильно отличаются от привычных нам номиналов 1 5 10 50(в России) или 1 2 5 10 20 50(у автора указано, что в его стране так). Естественно, полученные значения никем не проверялись. Если вы сделаете самостоятельные вычисления и сможете подтвердить или опровергнуть мои данные, то мы нахуярим еще кучу ответов на посты сможем их обсудить.

Теперь, дабы не быть голословным, пару слов об алгоритме вычисления. Если вы хотите решить задачу сами и независимо сравнить ваши данные с моими, то наверное, на этом пост для вас закончен, спасибо за внимание, ждем ваши значения.
Если же вы по какой-то причине еще читаете эту хрень (может еще одно лицо Нерона ждете, я хз), то говорю сразу Нерона больше не будет код я выкладывать в пост не буду. Причина этому проста. Я не профессиональный программист, а потому:
1) Мой код выглядит как говно. Переменные названы абы как, нет нормального редактирования, отступов, комментариев и прочих вещей, которые мне вне проф деятельности на хер не упали;
2) У меня нет на компе даже visual studio, а потому пришлось писать на чем бог послал. А бог сегодня послал мне среду FreePascal 3.2.2.
3)Я стесняюсь.
Короче, вы и сами вряд ли хотите в ночь на понедельник читать чужой говнокод на языке давно забытой цивилизации.
Поэтому алгоритм я вам щас на пальцах обрисую.

Я думаю, алгоритм брутфорса всех возможных наборов монет особо описывать не надо. Там просто куча вложенных циклов. Первая монетка всегда 1, вторая - перебор от 2 до 97, третья - от 3 до 98 ну и т.д. Главное чтобы последняя заканчивалась на 99.
Интерес представляет непосредственно алгоритм расчета минимального количества монет из заданного набора номиналов, необходимый для набора всех сумм от 1 до 99.
И тут все, на удивление, просто. Мы перебираем все числа от 1 до 99 и каждому из них должны присвоить в соответствие искомое число. Как? Ну, для начала если рассматриваемая сумма равна номиналу любой из монеток, то, очевидно, искомое число - 1. Тут все понятно. Есть у вас в кошельке монетки по 1коп, 5коп, 10коп, 50коп. Продавец просит заплатить 50коп. Что надо сделать? Правильно, достать одну монету на 50коп и заплатить. Едем дальше. А что если сумма не равна номиналу монетки? А тогда мы берем и отнимаем по очереди каждую из монеток и попадаем в новую сумму, которую мы уже вычисляли.

Не понятно? Тогда конкретный пример.
Для примера рассмотрим набор из трех монет 1коп, 12коп, 19коп. Это тот самый минимальный набор из трех номиналов. Так вот:

На скрине показан расчет для этого набора в формате "сумма от 1 до 99"-"искомое минимальное количество монет". Рассмотрим, к примеру, сумму 59. Вычтем из нее по одной монете каждого номинала: 59-1=58; 59-12=47; 59-19=40. Теперь рассмотрим полученные после вычитания суммы. Сумме 58 соответствует уже полученное ранее число 4; сумме 47 - число 7; сумме 40 - число 4. А теперь главная мысль: каждая из полученных сумм находится всего в одной монете от изначальной 59. И получается, что искомая сумма это min(4,7,4)+1=5. И эту 5 мы теперь запоминаем и с ее помощью сможем считать последующие суммы. Т.е. мы имеем банальную задачу на поиск пути в простом графе. Или я это только что придумал. Хз, меня с математического десять лет назад за пьянку выгнали. Все!

Надеюсь популярно объяснил. Если нет, то жду в комментах, попробую пояснить.
Ну а дальше мы просто считаем среднее арифметическое всех полученных чисел в таблице. Как видите, для этого набора оно равно 5.20.

Какие выводы можно сделать из результатов исследования?
Если когда-нибудь на президентских выборах вы будете сомневаться что вряд ли между кандидатом математиком и кандидатом юристом, то смело голосуйте за юриста. А то выберете математика, он как начнет вам процессы в стране оптимизировать, а вы потом в аптеке в очереди будете пытаться за презервативы сумму типа *руб 73коп монетами набрать по 19коп. Оно вам надо?

Если кто-то это дочитал, то спасибо за внимание. Надеюсь на дискуссию в комментах. И если у вас есть подобные странные и веселые задачи для математиков, то делитесь, я уверен они оценят.