2022-12-28 18:33:05
Итак, жила-была прекрасная принцесса, и захотела она выбрать себе достойного мужа. Разнеслась весть по окрестным королевствам, и съехалось к ней N принцев разной степени прекрасности. Мы понимаем, что прекрасность — вещь субъективная, у принцессы на этот счёт свои соображения. Но будем считать, что она всегда может однозначно сказать, какой из кандидатов лучше, без ситуаций «этот добрый, но зато этот красивый». Например, каждому она мысленно присваивает какой-то балл и потом сравнивает их друг с другом.
Отбор устроен следующим образом: принц заходит в тронный зал, они общаются, она всё про него понимает и отвечает ему «да» или «нет».
Если «да» — то отбор заканчивается, играем свадьбу, остальных кандидатов даже не смотрим.
Если «нет» — принц уезжает, вернуть его назад уже будет нельзя (потому что все принцы очень гордые), а принцесса смотрит дальше. Принцы никак не отсортированы, поэтому никто не знает, все ли молодцы попадутся в начале, или наоборот, к концу самый огонь, или в среднем всё одинаково.
Какая здесь оптимальная стратегия? Понятно, что какое-то время вроде бы надо отказываться, но когда надо соглашаться? Сколько ждать? У математики есть ответ!
Если N достаточно велико (хотя бы больше 100), тогда количество людей, которых вам надо отсмотреть, говоря им «нет», стремится к N/e (где е примерно равно 2.7). А потом надо выбрать первого, кто окажется лучше всех предыдущих. То есть примерно 37% процентов смотрим, запоминаем и отказываем, а уже потом решаем. Если N меньше 100, то процент чуть выше. Например, для 10 кандидатов отбраковать надо первые 40%.
Доказательство того, что именно эта стратегия является наилучшей, достаточно сложное, его мы здесь приводить не будем. Однако это не мешает нам пользоваться самим методом!
Завтра мы расскажем, какие у этой задачи могут быть приложения, а также о сложностях её применения к своей личной жизни. :)
Какие сложности видите вы?
876 views15:33
П
