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

[Niro]

Есть следующая практическая задача:

Имеется много конвертов, на каждом конверте 10-значное случайное число.
Нужно разделить конверты на две части:
первая часть ~ 1/10 от всей кучи;
вторая часть ~ 9/10 от всей кучи;

Признак разделения 10-значное число, которые забиты в программе (проверять только вручную).

Вполне возможно, что 1/10 нужная часть - идет подряд среди общей пачки, а может и нет.

Как максимально быстро найти нужный (хотя бы один конверт)???

Пока только одна идея: тщательно перетасовать конверты и проверять подряд, надеясь на теорию вероятности
(вероятность вытащить нужный конверт как раз 1/10, а перетасовав мы исключим случай,
что все нужные конверты находятся, например в конце пачки)

[pu4koff]

Я ничего не понял. Задача выглядит как: на глазок поделить кучу конвертов на две кучи. Маленькую, и ту, что в 9 раз больше. Кто такой искомый конверт, зачем делить на эти кучи, чего за числа в программе - ничего не понятно.

[Niro]

Есть куча конвертов (пусть будет 100), отличаются друг от друга случайными числами, которые на них написаны.
"Правильных" конвертов - пусть будет 10 штук.
"Правильность" можно проверить вбив номер конверта в программу - она скажет нужный это конверт или нет.

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

[type_Oleg]

Непонятен вид распределения и тип испытаний.
Среди этих многих конвертов достоверно имеется какое-то количество нужных, или могут быть, а могут не быть?

То есть может быть два типа задачи.
1) Имеем колоду 36 карт, среди них обязательно есть 4 туза.
2) Берем 100 колод по 36 карт, перемешиваем, выбираем из них 36 карт. Тогда среди них - не обязательно будут 4 туза.

Кстати, в обоих случаях наверное нет никакой особой стратегии поиска тузов.
Разве что, если в случае 1) проверили 32 карты, и в них ни одного туза, то оставшиеся 4 можно не проверять - там точно 4 туза.
А во втором случае надо проверять до конца.

[Niro]

Да, обязательно имеется некоторое (правда примерное) количество нужных конвертов.

[crazy horse]

(вероятность вытащить нужный конверт как раз 1/10, а перетасовав мы исключим случай,
что все нужные конверты находятся, например в конце пачки)

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

[pu4koff]

Можно пробовать искать зависимость в искомых числах. Допустим окажется, что нужны конверты с номером 123ххххххх или только начинающиеся на 1,5 или 9. Три цифры уж любой дурак запомнит. Тогда человек сможет предварительно отсеять откровенно неподходящие конверты, а оставшиеся уже пробивать по программе. Остаётся вопрос в удобстве дополнительного перелопачивания конвертов и пользе такой фильтрации. А то может наборы данных такие, что этим только три конверта отсеется, а работы лишней много будет проделано.
Если есть набор чисел со всех 100 конвертов, то тут можно позагоняться на предмет формирования оптимальной стратегии. Можно будет командовать оператору, что мол найди-ка ты дружок для начала конверты, начинающиеся на 8, а в оставшихся уже копошись внимательнее

[f.hump]

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

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

(вероятность вытащить нужный конверт как раз 1/10, а перетасовав мы исключим случай,
что все нужные конверты находятся, например в конце пачки)

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

[type_Oleg]

Я не понял, зачем перетасовывать.
Если заранее неизвестен порядок, то можно считать их уже перетасованными.
Или известно, что какое-то начальное неудачное расположение более вероятно ?
То есть более вероятно, что нужные конверты в самом конце ?

[Человек_Борща]

Как вариант, по очереди брать письма с обеих концов стопки, таким образом время перебора сокращается вдвое. Если ещё от середины кучи поставить по курсору и вести в концам кучи, то время сокращается в 4 раза а вероятность найти нужное письмо многократно увеличивается. Курсоры и в тех блоках можно ставить, увеличите перебор ещё в 2 раза.