Принцесса решила выйти замуж. Для этого она пригласила 10 принцев для смотра претендентов. Принцы заходят по-очереди. Очередному зашедшему принцу устраивается королевский ЕГЭ, на котором он получает от 0 до 10 баллов. Принцесса заинтересована найти будущего мужа с наибольшим результатом ЕГЭ. Узнав очередной результат, принцесса может сказать "ДА", после чего претендент становится мужем и смотр прекращается, или "НЕТ" - тогда принц обижается и покидает королевство навсегда.

Какой должен быть алгоритм у принцессы, чтобы получить мужа по возможности с большим баллом? Считаем равной вероятность получения любого балла любым принцем.

жесть

+(0) Да, принцесса обязана выйти замуж - иначе монастырь

макс "балл" должен быть 22

да она грит. мол отсортируйтесь в порядке убывания
и она первому говорит "Да"

(4) не катит, никто не знает заранее результата ЕГЭ

(5) примерно каждый 10-й будет иметь 10 баллов.
значит она просто опрашивает. и когда будет принц с 10-ю баллами. она грит Да. По теории вероятности у одного должно быть 10-ть баллов.

(6) если не будет, то она вынуждена выйти за последнего, у него средний результат 5, но может быть и меньше

+(7) я к тому возможно есть лучший алгоритм

(8)нет нету.

Вот пойми этих ТП. Устраивают какие-то конкурсы среди десятка мажоров (принцы живут за счет папиного бабла), при этом не могут определиться с максимальным результатом своих же конкурсов. Пытаются гадать вслепую.

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

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

wiki:Задача_о_разборчивой_невесте

Последнему она скажет ДА даже с 0. Остается отобрать из 9. Тут последнего с 0 брать не нужно, ибо в последнем хуже уже не будет, значит 9-го можно взять если хотябы 1. и так далее. Итого:
первого возмет если 9, 2-8, 3-7,4-6,5-5,6-4,7-3,8-2,9-1,10-0. Может быть так?

(0) а теперь объясняй почему так.

стратегия будет заключаться в отклонении всех первых n/e (где e = 2,781… — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих.[2] При увеличении n, вероятность выбора наилучшего претендента стремится к 1/e, то есть примерно к 37%.

википедисты

(15) А по ссылкам дальше слабо пройти:
http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf
http://math.ru/media/lecture/3
или даже так:
http://en.wikipedia.org/wiki/Secretary_problem

+(15) Вообще так:
Она должна пропустить
приблизительно 34,7% претендентов, не давая согласия на брак, из следующих приблизительно 32% (вплоть до 66,7% всех претендентов) давать согласие на брак только тому, кто лучше всех предыдущих, а из оставшихся 33,3% претендентов соглашаться и на второго по качеству среди уже прошедших. При этом вероятность удачного выбора (опять-таки при большом
n ,т.е.при n??) оказывается равной 2*x0?x0^2, что приблизительно равно 0,574. Таким образом, в этом случае шансы принцессы на удачный выбор (при оптимальной стратегии) больше 50%.

Рассмотрим мат ожидание при M(n) при n принцах
n=1 тут и выбирать нечего M(1)=5
n=2 вероятность первого быть больше M(1) равна 5/11, в этом случае средний балл (6+10)/2 = 8, иначе ждем второго:
M(2)=5/11*8+6/11*5=6.36....

(18) там немного другая задача, тут точно известно, что если получил 10 - то он лучший

алгоритм:

   
   МинБалл = 0;
   МаксБалл = 10;
   ЧислоПретендентов = 10;
   Массив = Новый Массив(ЧислоПретендентов+1);
   Массив[1] = (МаксБалл+МинБалл)/2;
   Для й=2 По ЧислоПретендентов Цикл
       ЦелЧасть = Цел(Массив[й-1]);
       СредЛучшБалл = (ЦелЧасть+1+МаксБалл)/2;
       ХудшВер = (ЦелЧасть-МинБалл+1)/(МаксБалл-МинБалл+1);
       ЛучшВер = 1-ХудшВер;
       Массив[й] = ХудшВер*Массив[й-1]+ЛучшВер*СредЛучшБалл;
   КонецЦикла;
   
   Для й=1 По ЧислоПретендентов Цикл
       Сообщить(""+й+" "+?(й=ЧислоПретендентов,"*",Цел(Массив[ЧислоПретендентов-й])+1));        
   КонецЦикла;
   


результат:

1 9
2 9
3 9
4 9
5 9
6 8
7 8
8 7
9 6
10 *

(0)Надо было задачу сформулировать как "Работодатель ищет 1С-ника" и предлагает пройти тест на профа :)

