Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 26.04.2004, 12:11   #31
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

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

Поиск - линейный, 256 проходов - вот мое хамбл апиньон.
Reply With Quote
Old 26.04.2004, 12:25   #32
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

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

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

Т.е. меньше, чем 50%.
как я уже показал, вероятность ненахождения ни одного из двух элементов среди первых случайных 128 элементов составит 25%, что действительно меньше 50%. и уж еще меньше вероятность того, что это случится на 129-м шаге. но при чем тут это? по-моему, мы с тобой по разному воспринимаем задание и вычисляем разные цели
Reply With Quote
Old 26.04.2004, 12:59   #33
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

суммирую:
алгоритма и не существует, кроме как перебирать по штучке.
а всякие повышения вероятностей - это проделки Фикса.
Reply With Quote
Old 26.04.2004, 13:10   #34
cares?..
 
who's Avatar
 
Join Date: 01 2004
Location: RA Army
Age: 47
Posts: 149
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Lightbulb

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

еще раз отсылаю всех любителей игр с вероятностью нахождения элементов при обычном последовательном поиске к Д.Кнуту
Reply With Quote
Old 26.04.2004, 13:38   #35
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

прямо автомат-расфасовщик..
Reply With Quote
Old 26.04.2004, 15:52   #36
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

Quote:
Originally Posted by greka
а всякие повышения вероятностей - это проделки Фикса.
о повышении вероятностей, кажется, никто кроме тебя и не говорит грека ака фикс?
Reply With Quote
Old 26.04.2004, 15:54   #37
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

Quote:
Originally Posted by who
полностью согласен с грекой!

еще раз отсылаю всех любителей игр с вероятностью нахождения элементов при обычном последовательном поиске к Д.Кнуту
если честно, я кнута не читал, а так бегло что-то найти про вероятности не удалось. если можно, в двух словах - что там, связанное с вероятностями?
Reply With Quote
Old 26.04.2004, 17:24   #38
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Quote:
Originally Posted by Aram Hambardzumyan
о повышении вероятностей, кажется, никто кроме тебя и не говорит грека ака фикс?
т.е. об "улучшенном" варианте поиска для этого примера тоже никто не говорил, получается?
Reply With Quote
Old 27.04.2004, 06:11   #39
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

Quote:
Originally Posted by greka
т.е. об "улучшенном" варианте поиска для этого примера тоже никто не говорил, получается?
все, что было о вероятности - оценки одного единственного алгоритма случайной выборки. попытки улучшенных алгоритмов поиска были, но с вероятностью связи не имели.
Reply With Quote
Old 27.04.2004, 07:09   #40
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 13:55.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.