6. Сигнатурой имени является его цифровой код (пример: «LESK*M*», «5375*6*»). Для поиска ложных совпадений следует сопоставить всем именам их цифровые сигнатуры, отсортировать их но сигнатурам (и по имени для одинаковых сигнатур), а затем последовательно считывать отсортированный файл и выводить сообщения об одинаковых сигнатурах, соответствующих различным именам. Чтобы определить имя по цифровой сигнатуре, мы используем структуру, в которой эти сигнатуры содержатся вместе с именами и другими данными. Можно, конечно, отсортировать эту структуру и затем искать в ней нужную сигнатуру с помощью двоичного поиска, но в реальной системе лучше всего будет воспользоваться хэшированием или базой данных.
7. Чтобы транспонировать матрицу, Виссоцки пронумеровал ее столбцы и строки, вызвал системную сортировку сначала по номерам столбцов, а затем по номерам строк, после чего удалил номера строк и столбцов с помощью третьей программы.
8. Ага!-озарение для этой задачи в том, что сумма элементов какого-то из к-эле- ментпых подмножеств не превышает t тогда и только тогда, когда сумма подмножества из к наименьших элементов не превышает этого числа. Это подмножество может быть найдено за время, пропорциональное л log л, сортировкой исходного множества, ИЛИ за время, пропорциональное п, с помощью алгоритма выбора (см. решение задачи 9 из главы 11). Когда Ульман предложил это задание в качестве упражнения своим студентам, те предложили всевозможные алгоритмы решения, среди которых были и алгоритмы с упомянутой скоростью работы, но кроме них были и такие, которые работали за O(n\ogk), О(пк), 0(п2) и 0(л*). Можете ли вы придумать естественные алгоритмы решения этой задачи с таким временем работы?
Опубликовал vovan666
April 17 2013 00:06:28 ·
0 Комментариев ·
4417 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
