?

Log in

No account? Create an account

Previous Entry | Next Entry

Мозги атрофировались совсем :(
Лет 10 назад, да даже и 5, решил бы задачку с легкостью, а щас не могу...

Стандартная задача - есть 16 монет разных весов, нужно минимальным количеством взвешиваний расположить их по ранжиру. Взвешивать можно только одну с одной.
Как решить?

Теперь немного усложним и приведем к некоему жизненному знаменателю.
Не 16 монет, а 16 бутылок пива. Разного пива :)
Задача та же - отранжировать по степени ацтойности.
Но есть серьезное осложнение - поскольку речь о пиве, то к концу дегустации отличить один вкус от другого будет очень сложно :)
Потому, видимо, придется ранжировать не все 16, а, например, ограничиться Топ-4 (все что хуже все равно больше покупаться не будет :)


Нужна помощь :)
С меня - атчот с фотками :))

Posted via LiveJournal.app.

Comments

( 14 comments — Leave a comment )
i_cherski
Nov. 21st, 2010 07:27 am (UTC)
А в чем тебе нужна помощь? )
the_bpah
Nov. 22nd, 2010 04:53 pm (UTC)
выбрать метод :)
так чтобы успеть достигнуть результата пока не закончатся исходный продукт и восприятие реальности :)))
_bon_bon_
Nov. 21st, 2010 09:12 am (UTC)
жЫзненная комбинаторика?))

Как ты воду смог оценить,а пиво нет?!
the_bpah
Nov. 22nd, 2010 04:55 pm (UTC)
мой рекорд по воде - примерно 4 литра за пару часов
и, не поверишь, вкус мог отличать и после этого :)

с пивом, боюсь, так не получится :)))
takoynickzanyat
Nov. 21st, 2010 10:59 am (UTC)
главное пивко доведи до правильной температуры, а то нормальное пиво запишут в отстой
the_bpah
Nov. 22nd, 2010 04:55 pm (UTC)
все пиво будет одинаковой температуры :)
tersan
Nov. 21st, 2010 04:04 pm (UTC)
надо сплёвывать )
the_bpah
Nov. 22nd, 2010 05:01 pm (UTC)
как же я ждал твой коммент :)
традиционно уже, да :)

пузырьком хорошо, но для вычленения ТОП-4 скорее всего многовато сравнений, если правильные экземпляры в конце

вчера лучшее что пришло в голову - выбрать произвольный референсный образец и сравнить остальные с ним
дальше выборку осуществлять уже только в группе виннеров
если виннеров будет много, то повторить метод
понравилось тем что сравнивать за раз можно не два, а даже три образца (первый -> референсный -> второй)
jktue
Nov. 22nd, 2010 05:05 pm (UTC)
хорошо. вариант номер 2. выбираешь случайную пару -сравниваешь. победителю пишешь +1 очко. лузеру -1 очко. в конце [когда все нажрались] суммируешь - получаешь рейтинг. плюсы: (а) процесс распараллеливается на любое количество участников :)) (б) работает на любое количество времени :)) (в) при определнии топ-N беспрецедентное говно, набирающее по ходу чемпионата -много, можно выкидывать из рассмотрения.
the_bpah
Nov. 22nd, 2010 09:26 pm (UTC)
отличный и очень вкусный вариант :) но давай сравним
в варианте с референсом мы имеем следующее
1 тур - 15 сравнений - группа виннеров 1..15 шт, в среднем 8 :)
2 тур - 8 сравнений - группа виннеров 1..7 шт, в среднем искомые 4 :)
3 тур - по олимпийской системе - 4 сравнения

Итого 27 сравнений, ура :)
Интуитивно понимаю что реальный результат примерно 30-35, математически посчитать не могу :( всё забыл, а ведь когда-то увлекался комбинаторикой...

К-во участников скорее осложняющий фактор, т к вкусы могут отличаться

Потому твой вариант более честный, каждый участник ставит +1 более понравившемуся варианту и 0 лузеру
Далее по сумме баллов
Но к-во сравнений, опять же интуитивно, больше
jktue
Nov. 23rd, 2010 08:44 am (UTC)
я бы сказал, что самый быстрый доказуемо правильный алгоритм это 16*lg(16)=64 операции. по любому уже немало.

мне болбше интересует, где взять 16 worth accounting сортов пыва. глубоко пастеризованное, 95% наименований на полке, сразу можно нахер посылать. одинаковая шняга в независимости от цены и этикетки.
the_bpah
Nov. 23rd, 2010 08:47 am (UTC)
а как 16*lg(16) посчитано? почему именно столько?
мне одновременно и стыдно за то что я все забыл, и очень любопытно


ассортимент седьмого континента на Смоленке - 12 сортов нефильтрованного пива
еще 3 найдены в азбуке вкуса на ленинградке и одно щас активно продвигается на ВР (5 бутылок - бокал в подарок)
каждая бутыль в пределах 100..160 руб
jktue
Nov. 23rd, 2010 01:45 pm (UTC)
Идея примерно такая же, как в твоем предложении - деление пополам. n lg(n) результат решения С(n)=n+2C(n/2). берем первого кандидата. Массив поделен на две части. лучше первого, хуже или равны первому. В идеале поделили пополам.

Ты предлагаешь тоже самое, только сортировать нужную половину, забив на хвост, т.е. С(n)=(n-1)+c(n/2).
( 14 comments — Leave a comment )