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

[shatver]

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

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

[Agregat]

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

[Aram Hambardzumyan]

Originally Posted by shatver

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

боюсь, что нет. подумаю на досуге над доказательством

[shatver]

Originally Posted by Agregat

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

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

[Aram Hambardzumyan]

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

[Agregat]

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

PHP Code:

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]

Originally Posted by Agregat

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

PHP Code:

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]

Originally Posted by Aram Hambardzumyan

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

75% уже неплохой результат... а как получается такая цифра?

[Aram Hambardzumyan]

Originally Posted by shatver

75% уже неплохой результат... а как получается такая цифра?

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

[shatver]

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

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

[nm]

Originally Posted by Aram Hambardzumyan

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

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

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

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

[shatver]

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

[nm]

Originally Posted by shatver

а 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 находишь искомый ответ.

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