Задачка по поиску...

[shatver]

Есть массив из 256 значений, из которых два достоверно удовлетворяют некому условию... Узнать какие именно можно лишь подставив данные значения в это условие... требуется найти любое одно из этих двух значений... есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности
(80-90 %)... Или хотя бы убедиться что это невозможно..

Другой дополнительной инфы нету, типа отсортированности для бинарного поиска и т.д.

[Agregat]

Чтоб я полностью осознал задачу переспрошу:
известно, что только 2 числа равны друг другу, но не извесно какие? нужно найти это число?

[Aram Hambardzumyan]

есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности
(80-90 %)...
боюсь, что нет. подумаю на досуге над доказательством

[shatver]

Чтоб я полностью осознал задачу переспрошу:
известно, что только 2 числа равны друг другу, но не извесно какие? нужно найти это число?
Нет числа не равны друг другу..просто они удовлетворяют некому условию..проверить же это можно непосредственно подставив число в ..ну скажем в некую формулу... Не хотелось бы делать это 256 раз.. раз чисел два то хотелось бы сократить вдвое кол-во проверек...

[Aram Hambardzumyan]

кстати, а что подразумевается под нахождением с точносьтю до 80-90%?

[Agregat]

Я тоже склонен думать, что не выйдет. Разве, что можешь попробовать искать с двух сторон одновременно, что при равномерном распределение чисел по массиву может уменьшить кол проверок типа:

for (int i = 0; i < 128; ++i)
{
if (uslovie(p[i])) return p[i];
else if (uslovie(p[255 - i])) return p[255 - i];
}

[Aram Hambardzumyan]

интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.

[greka]

Я тоже склонен думать, что не выйдет. Разве, что можешь попробовать искать с двух сторон одновременно, что при равномерном распределение чисел по массиву может уменьшить кол проверок типа:

for (int i = 0; i < 128; ++i)
{
if (uslovie(p[i])) return p[i];
else if (uslovie(p[255 - i])) return p[255 - i];
}

при равномерном распределении не имеет значения, с какого конца ведется поиск.
Я к тому, что в данном случае "с двух концов" не увеличивает скорость поиска - всиравно в сумме делаешь 256 проверок, а не 128.

чисто технически наличие условия "if..else" в цикле сильно замедляет скорость выполнения цикла.

[greka]

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

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

[shatver]

интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.
75% уже неплохой результат... а как получается такая цифра?

[Aram Hambardzumyan]

75% уже неплохой результат... а как получается такая цифра?
если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%. вероятность того, что в данной половине окажутся оба элемента, равна 25%. если в качестве упоминаемой половины рассмотреть невыбранные 128 элементов, то получается, что мы 'промахиваемся' с вероятностью 25%, т. е. вроятность нахождения хотя бы одного элемента - 75%

[shatver]

И правда же... совсем мозги заржавели... фактически нужно каждый раз случайным образом выбирать 128 элементов... а если выбрать 192 то и за все 90% переходит... но 192 это много...

Вообщем все ясно.. Всем спасибо..

[nm]

если случайным образом отобрать половину элементов


считай, что _случайным_ образом я выбрались первые 128 элелемтов ;)))) почтому слово случайный -- выкидываем ;))))

так что я бы предложил другой алгоритм - просто идти с начала и проверять. если попал на ответ - хорошо, выходим из цикла, если нет -идем дальше :)
в среднем у тебя будет 64 итерации на каждый поиск.
вероятность того, что ты сделаешь 253 проверки -1/(253*254), если я все правильно понимаю ;))))

если у тебя есть возможность оценивать _хорошесть_(ты имешь какую-то оценочную функцию) ответа - то стоит запоминать позицию и значение этой функции. если ты прошел первые N элементов и не нашел искомого значения -- то тогда просто прерываешь поиск и возвращаешь _хороший_ результат. в принципе это актуально для задач реального времени, когда важно найти результат в заданый промежуток времени и приемлемо, если он будет не совсем точным.

[shatver]

