Жениться на дочке султана
Султан предоставил простолюдину шанс жениться на одной из ста его дочерей. Простолюдина будут представлять дочерей по очереди. Когда дочь пpедставляется, пpостолюдину сообщают ее пpиданое. У пpостолюдина есть только один шанс пpинять или отвеpгнуть каждую дочь; он не может веpнуться к pанее отвеpгнутой дочеpи. Условие султана в том, что пpостолюдину позволено жениться только на дочеpи с наибольшим пpиданым. Какая наилучшая стpатегия для пpостолюдина, учитывая то, что он ничего не знает о pаспpеделении пpиданого.
Ответ
Рейтинг: : Алгоритм - пропустить 37 дочерей, при этом "приметить" лучшую из них. Потом отсматривать остальных и остановиться на первой, которая окажется лучше, чем "примеченная". Если таковой не окажется - взять сотую (а что ж еще делать в этом случае).
-372
Комментарии:
Tratarararam, 2008-06-17
я думаю лучше жениться на простолюдинкеVlad, 2008-06-26
Динамическое програмирование – сложная задача если никогда об этом не слышал HeeL, 2008-06-27
Vlad, абсолютно верно, классическая задача такого планаЕвгений, 2008-07-12
Да причем тут динамическое программирование? Это задача из мат статистики и теории вероятности. Искомое число пропускаемых девушек получается от деления их общего число на число е. Так что результат получается точным методов, а не итеративным.
И вообще глупая задача для того, чтобы ставить ее в подобном неспециализированном разделе.Андрей, 2008-07-22
а причем здесь лучшая или худшая, если надо угадать которая с большим наследством?Вадим, 2008-08-29
Помоему ответ, не совсем соответствует истине, ведь нужно найти с найибольшим приданы, а не самую красивую. Андрей прав.Алексей, 2008-09-11
Народ! Растолкуйте ответ, ато я не совсем понял.DJ_Serega, 2008-12-11
Что задача что ответ фигня (если честно).
Просто угадать надо.Ильдар, 2008-12-14
"Лучшая" в данном случае не самая красивая, а с самым большим приданным.Омен, 2009-03-25
Условие не верно изеачальноАндрей, 2009-04-18
Почему именно 37 дочерей?вася, 2009-05-25
37 именно потому, что ничего не известно от том, в каком порядке будет идти размер приданого. 37 пропускаются специально для того, чтобы прикинуть, какой максимум может быть примерно. Тогда повышается вероятность того, что при встрече реального максимума его можно угадать.
Это примерно как если бы по одному выходила вся группа, и угадать, кто в ней самый высокий строго в тот момент, когда он выходит. Если сразу на первого более-менее высокого показать - как правило будет прокол. А если сначала оценить распределение - то вероятность повышается. Но нельзя этим увлекаться, а то ведь возвращаться назад нельзя. Вот 37 из 100 - оптимально (по формулам).Romeo66rus, 2009-06-11
Меня удивляют как так люди ставят минус, когда просто абсолютно не врубаются! Они правда не верят что ли, что действительно такие задачи решаются математически? Думают что их опять обманывают?Константин aka HALYAVA, 2009-08-30
Я не спорю, что стратегия наилучшая, но не 100% - однозначноHL, 2009-09-07
Криво сформулировано условие:
"пpостолюдину позволено жениться только на дочеpи с наибольшим пpиданым" подразумевает что нужно найти максимум (строго).
т.е. при таком раскладе султану достаточно послать самое большое приданное 2-3 дочери... причем в первом десятке вложить ВСЕ имеющиеся приданные... а остальным дочерям по одному динару 
zx, 2009-10-19
Раньше не встречался с такого рода задачами и решение интересное,но остаётся вопрос насколько эта стратегия лучше(эффективнее)чем обычное угадывание?ramzes, 2009-11-01
эта задача из серии "с подвохом" решается просто.Каждой из них можно сказать да или нет. "Да"-не значит окончательный выбор, ибо возвращатся нельзя к тем кому сазал НЕТ.Стало-быть говорить всем ДА а затем выбрать самую богатую. А вообсче задача-леваяАлекс, 2009-11-10
Может я вообще не врубился, но что получается по моему ходу мыслей: Если выберешь первую, то с большим приданным может оказаться какя-нибудт, например 25-я. Если выберешь к примеру 5-ю, может оказаться, что первая была с наибольшим приданным.Спартак, 2010-03-02
Элементрано!!!
Соглашаться с жениться на каждой. Ибо сказано в задаче
"пpостолюдину позволено жениться только на дочеpи с наибольшим пpиданым". Простолюд соглашается, а султан не позволит если у этой дочери не максимальное приданное и вызывают следующую дочь в очереди.Масяня, 2010-05-01
Спартаку респект!!
а ещё можно так и сказать : ДАВАЙ СЮДА ДОЧЬ с САМЫМ БОЛЬШИМ ПРИДАНЫМ))) Bake, 2010-06-04
Pri4em tut algorytm nado chpionyt za sotnyu
иВася, 2010-06-28
я не понимаю по какой формуле получается 37, только объясните по человечески-не нужно грубить!!!!!!!!!
Полуночник, 2010-10-08
Если после 37-ми просмотренных не окажется лучше "примеченной", то и сотую он не возьмет.. Батя же сказал что позволено жениться только на той, у кого приданое больше всех..General, 2010-10-14
Классическая задача теории вероятностей имеет рейтинг -224 O_o Soprus, 2010-12-02
Ошибки в орфографии, да еще условие составлено неграмотноВА, 2010-12-15
Извините но ответ просто конченый. Если это формула - приведите формулу.
И как "приметить" с самым богатством а не самую лучшую?Кайрат, 2011-01-04
Приведите формулу из этой теории веротяности, по которой решать надо. Это всего лишь вероятность? То есть при таком варианте у нас шансов больше? ОБъясните, господа умники, а то не все тут все таки знают, что это за теория. Поэтому и будут минусыas, 2011-01-14
выбрать ту у которой сиськи большеФлоу, 2011-06-18
Кайрат, гугли "задачу о разборчивой невесте".
На википедии она даже есть Вася, 2011-12-07
не надо ставить минус если вы не понимаете задачу вася, 2011-12-07
mccme ru free-books mmmf-lectures book 25 pdfВася, 2011-12-07
mccme точка ru слеш free-books слеш mmmf-lectures слеш book точка 25 точка pdf каму интересно решения вот ссылкаШапа, 2012-03-04
Некорректно сформулированно условие задачи. Предложенная стратегия несомненно улучшает шансы простолюдина, но в итоге шансы получаются как у той блондинки - 50/50 - или жениться или нет))) Да и, строго говоря, с таким ответом задаче место в разделе Математика.
А, с точки зрения логики, единственно правильное решение предложил Спартак.Ашот, 2012-03-24
Идиотвство -1Аноним, 2012-10-21
Игра раньше была такая называлась гугол (не путать с браузером) пишешь на бумажках любые разные числа и даешь игроку их просматривать по одной и он должен выбрать самое большое из них. taviskaron, 2013-06-02
"...подумал, подумал, и женился на той, у кого сиськи больше"Саша, 2013-06-28
наберите в яндексе "Выбор наибольшего приданого" и по первой ссылке можно посмотреть математическое решение этой задачи. Сюда не могу ссылку выложить. Программа требует изменить комментарийIvan, 2013-08-05
можно решить графически - подождать, пока не получишь достаточно сведений, чтобы оценить вершину нормального распределения(колокол гаусса), а тогда выбрать более или менее приближеннуюАлександр, 2014-04-02
37 это округление (1/e)*100! Задача просто громадная по своему решению, так что описывать его не буду... Можете прогуглить, если пробывали решать задачи на комбинаторику с бесконечными наборами событий, то сумеете разобраться)Юлия, 2015-03-19
Минус, минус, минус! Противоречие уже в условии: У пpостолюдина есть только один шанс пpинять или отвеpгнуть каждую дочь; он не может веpнуться к pанее отвеpгнутой дочеpи. Условие султана в том, что пpостолюдину позволено жениться только на дочери с наибольшим пpиданым.
Ну согласился он женится на какой-то, а у нее не самое большое приданое, и все по новой?? В чем тогда смысл угадывания? Видимо у султана такая развлекуха тупая от "нечегоделать"... Гедеон, 2016-03-21
"Условие султана в том, что пpостолюдину позволено жениться только на дочеpи с наибольшим пpиданным" - из чего следует, что на других жениться нельзя. Потому, если 37-я дочь обладает самым большим приданным, или после 37-й идёт дочь с приданным больше чем у неё, но не с самым большим, то стратегия не работает. Так что задача не очень. 
