Задача Золушки

[Аватар]

задача не про золошку, а про лоторею.

Угу, тоже того же мнения. Максимально быстрой стратегии не существует. Конверт выдергивать случайным образом - не максимально быстро, но зато и не максимально медленно. И будет максимально средне (1/10) при неограниченном количестве испытаний

[Niro]

Сообщение от crazy horse

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

спсб, разумно.

pu4koff
не, номера конвертов абсолютно случайны

f.hump

почему? разве перетасовка не может иметь обратный эффект?

Ну предположим, что нужные 10 конвертов находятся внизу пачки, а я начну перебирать их сверху по одному, тогда для того чтобы найти хотя бы один нужный конверт, нужно будет просмотреть 90 "не правильных"!!!
Протасовав эту кучу, я их "равномерно" раскидаю по куче и буду уповав на теорвер

задача не про золошку, а про лоторею.

ну золушке, тоже надо было рассортировать кучу пшено+гречка
никаких лотерей, задача вполне практична, конверты реальны
(в них логины/пароли будущих клиентов от системы, 10-ые числа - идентификаторы паролей; конверты (физики+юрики) были случайно "слиты" манагером)

[type_Oleg]

Сообщение от Niro

...
Ну предположим, что нужные 10 конвертов находятся внизу пачки, а я начну перебирать их сверху по одному, тогда для того чтобы найти хотя бы один нужный конверт, нужно будет просмотреть 90 "не правильных"!!!
Протасовав эту кучу, я их "равномерно" раскидаю по куче и буду уповав на теорвер ..

Вот с какой вероятностью нужные конверты находятся в конце, с такой же вероятностью они окажутся в конце после перетасовки.

Так что вероятность испортить хорошее расположение равна вероятности того, что плохое было в начале.

Поэтому тасовать имеет смысл, если есть основания полагать, что в начале скорее плохо, чем хорошо.
Например, свежекупленную колоду карт тасуют, потому что есть основания полагать, что на фабрике их расположили по порядку, по мастям и по весам.
А у вас какие основания ?

[Niro]

А у вас какие основания ?

что когда менеджер "сливала" пачки с правильными + неправильными конвертами,
она их не тасовала, и тогда они (нужные) лежать кучкой, в какой-то части большой кучи

[f.hump]

никаких лотерей, задача вполне практична, конверты реальны
(в них логины/пароли будущих клиентов от системы, 10-ые числа - идентификаторы паролей; конверты (физики+юрики) были случайно "слиты" манагером)

если все так реально, может изначально формировать список упорядлченный по id. добавление/удаление может оказаться медленным, зато поиск будет быстрым.

[pu4koff]

Я бы манагеров обязал сортировать, чтобы бездумно в кучу всё не сливали