а 64 итерации откуда?
а слово случайный выкидывать не надо.. потому как условие все время меняется..а значит и пары цифр удовлетворяюшие ему...
Ведь то что условие неизвестно, не означает что оно не подчинено определенной логике...и вполне может сказаться что постоянный выбор первых 128 цифр и есть худший вариант... А выбирая каждый раз случайным образом можно эту логику перебить и иметь в среднем эти 75% ...

[nm]

а 64 итерации откуда?
а слово случайный выкидывать не надо.. потому как условие все время меняется..а значит и пары цифр удовлетворяюшие ему...
Ведь то что условие неизвестно, не означает что оно не подчинено определенной логике...и вполне может сказаться что постоянный выбор первых 128 цифр и есть худший вариант... А выбирая каждый раз случайным образом можно эту логику перебить и иметь в среднем эти 75% ...

так. условие насколько сложное ?? :)))) я к тому, что генерация _случайного_ числа и выборка _неповторяющегося_ _случайного_ индекса -- задача довольно трудоемкая :))))

64 итерации -- если у тебя ответы распределены равномерно по всем 256 индексам, тогда получается след. вариант:
вероятность того, что мы нашли ответ в N-ной итерации -

1/256 /* первое число может быть в любой из N позиций */ x
(255-N)/255 /* второе число должно быть в позиции больше , чем N */ x
2 /* у нас нет _первого_ и _второго_ числа, у нас есть просто число, которое надо найти, т.е. задача симметрична */

вот .... и при помощи простой арифметики получаем, что сумма таких вот вероятностей для N=0 по N=64 получается около 0.45 .... тааак ;) что-то в формуле не так, но вобщем результат имхо именно такой должен быть - за 64 итерации ты с вероятностью 1/2 находишь искомый ответ.

ндя. я уже даже как-то засомневалсь, в том что написал ;)))) но все-таки мне кажется, именно так, а не иначе ;)

[Agregat]

СЛучайный индексы получить как раз очень просто - хранишь список свободных позиций и каждый раз генерируешь случайное число в промежутке 0 - 255, 254, 253... 128 (например), и забираешь это число из индекса.

[who]

Дональд Кнут - "Сортировка и поиск".

[greka]

интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.
интуиция тебя обманывает. Выделю время - укажу, в чем именно.

[nm]

интуиция тебя обманывает. Выделю время - укажу, в чем именно.

аргументы - в студи, интерестно все-таки ....
а ты - выделю время :)

[shatver]

действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...

[greka]

действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...
для начала разговора я бы попросил привести эти самые "азы" на свет божий.

[shatver]

Greka ты издеваешься или где?
Арам же вроде ясно написал:
"если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%. вероятность того, что в данной половине окажутся оба элемента, равна 25%. если в качестве упоминаемой половины рассмотреть невыбранные 128 элементов, то получается, что мы 'промахиваемся' с вероятностью 25%, т. е. вроятность нахождения хотя бы одного элемента - 75%
"

[Aram Hambardzumyan]

Greka ты издеваешься или где?
Арам же вроде ясно написал:....
если я правильно понял, грека оспаривает 'легитимность' моей случайной выборки

[nm]

для начала разговора я бы попросил привести эти самые "азы" на свет божий.


Гарик, еще раз -- выкладки в студию :) даже если они не правильные ....


п.с. к делу не относится, но вспомнилось. ...

академик - это человек, который может объяснить 5 летнему ребенку за что он получил это звание...


так что, Гарик, постарайся уж ... :)

[greka]

>интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.

Итак.

"можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. "

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

Вероятность нахождения элемента не увеличивается, если исходное множество делить - ибо она должна быть ПОМНОЖЕНА на вероятность того, что СРЕДИ ОТБРАСЫВАЕМЫХ ЭЛЕМЕНТОВ НЕТ ТЕХ, КОТОРЫЕ НАМ НУЖНЫ.

а вы - делите пополам, говорите - веорятность удваивается, потом еще делите пополам - еще раз удвоилась вероятность - класс, теория вероятностей отдыхает :D

[Aram Hambardzumyan]

>интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.

Итак.

"можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. "

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

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

