Помогите с поиском решения

[jangle]

Есть такая задачка. Допустим на складе лежит 100000 коробок. В одной из них, лежит ключ. В какой именно неизвестно. Все коробки пронумерованы от 1 до 100000. Задача: найти ключ наиболее быстрым способом. Есть два варианта:

1. Тупо открывать подряд, все коробки с 1 по 100000.
2. Открывать случайную коробку, разумеется игнорируя уже открытые.

Какой способ предпочтительнее? Если ключ лежит скажем в 200 коробке, то разумеется первый способ.
А если в 95941-ой? То наверное второй, т.к. есть вероятность, что мы ее откроем быстрее, чем при простом переборе. Проблема, что заранее неизвестно в какой коробке лежит ключ.
ИМХО оба способа равноценны, только я не могу придумать математического обоснования для этого.
А вы как думаете?

[Debugger]

Конечно. Если ключ положен случайным образом, то оба равноценны.

[MIT]

3) Разбить на секции по 1000 коробок и проверять по очереди коробки каждой секции, т.е. при первом проходе это будет:
0
1000
2000
3000
...
99000
при втором:
1
1001
2001
...
99001

[Debugger]

MIT, коробка будет 99999й .
Тут все способы перебора работаею одинаково.
Могу предложить еще один метод. Проверять первый, последний, второй, предпоследний, третий и т.д. т.е. сначала следующий с начала, потом предыдущий с конца.

[MIT]

коробка будет 99999й

возможно

Тут все способы перебора работаею одинаково.

Нет, у способа с распределенным просчетом несколько больше шансов.

[SLIM]

Советую попробовать метод "загони тигра"
Количество ящиков разбивается по возможности равные части. Эти две части разбиваются еще на две каждая, потом еще.
Пробегать эти разбитые кусочки можно в произвольном случайном порядке. Каждый раз, после прочесывания квадрата у тебя будет исключаться большой кусок, а ресурсов на поиск уйдет намного меньше.

[Хакер]

Способы равноценны.
Математически это обосновывается тем, что вероятность угадывания на каждой итерации соответственно одинаковая, что там, что там.

Первый быстрее, т.к. не надо вести учёт уже выпавших случайных индексов.

[jangle]

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

[Alec]

Получается колоколобразное распределение.

Не факт. В середину так-же не будет ложить.
С другой стороны - может положить и по краю и в центре - предполагая, что ищущие будут использовать именно такое распределение вероятности.

[jangle]

Не факт. В середину так-же не будет ложить.
С другой стороны - может положить и по краю и в центре - предполагая, что ищущие будут использовать именно такое распределение вероятности.

Допустим, надо придумать числовой пароль в диапазоне от 1 до 10000. Я бы наверное не стал, выбирать числа по краям диапазона. А выбрал, что-нибудь типа 6793

[iGrok]

Допустим

И вот одним этим словом все теории про психологию обламываются.

Действительно, при любом способе кроме "влоб и по очереди" ты просто будешь тратить дополнительное процессорное время на учёт обработанных коробок.

[jangle]

Действительно, при любом способе кроме "влоб и по очереди" ты просто будешь тратить дополнительное процессорное время на учёт обработанных коробок.

Еще надо учитывать, что коробка "открывается" не мгновенно. Допуститм идет криптографическая атака, брутфорс RAR - архива. Проверка даже одного пароля - занимает очень много процессорного времени, а учет обработанных паролей - ничтожное. Здесь (как мне кажется) реально может помочь только одно - оптимизация полного перебора, путем сужения пространства решений, с отбрасыванием предположительно "плохих" паролей типа 11111, AAAAA, 33333. Такие пароли, должны быть проверены в самую последнюю очередь. Это конечно при условии, что пароль придумывает человек, а не машина.

[Williams]

Если речь идет о стандартном кодовом замке с 3-мя цифрами на чемодане, большинство ставит что-то ближе к 999, т.к. ошибочно полагает что так безопаснее

[jangle]

Если речь идет о стандартном кодовом замке с 3-мя цифрами на чемодане, большинство ставит что-то ближе к 999, т.к. ошибочно полагает что так безопаснее

Помню я такие чемоданы, вскрываются полным перебором за час

[iGrok]

Если речь идет о стандартном кодовом замке с 3-мя цифрами на чемодане, большинство ставит что-то ближе к 999, т.к. ошибочно полагает что так безопаснее

Помню я такие чемоданы, вскрываются полным перебором за час

Вскрываются они за пять минут вращением колец с небольшим усилием. Косяк конструкции замка. =)

[Amed]

jangle, предложи форумчанам опрос.

[quote]Перед Вами стоят 100 ящиков, пронумерованных от 1 до 100. У Вас есть ключ и Вам нужно его спрятать в один из ящиков так, чтобы его искали как можно дольше. Какой ящик Вы выберете?[quote]

Заодно узнаем "психологический" вариант распределения ключей по ящикам

[1Steps]

Как вариант, если коробки пустые.
Делишь пополам, проверяешь какая половина больше весит, отбрасываешь не нужную и т.д.

[1Steps]

Эту задачу задают здесь(в Америке) начинающим программистам при устройстве на работу.

Условие.
У Вас есть 6 шаров.
Один шар весит больше, чем остальные.

Задача.
Найти тяжёлый шар в 2 взвешивания.

Решение.
Действие первое.
Делим на 2.
Взвешиваем обе части.
Меньшую выбрасываем.

Действие второе.
Оставшихся три шара делим на 2 с отатком в один шар.
Взвешиваем любых два шара(из трёх).
Если вес равен, значит оставшийся шар тяжелее.

Смысл ты понял.

[jangle]

jangle, предложи форумчанам опрос.

Перед Вами стоят 100 ящиков, пронумерованных от 1 до 100. У Вас есть ключ и Вам нужно его спрятать в один из ящиков так, чтобы его искали как можно дольше. Какой ящик Вы выберете?

Заодно узнаем "психологический" вариант распределения ключей по ящикам

У меня есть база паролей (несколько сотен штук) придуманных пользователями одной нашей системы. Вот по ним и изучаю психологию юзеров, одно могу сказать наверняка - случайных паролей там нет. Все в той или иной степени осмысленные. Много цифровых, номера автобусов например, телефоны, модели машин, районы Москвы, улицы и т.д. Строчек типа @3rt!$Dh3L - нет вообще

[jangle]

Как вариант, если коробки пустые.
Делишь пополам, проверяешь какая половина больше весит, отбрасываешь не нужную и т.д.

В моем случае, речь идет о поиске и брутфорсе паролей, думаю это уже понятно ))

[Zenitchik]

А я всегда генерю рандомный пароль, посредством программы собственной разработки.