273

Как насчёт монеток?

Значит так, посмотрел давеча видео Кевина, того, который Vsauce, про "наггетсовый" алгоритм. Ну и вот там, среди всего прочего, было то, что набор монеток мелочи, ну то есть существующие номиналы монеток - это не самое оптимальное решение, чисто математически. И вот тут я сразу понял, что обязательно заморочусь насчёт кое-какого дела... Сейчас объясню в чём суть:

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

В моей стране (Беларусь) мелочь отчеканена монетами, номиналом в 1, 2, 5, 10, 20 и 50 копеек. То есть всего шесть номиналов. Разные номиналы, понятное дело, сделаны для того, чтобы суммы, размером от 1 до 99 копеек было удобно отсчитывать небольшим количеством монет. Например, нужно вам 73 копейки - хорошо: это 1х(50) + 1х(20) + 1х(2) + 1х(1), то есть всего четыре монетки, если у вас есть монетки нужных номиналов под рукой.

Практично, не так ли? Очень удобно отсчитывать любую сумму. На практике. Человеку. Но чисто математически: это ли оптимальные номиналы монеток? То есть правда ли, что при наборе суммы от 1 до 99 копеек с таким набором монет из шести номиналов, получается так, что в среднем используется меньше всего монеток? И... Нет!

А как узнать, каков оптимальный набор монеток, тогда? Ну, будь я математиком, я бы точно полез куда-нибудь в дебри матанализа и накопал кучу всего и всякого полезного, что точно, основательно и однозначно давало бы ответ на данный вопрос.

Но... Из математика может получиться программист, а вот из программиста математик - уже никогда. В конце концов когда можно вычислить ответ просто брутфорсом даже на своём унылом ПК, кому пойдёт в голову лезть в матанализ?

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

В общем, в код вдаваться сильно не буду. Комп просто генерирует все возможные комбинации номиналов монеток, потом для каждой комбинации оптимальным образом разменивает все суммы от 1 до 99, запоминая, сколько монеток требуется для каждой суммы. Ну то есть сначала он разменивает 1 - получается нужна одна монетка с номиналом 1, потом 2 - тут уже зависит от того, какие номиналы есть в текущем наборе: либо две монеты по 1, либо одна номиналом 2, если такая в наборе есть. Дальше, в процессе своего титанического труда, которым он занимается прямо сейчас, пока я пишу этот пост, он вычисляет среднее арифметическое от того, сколько монеток требовалось ему для размена каждой суммы. У какого набора монеток такое среднее арифметическое меньше, тот, очевидно, и есть самый лучший с точки зрения экономии монеток из всех.

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

Как насчёт монеток? Программирование, Математика, IT, Длиннопост

В окне консоли первые шесть чисел - номиналы монеток в наборе, а самое правое - среднее количество монеток, которое нужно для размена всех сумм от 1 до 99 таким набором.

И если для четырёх номиналов программа высчитывает результат практически мгновенно, то для шести... Несколько часов. Разумеется, по сути считается на один номинал меньше, потому что самая младшая монетка всегда должна иметь достоинство в 1 - иным набором любую сумму просто не разменять.

Итааак, дамы и господа, леди и джентльмены!

Я рад вам сообщить, что если бы все люди умели считать как чёртовы машины и некруглые большие числа никого не смущали, то номиналы монеток лучше всего было бы сделать такими:

Как насчёт монеток? Программирование, Математика, IT, Длиннопост

(1), (2), (5), (11), (25), (62) для шести номиналов. Близко к тому, что есть, но не то же самое, однако. При этом вы бы тратили в среднем 3.16 монеток, для того, чтобы отсчитывать ими мелкие суммы.
А вот при наборе из шести номиналов (1), (2), (5), (10), (20), (50) этот показатель составляет аж 3.43 !

"Какой ужас!"

Желаете отчеканить всего 5 номиналов монет для казны, сударь?
Ваш математически лучший выбор:
(1), (3), (7), (16), (40)  и тогда в среднем нужно будет 3.49 монетки для того, чтобы составить нужную сумму мелочи.

4 номинала? Ну, тогда (1), (3), (11), (38) конечно! Ведь именно такой набор требует в среднем лучшие 4.14 монетки для размена мелочи!


А в категории три номинала побеждает (1), (5), (22) со средним количеством необходимых монет в 5.31

Ну что ж...

Сердечно поздравляю всех, кто дочитал до этого места (именно дочитал, а не доскроллил). Теперь вы знаете забавную информацию, добытую парой часов процессорного времени. И я очень надеюсь, что это знание вас хоть немного развлечёт, как развлекло меня.

На этом у меня всё. Всем добра :3