проститутки львів
Follow us on twitter

неОфіційний форум Чернівецького Національного Університету (ЧНУ)

 
Примітки

Найцікавіше з Хабрахабр Найцікавіше з Хабрахабр

Відповідь  
Старий 03.08.2010, 23:07   #1
admin
Інженерно-технічний
 
Аватар для admin
under construction
Детальніше...
 
Реєстрація: 04.03.2009
Дописів: 4.854
Завантажень: 4
Завантажень: 3
Сказав Дякую: 156
Йому подякували 150 раз(а) в 120 повідомленнях
Icon14 Алгоритмы / Быстрый поиск



Я вижу, простые (хоть и очень важные) алгоритмы тут не любят. Ну давайте поговорим о чём-нибудь более сложном. Допустим о поиске.
Но прежде, чем рассказывать алгоритм, я попрошу вас самих немного подумать. Предположим у нас есть следующий бинарный массив:
1101
1011
1111
0101
0001
0111
0100

На вход поступает строка из этого массива, а вам надо сказать под каким номером, эта строка находится в исходном массиве. Я утверждаю, что могу сказать это минимум за 2, а максимум за 4 поразрядных (!) сравнения. В среднем же мне потребуется 2.85 поразрядных сравнений. Для массива из 70000 тысячеразрядных строк, мне потребуется 16.12 сравнений.

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

[Посилання можуть бачити тільки зареєстровані користувачі ]
__________________
admin зараз поза форумом   Відповісти з цитуванням
Хочеш допомогти розвитку форуму? Відправ посилання всім своїм друзям. Дякую!

Відповідь  

Параметри теми

Ваші права у розділі
Ви не можете створювати теми
Ви не можете писати дописи
Ви не можете долучати файли
Ви не можете редагувати дописи

BB-код є Увімк.
Усмішки Увімк.
[IMG] код Увімк.
HTML код Вимк.

Швидкий перехід

Схожі теми
Тема Автор Розділ Відповідей Останній допис
Поиск и сравнение фото в онлайне lunizz Болталка 1 27.04.2011 17:00
Linux для всех / Быстрый tile окон с помощью Compiz admin Найцікавіше з Хабрахабр 0 20.02.2010 20:47
Генетические алгоритмы Stalker Комп'ютерних наук 11 05.02.2010 20:57
Алгоритмы / Adaptive boosting admin Найцікавіше з Хабрахабр 0 10.01.2010 17:10
Поиск шпор admin Учбові матеріали 0 11.03.2009 20:05




знакомства для секса