Эрудит выбирает себе машину. В салоне ему на выбор предлагается 1000 автомобилей. Консультант по очереди предлагает на выбор одну из 1000 машин. Про две любые увиденные машины Эрудит может сказать какая из них лучше. Все автомобили в салоне образуют упорядоченное множество (Если Мерседес лучше БМВ, а БМВ лучше Ауди, то Мерседес лучше Ауди).
Консультант показывает Эрудиту по очереди каждую из 1000 машин в случайном порядке. Эрудит все сравнивает и, например, про 15-ю машину может сказать какая она пятая по качеству (лучше 10-и и хуже 4-ех предыдущих).
На каждом просмотре автомобиля Эрудит должен сообщить консультанту: покупает он эту машину или нет. Если покупает, то показ автомобилей прекращается и Эрудит едет домой на новеньком авто. Если Эрудита машина не устраивает, то процесс показа автомобилей продолжается. Автомобили можно смотреть только по одному разу, т.е. если Эрудит решил посмотреть следующую машину, то предыдущие он уже купить не сможет. Если показ машин закончился, а Эрудит так и не решился купить себе автомобиль, то он проиграл и в ближайшее время будет ездить только на такси и общественном транспорте, что Эрудита не устраивает.
Естественно, что цель Эрудита купить самый лучший автомобиль (даже второй по качеству его не устроит).
Как стратегии Эрудиту нужно придерживаться при выборе автомобиля, чтобы с наибольшей вероятностью купить наилучший по качеству?
Может быть, ему следует просмотреть 500 машин, а из последующих купить ту которая займет 1 место в предшествующем ряду, если и как только такая попадется. офтоп: на практике, конечно, лучшую машину консультант в таких условиях, скорее всего, покажет последней).
Может быть, ему следует просмотреть 500 машин, а из последующих купить ту которая займет 1 место в предшествующем ряду, если и как только такая попадется.
Не оптимально :)
ЦитатаVita ()
Если при каждом сравнении наилучшую запоминать, то и место остальных не важно уже. И после полного перебора эту наилучшую купить. Так можно?
Нет, машину можно посмотреть только один раз, если при этом просмотре консультант получил отказ, то эту машину уже Эрудит купить не сможет.
Может быть, ему следует просмотреть n машин, а из последующих купить ту которая займет 1 место в предшествующем ряду, если и как только такая попадется.
n пожалуй меньше 500. Сколько именно буду думать, если сам алгоритм верный.
Может быть, ему следует просмотреть n машин, а из последующих купить ту которая займет 1 место в предшествующем ряду, если и как только такая попадется. n пожалуй меньше 500. Сколько именно буду думать, если сам алгоритм верный.
Математически решить не могу,но исходя из одного любопытного правила, предположу: эрудиту следует просмотреть 199 машин,ранжируя их,и как только после этого ему попадется лучше,брать её
Добавлено (03.05.2017, 20:49) --------------------------------------------- Хотя..если брать лучшую после 400, то на глазок имеем вероятность около 60. В то время, как после 500, она =50, а после 200 вроде меньше 40. Да, пожалуй, меняю ответ. Лучшая после 400й
Сообщение отредактировал никник - Чт, 04.05.17, 20:26
Vita, представьте, что каждой машине cоответствует цена от 1 до 1000р, 2 машин с одинаковой ценой нет. Мы эту цену не знаем, но отличить более дорогую машину от более дешевой можем всегда, хоть и не можем сказать насколько она дороже. Если бы перед нами стояла лишь задача выбрать лучшую машину, я бы скорее всего использовал тактику:
ЦитатаVita ()
сравниваются
ЦитатаVita ()
лучшая из первой пары и 3
В стоящей перед нами задаче, мне кажется не лишенным резона ранжировать весь ряд уже показанных машин, чтобы видеть динамику формирования ряда. Однако, я все же отказался от такой тактики в пользу более простой.
ЦитатаVita ()
Мерседес лучше БМВ, Ауди лучше БМВ, лучше Мерседес или Ауди?
что то лучше Мерседес или Ауди, Эрудит может определить что именно, увидев эти 2 машины.
Может быть, ему следует просмотреть 500 машин, а из последующих купить ту которая займет 1 место в предшествующем ряду, если и как только такая попадется.
или лучший или никакой 
