[greka]

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

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

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

[Aram Hambardzumyan]

Originally Posted by greka

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

ничего такого я не утверждаю. увеличится относительно чего? относительно какого алгоритма? я рассматриваю только один алгоритм и не сравниваю его с чем-либо, относительно чего утверждал бы об увеличении вероятности.

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

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

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

[greka]

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

[who]

Originally Posted by greka

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

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

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

[greka]

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

[Aram Hambardzumyan]

Originally Posted by greka

а всякие повышения вероятностей - это проделки Фикса.

о повышении вероятностей, кажется, никто кроме тебя и не говорит грека ака фикс?

[Aram Hambardzumyan]

Originally Posted by who

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

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

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

[greka]

Originally Posted by Aram Hambardzumyan

о повышении вероятностей, кажется, никто кроме тебя и не говорит грека ака фикс?

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

[Aram Hambardzumyan]

Originally Posted by greka

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

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

[shatver]

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