Методы программирования. Громов Ю.Ю - 108 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

108
Упражнения
1. Выполните методом Soundex пошаговое преобразование фами-
лий Euler, Gauss, Hilbert, Knuth, Lloyd и Lukasiewicz в соответствующие
им коды.
2. Определите количество сравнений K = K
i
и количество сравне-
ний i ≤ N, производимых алгоритмом S и алгоритмом Q при успешном
поиске ключа 765 и неудачном поиске ключа 843 в последовательности
ключей 503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677,
765, 703. Проанализируйте полученные результаты.
3. Установите общее количество сравнений, производимых алго-
ритмом Q, и общее количество сравнений, производимых алгоритмом T,
при успешном поиске ключей 61, 512, 908 и неудачном поиске ключей
172, 769 в упорядоченной последовательности ключей 61, 87, 154, 170,
275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908. Проанализируйте
полученные результаты.
19. ПОИСК В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ
Далее обсудим методы поиска, основанные на линейном упорядоче-
нии ключей (числовом или алфавитном):
K
1
< K
2
< …
< K
N
.
При поиске такими методами после сравнения аргумента K с клю-
чом K
i
из таблицы поиск продолжается одним из трёх путей, в зависимо-
сти от того, какое из трёх условий будет выполнено:
– если K < K
i
, то записи R
i
, R
i+1
, …,
R
N
исключаются из рассмот-
рения;
– если K = K
i
, то поиск завершён;
– если K > K
i
, то записи R
1
, R
2
, …, R
i
исключаются из рассмот-
рения.
Рассмотрим метод, заключающийся в следующем. Сначала, сравнив
аргумент K со средним ключом в таблице, определяют, в какой половине
таблицы находится искомый ключ. Затем применяют ту же процедуру к
половине таблицы, четверти таблицы и т.д. Максимум за величину по-
рядка lg N сравнений находят искомый ключ (либо устанавливают, что
его нет в таблице). Такой метод известен как логарифмический поиск, или
метод деления пополам, или бинарный поиск.
Хотя основная идея бинарного поиска сравнительно проста, детали
его реализации нетривиальны. В одной из наиболее популярных форм
реализации метода используются два указателя l и u, которые обозначают
нижнюю и верхнюю границы поиска соответственно.

Страницы