Вероятность нахождения элемента не увеличивается, если исходное множество делить - ибо она должна быть ПОМНОЖЕНА на вероятность того, что СРЕДИ ОТБРАСЫВАЕМЫХ ЭЛЕМЕНТОВ НЕТ ТЕХ, КОТОРЫЕ НАМ НУЖНЫ.
это всё я учитываю.

а вы - делите пополам, говорите - веорятность удваивается, потом еще делите пополам - еще раз удвоилась вероятность
я такого не говорил, и из моих вылкадок это не следует. иначе на выборке 128 элементов я бы получил 100%

а какой результат получаешь ты для 128 шагов?

[shatver]

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

У меня впечатление что либо ты не внимательно читаешь, либо стоит проверить свои собственные знания азов.. А то менторский тон так и хлышет за край...


Повторим еще раз

"если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%."
50 % означает 1/2 ...

Далее
" вероятность того, что в данной половине окажутся оба элемента, равна 25%."

25% это 1/4, что есть умножение двух вероятностей (1/2) * (1/2)... то самое умножение, о котором мы по вашему мнению "забываем"..

[greka]

2 shatver: "Greka ты издеваешься или где?", "менторский тон" - блин, пописай успокойся, что ли?

[shatver]

"блин, пописай успокойся, что ли?"...
А что... помогает? тебе виднее наверное...

по сушеству давай....

[greka]

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

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

AH, ты предлагаешь вдвое сократить множество возможных значений, и утверждаешь, что вероятность нахождения элемента увеличится. Абсолютная вероятность действительно "увеличивается". И с вероятностью 100% ты найдешь элементы, если "поделишь" множество еще 128 раз.

Если учтем относительную вероятность - т.е. вер-сть того, что за предыдущие 128 шагов ты не найдешь, и найдешь на 129-м:
1/2 * 2/128.

Т.е. меньше, чем 50%.

Комментарии?

[greka]

лучшего способа поиска я не вижу. Агрегат дал решение, которое делает 128 сравнений, забыв о том, что нужно найти 2 элемента, а не 1 ("return").

как можно "делить" случайно распределенные элементы по позициям ?
"первые 128" == "последние 128" == "элементы на четных позициях" == "элементы на позициях хода лошадью".

Поиск - линейный, 256 проходов - вот мое хамбл апиньон.

[Aram Hambardzumyan]

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

Если учтем относительную вероятность - т.е. вер-сть того, что за предыдущие 128 шагов ты не найдешь, и найдешь на 129-м:
1/2 * 2/128.

Т.е. меньше, чем 50%.
как я уже показал, вероятность ненахождения ни одного из двух элементов среди первых случайных 128 элементов составит 25%, что действительно меньше 50%. и уж еще меньше вероятность того, что это случится на 129-м шаге. но при чем тут это? по-моему, мы с тобой по разному воспринимаем задание и вычисляем разные цели

[greka]

суммирую:
алгоритма и не существует, кроме как перебирать по штучке.
а всякие повышения вероятностей - это проделки Фикса.

[who]

суммирую:
алгоритма и не существует, кроме как перебирать по штучке.
а всякие повышения вероятностей - это проделки Фикса.

полностью согласен с грекой! :agree:

еще раз отсылаю всех любителей игр с вероятностью нахождения элементов при обычном последовательном поиске к Д.Кнуту ;)

[greka]

прямо автомат-расфасовщик..;)

[Aram Hambardzumyan]

а всякие повышения вероятностей - это проделки Фикса.
о повышении вероятностей, кажется, никто кроме тебя и не говорит :) грека ака фикс? ;)

[Aram Hambardzumyan]

полностью согласен с грекой! :agree:

еще раз отсылаю всех любителей игр с вероятностью нахождения элементов при обычном последовательном поиске к Д.Кнуту ;)
если честно, я кнута не читал, а так бегло что-то найти про вероятности не удалось. если можно, в двух словах - что там, связанное с вероятностями?

[greka]

о повышении вероятностей, кажется, никто кроме тебя и не говорит :) грека ака фикс? ;)
т.е. об "улучшенном" варианте поиска для этого примера тоже никто не говорил, получается?

[Aram Hambardzumyan]

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

[shatver]

Задача была найти любой один из двух элементов , а не оба элемента ...