Форумы-->Форум для внеигровых тем-->
1|2
| Автор | Вычислительная задача:монетки |
|---|
У нас есть неограниченное число монет и купюр по 1, 2, 5, 10, 50, 100, 500, 1000, 5000 рублей.
Покупаем поочерёдно товар за 1, 2, 3, ... N рублей
Тратим при этом только минимальное количество купюр и монет (4999 = 4*1000р + 1*500р + 4*100р + 1*50р + 4*10р + 1*5р + 2*2р и т.д.)
Картина расходования купюр и монет при разных диапазонах цен товаров - разная, а именно такая:
N=5000 -> 1х5000р, 10000х1000р, 2500х500р, 10000х100р, 2500х50р, 10000х10р, 2500х5р, 4000х2р, 2000х1р
N=1000 -> 1х1000р, 500х500р, 2000х100р, 500х50р, 2000х10р, 500х5р, 800х2р, 400х1р
N=500 -> 1х500р, 1000х100р, 250х50р, 1000х10р, 250х5р, 400х2р, 200х1р
N=100 -> 1х100р, 50х50р, 200х10р, 50х5р, 80х2р, 40х1р
N=50 -> 1х50р, 100х10р, 25х5р, 40х2р, 20х1р
N=10 -> 1х10р, 5х5р, 8х2р, 4х1р
При N=500 - N=5000 купюры 500 и 50 тратятся в 4 раза реже, чем 1000 и 100
При каких номиналах купюр/монет, выпускаемых монетным двором, расходование купюр/монет будет максимально равномерно?
Количество разнообразных купюр/монет не должно превышать 20шт и должно стремиться к минимуму. | N=5000 -> 1х5000р, 10000х1000р, 2500х500р, 10000х100р, 2500х50р, 10000х10р, 2500х5р, 4000х2р, 2000х1р
А можно пояснение? Что есть N и какова общая формула? | | Покупаем поочерёдно товар за 1, 2, 3, ... N рублей | | сумма монет = 5000 = N | | Нет я все неправильно понял..надо еще разок перечитать.Где мой задачник по теории вероятностей для рулетки. | N(x)=1+min{N(x-c(i))}|i:C(i)<=x}
N(x) - количество монет/купюр, необходимых для выплаты суммы х
c(i) - номинал i-й монеты
N(0)=0
N(1)=1 (откуда следует, что минимальный номинал должен быть равен 1)
Дальше по рекурсии
Таким образом получаем минимальное количество монет для выплаты суммы х
После чего можно просчитать частоту использования монет для произвольного набора номиналов.
Я думаю, оптимальна последовательность 1,2,5,10,25,50,100 по той простой причине, что она используется в большинстве стран мира. | о той простой причине, что она используется в большинстве стран мира.
большинство людей за всю историю человечества... мёртвые
большинство оно такое, что и дураками бывает
формула занятная, подумаю | N=5000 -> 1х5000р, 10000х1000р, 2500х500р, 10000х100р, 2500х50р, 10000х10р, 2500х5р, 4000х2р, 2000х1р
А можно пояснение? Что есть N и какова общая формула?
чтобы купить товар за 1 рубль, а потом купить товар за 2 рубля, а потом купить товар за 3 рубля, ... , а потом купить товар за 5000 рублей
надо истратить: 1х5000рублей, 10000х1000рублей, 2500х500рублей, 10000х100рублей, 2500х50рублей, 10000х10рублей, 2500х5рублей, 4000х2рублей, 2000х1рублей
Вопрос: какой номинал купюр/монет надо использовать в стране, чтобы купюры/монеты тратились максимально равномерно?
Ясен пень, что стопка купюр 1,2,3,....4999,5000 потратится равномерно, поэтому должно быть какое-то разумное ограничение в 10-20 разных номиналов | оптимальна последовательность 1,2,5,10,25,50,100 по той простой причине, что она используется в большинстве стран мира
Нет, просто с такой системой удобнее считать, чем например с купюрами по 2,4,8,16,32,64.
Кстати, если с 1,5,10,50,100 понятно, то 2 может заменяться на 3, как в СССР, или отсутствовать. 25 может меняться на 20. Так что тут ещё неизвестно что лучше
А по задаче - вопрос не понятен. Что значит расходование купюр/монет будет максимально равномерно? | N(x)=1+min{N(x-c(i))}|i:C(i)<=x}
Таким образом получаем минимальное количество монет для выплаты суммы х
Не получаем, кстати. В общем виде. На собеседованиях кандидатов постоянно так валю)))
Допустим, есть номиналы 20, 14, 1 (для наглядности). Нужно заплатить 29. По такой формуле мы заплатим 20 и 9 раз по 1 (10 купюр), а минимальное - 2 по 14 и 1 (3 купюры).
Но это справедливо только в общем виде. В реальности, когда старшая купюра минимум в 2 раза больше младшей, так считать можно.
А задачка интересная, жаль, что сейчас времени нет. На выходных если только получится попробовать. | | Походу купюры в 1,2,4,8,16 и так вплоть до 524228 (от 2^0 до 2^19) будут использоваться абсолютно равномерно | При N=2^K-1 (при любом целом K) любая купюра будет использована ровно N/2 раз
При других значения N равномерность будет слегка нарушаться | для Akron:
Неа.
1х10р, 5х5р, 8х2р, 4х1р
Если мы покупаем такое количество товаров по таким ценам, при условии невозможности купить несколько единиц товара за одну купюру, это и будет оптимальным распределением. Т.е. 1 по 10, 5 по 5 и т.д. | для FireSwarm:
Да, я всё прикинул. Например, при N=255 каждая купюра от 1 до 128 будет использована ровно 128 раз. То есть 128 штук по 1, 128 по 2, 128 по 4, 128 по 8 и так далее, и 128 по 128. | для FireSwarm:
Не получаем, кстати. В общем виде. На собеседованиях кандидатов постоянно так валю)))
Допустим, есть номиналы 20, 14, 1 (для наглядности). Нужно заплатить 29. По такой формуле мы заплатим 20 и 9 раз по 1 (10 купюр), а минимальное - 2 по 14 и 1 (3 купюры).
Получаем.
N(1)=1
N(2)=1+N(2-1)=2 // 1+1
...
N(13)=13 // 13x1
// начиная с 14 появляется новый номинал
N(14)=1+min{N(14-1), N(14-14)}=1+min{N(13),N(0)}=1
N(15)=1+min{N(15-1), N(15-14)}=2 // 14+1
...
// с 20 следующий номинал
N(20)=1
N(29)=1+min{N(29-1), N(29-14), N(29-20)}=1+N(15)=3 // 14+14+1
Так что зря кандидатов валите. Это классическая задачка на динамическое программирование. Оптимальная последовательность выдачи монеток должна содержать в себе оптимальную подпоследовательность.
По теме - задача сформулирована странновато.
Одного номинала в 1 коп достаточно для выдачи любой суммы и распределение - равномернее не бывает. Но монет таскать придется много :)
При наличии номиналов на произвольную сумму х на выдачу любой суммы уйдет ровно одна купюра, распределение опять же равномерное.
Итого 2 тривиальных решения уже есть.
Видимо, имеется в виду фиксированное количество номиналов.
Также (неявно) предполагается, что все возможные значения сумм выдачи равновероятны. | для Monsieur:
Не зря валю... Твоего решения не предоставляют. Все написанные программки на этом примере валятся, так что у них точно что-то не так. А простейшее решение задачи - поиск в ширину. Что ты, вроде как и описал. Только у тебя поиск с конца идет. | для Akron:
Ты абсолютно прав . Если N записать в двоичной системе счисления , то это и будет купировка суммы - 1- берём купюру , 0- не берём . Очевидно , что именно так достигается максимальная равномерность при купировке N последовательных сумм . | для Monsieur:
Сказано Количество разнообразных купюр/монет не должно превышать 20шт и должно стремиться к минимуму
Ну и как тут подходят варианты с 1 копейкой и все возможные номиналы?
При моём варианте в 20 номиналов и не более 20 штук охватывается интервал от 1 до более чем миллиона, или от 1 копейки до 10000 рублей | У нас есть неограниченное число монет и купюр по 1, 2, 5, 10, 50, 100, 500, 1000, 5000 рублей.
Зачем при таком счастье решать какие-то задачки? | для Akron:
Сказано Количество разнообразных купюр/монет не должно превышать 20шт и должно стремиться к минимуму
Ну и как тут подходят варианты с 1 копейкой и все возможные номиналы?
Номинала в 1 копейку достаточно длы выдачи любой суммы денег.
Распределение купюр равномерное, так как в обороте используется 1 купюра/монета.
Количество номиналов при этом заведомо минимально, так как равно 1.
Все (оговоренные) условия задачи выполнены. |
1|2К списку тем
|
