Задачка по поиску... - Page 3

shatver · Apr 19, 2004, 18:33

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

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

greka · Apr 26, 2004, 11:11

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

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

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

Aram Hambardzumyan · Apr 26, 2004, 11:25

Quote:

Originally Posted by greka

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

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

Quote:

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

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

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

greka · Apr 26, 2004, 11:59

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

who · Apr 26, 2004, 12:10

Quote:

Originally Posted by greka

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

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

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

greka · Apr 26, 2004, 12:38

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

Aram Hambardzumyan · Apr 26, 2004, 14:52

Quote:

Originally Posted by greka

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

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

грека ака фикс?

Aram Hambardzumyan · Apr 26, 2004, 14:54

Quote:

Originally Posted by who

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

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

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

greka · Apr 26, 2004, 16:24

Quote:

Originally Posted by Aram Hambardzumyan

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

грека ака фикс?

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

Aram Hambardzumyan · Apr 27, 2004, 05:11

Quote:

Originally Posted by greka

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

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

shatver · Apr 27, 2004, 06:09

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

Apr 26, 2004, 11:11	#31
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	лучшего способа поиска я не вижу. Агрегат дал решение, которое делает 128 сравнений, забыв о том, что нужно найти 2 элемента, а не 1 ("return"). как можно "делить" случайно распределенные элементы по позициям ? "первые 128" == "последние 128" == "элементы на четных позициях" == "элементы на позициях хода лошадью". Поиск - линейный, 256 проходов - вот мое хамбл апиньон. __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Apr 26, 2004, 11:59	#33
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	суммирую: алгоритма и не существует, кроме как перебирать по штучке. а всякие повышения вероятностей - это проделки Фикса. __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Apr 26, 2004, 12:38	#35
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	прямо автомат-расфасовщик.. __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
задачка на тему Самолет	mk	General	186	Dec 23, 2004 17:07
Задачка	Shirinyan	Fun	13	Oct 22, 2003 13:41
Задачка от Альберта, самого Энштейна	R0nIn	General	34	Aug 19, 2003 19:24
Еще одна задачка	Agregat	Languages, Compilers and Interpreters	15	Oct 8, 2002 19:22
Задачка	Amph	Algorithms	1	May 29, 2002 04:02

Apr 19, 2004, 18:33
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	Задачка по поиску... Есть массив из 256 значений, из которых два достоверно удовлетворяют некому условию... Узнать какие именно можно лишь подставив данные значения в это условие... требуется найти любое одно из этих двух значений... есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности (80-90 %)... Или хотя бы убедиться что это невозможно.. Другой дополнительной инфы нету, типа отсортированности для бинарного поиска и т.д.

Apr 27, 2004, 06:09	#40
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	Задача была найти любой один из двух элементов , а не оба элемента ...