(22) это к PR

(0) Надо определить "порог терпимости". Пусть он будет T.

КолПринцев = ПринцыНаЕГЭ.Количество()
Для сч = 1 По КолПринцев  Цикл
   Принц = ПринцыНаЕГЭ[сч ];
   Если ЕГЭ(Принц) >= Т Тогда
       СрочноЗамужДура(Принцесса);
   КонецЕсли;
   Если и = КолПринцев Тогда
       СрочноЗамужДура(Принцесса);
   КонецЕсли;
КонецЕсли

про невесту задача - чушь :)
По крайней мере, в изложении вики.
я не знаю, что там обсуждают авторы в книге (видимо, он обладают дополнительной инфо, не указанной в вики), но если задача стоит "Цель: выбрать лучшего претендента." при условии "О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих" - то однозначно надо перебирать всех, ЧТОБЫ УЗНАТЬ УСЛОВИЯ, ЛУЧШЕ ОН ИЛИ ХУЖЕ.
А пока не переберешь - не узнаешь.
Все.
Задача решена :)

(6)>>и когда будет принц с 10-ю баллами. она грит Да
А если в данной задаче еще и условие ограничения "сверху" количества баллов (верхняя планка известна заранее), то однозначно - как первый с 10-ю баллами - то "согласна".
Но перебирать надо ВСЕХ.
Никакая теория вероятности здесь не работает:
с 10 может оказаться - 1-ый, или вообще может не быть ни одного с 10.
И тогда надо искать с 9, 8, 7.... а это - однозначно всех перебирать.
И то - последний окажется с 1, а предыдущие уже - тю-тю, уплыли в свои королевства :)
Так что задача не имеет НИКАКОГО решения в приложении к "невесте, женихам и выбору".
Вот к вещам, которые подчиняются теории вероятности - пожалуйста.
А женихи и их интеллект - нет.
Не верите?
Посмотрите на 1с-ников :D

нудная задача на вероятность.. хоть и динамическая
если 1 прынц - средняя егэ у него 5
если 2е - то у 1го как есть, у 2го средняя 5 -> берем только >5
итого средняя 5*6/11+8*5/11=70/11
если 3е - берем только >70/11 (>6)
итого средняя 8,5*4/11+70/11*7/11=(374+490)/121=864/121
если 4ро - берем только >864/121 (>7)
...
в общем что-то похожее на (21)

(25) нет, ты просто читаешь невнимательно

Если у каждого принца средний балл 5 баллов (равновероятно любое значение), а события не связаны, то у любого количества принцев будет средний балл 5.

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

Если для каждого принца все баллы (0..10) равновероятны, то вероятность получения 10 баллов будет 1/11.
Вероятность найти 10 баллов среди двух принцев будет 1/11+(10/11)*(1/11) и так далее.
Соответственно, можно оценить вероятность того, что будет кандидат с баллом равным или выше заданного, потом его и искать среди всех.

(29)>>что у всех принцев будет ноль баллов.
Вот именно!
Но задача-то стоит однозначно - ВЫБРАТЬ из тех, кто есть, лучшего!
А такие задачи к вероятностям не имеют никакого отношения.
(28)>>ты просто читаешь невнимательно
Задача с однозначным ответом не решается подсчетом вероятностей.

"- Принцесса, вы ждали принца на белом коне? так вот он я!
-- коня я вижу, а где же принц?"
©

решения такие решения))
http://img2.joyreactor.cc/pics/post/42-пасхалка-аниме-465602.jpeg

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

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

(0) все зависит от риска, считаю что в данной задаче все что больше 5 баллов надо хватать.

(34) Тогда есть вероятность (примерно равная (1/2)^10), что принцесса вообще "на бобах" останется.

(35) да уж, ещё одной принцессе не повезло )

(6) По теории вероятности есть вероятность, что у всех будет по 1-5 баллов, и только у последнего будет 10.

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

А в данном случае - одна попытка, и какова бы вероятность не была, мат.теория может подложить свинью.
А раз так, то надо выбирать самого красивого. Правда, выбор по красоте, это если из девушек, ну тогда - самого сильного и очаровательного, типа того. А баллы - ну главное, чтобы выше 2 было.

Эх, утро еще, врядли кто-то в ближайший час что-нибудь напишет.