Задача N12 (прочитанная мною лет пять назад в журнале "Компьютерра").
Представим себе жениха перед выбором наиболее богатой (красивой, доброй и т.п.) невесты из N претенденток, когда их поочередно показывают ему, а он вправе либо сделать свой выбор, либо перейти к просмотру следующей. В случае выбора просмотр прекращается, а в случае отказа представленная невеста "отбраковывается" и повторный выбор ее будет уже невозможен.
Итак, жених, зная число невест и ничего не зная о величинах их приданного, должен выбрать такую тактику выбора, чтобы с одной стороны не выбрать "первую встречную" (сделав выбор слишком рано), а с другой не пропустить самую богатую ("отбраковав" ее, понадеявшись на еще более удачный выбор).
Какая тактика будет являться наиболее оптимальной и чему в этом случае будет равна вероятность правильного выбора?
В более общем виде: дана последовательность X из N чисел. Число N считается заданным, а о самих элементах последовательности ничего не известно (закон распределения, математическое ожидание, минимальное и максимальное значение и т.п.). Поочередно выбирается один элемент за другим. Выбранные элементы могут служить в качестве информации для принятия решения.
Необходимо с наибольшей вероятностью найти максимальный (минимальный) элемент, при условии, что к уже выбранным элементам возвращаться после их просмотра нельзя.