1. Чтобы пайги все анаграммы некоторого слова, мы начинаем с вычисления его сигнатуры. Если предварительная обработка не предусматривается, придется считывать весь словарь, вычислять сигнатуру каждого из слов и затем сравнивать ее с сигнатурой исходного слова. Если разрешена предварительная обработка, можно решить задачу двоичным поиском по структуре, содержащей пары (сигнатура, слово), упорядоченные по сигнатуре. Mvccep и Саинн реализуют несколько программ поиска анаграмм в главах 12-15 книги «Учебное и справочное руководство по STL» (Musser, Saini, STL Tutorial and Reference Guide, Addison Wesley, 1996).
2. Двоичный поиск позволяет найти повторяющийся элемент рекурсивным поиском под-иптервала, содержащего более половины чисел. В моем первом варианте решения не гарантировалось, что количество чисел на каждой итерации сокращается вдвое, поэтому в худшем случае время выполнения log2 п проходов было пропорционально п log п. Джиму Сейксу удалось сократить время выполнения до линейного, когда он учел тот факт, что можно отбрасывать повторяющиеся числа, если их слишком много. Если известно, что повторяющееся число должно быть в некотором диапазоне, включающем m чисел, то только т+1 число будет сохранено па рабочей лепте. Все лишние числа просто сбрасываются. Несмотря па то, что в его методе входные данные часто игнорируются, эта стратегия оказывается достаточно падежной: одно повторяющееся число будет найдено всегда.
Опубликовал vovan666
April 17 2013 00:06:22 ·
0 Комментариев ·
2564 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
