Задача разборчивой невесты

[Magok]

Имеется ли у кого исходник(на бэйсике или дэлфи или си) для решения данной задачи или информации о том как её сделать?

В некотором царстве, в некотором государстве пришло вре­мя принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух пре­тендентов принцесса, познакомившись с ними, может сказать, ка­кой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гор­дые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?

[Oxygen]

А стандартный алгоритм сортировки пузырьком (вернее его первый пробег) не прокатит? По идее после первого цикла самый лучший будет выбран....

[alibek]

Тут сортировка не подойдет, насколько я понял.
Помоему самого лучшего со 100% вероятностью выбрать вообще невозможно. Это случиться только в том случае, если лучший претендент будет проверяться последним, а вероятность этого -- 0.1%.
Ну а чтобы выбрать не самого лучшего, а по возможности лучшего, можно взять первых 500 претендентов, определить по ним "средний балл" и из оставшихся 500 претендентов выбрать первого, который будет лучше усредненного.

[jangle]

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

А если у оставишихся 500 баллы будут ниже среднего? Задача не будет решена

[jangle]

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

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

Код: Выделить всё

Если новый жених лучше всех ранее просмотренных, то выбираю его, и плевать на всех остальных

Определение момента, когда принцесса должна включить это условие, скорее всего и является решением задачи

[Денис]

Magok
Смотри на официальном сайте

[Magok]

Спасибо всем за ответы.

Ну вот что я на теории понял благодаря объяснению alibek.

Допустим царевне вначале необходимо пройти первых P (допустим p=10) принцев и найти из нах самого максимального по критериям - K.
А затем из следующей десятки искать первого кондидата у которого Кследующей_десятки>Кпервой_Десятки. Если не найден то смотреть следующую "десятку" и т.д. Но вот тут получается как в посту jangle.

Еслиб P=0 то задача принцессы выскочить за муж за первого принца (вероятность = 100%).
Если P=1000 то вероятность 0% и она не выйдет за муж.