Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Осн-й вопрос задачи поиска: где в заданной совокупн. данных находится элемент, обладающий заданым св-вом. Большинство задач поиска сводится к простейшей – поиск в таблице эл-та с заданным значением.
Алгоритмы поиска. 1)Линейный поиск. Продолжает поиск до обнаружения искомого эл-та или до конца массива, последов-но перебирая все эл-ты; 2)Линейный поиск с использ-ем барьера. В массив на n+1 место записываем искомый эл-т X, который будет являться барьерным. Если эл-т будет найден только при i = n+1, значит, интересующего эл-та в массиве нет; 3)Бинарный поиск. Это один из методов непоследовательного поиска, назыв-ый также методом половинного деления. Идея: проверить, является ли x средним элементом массива. Если да, то ответ получен, если нет, то если x> среднего элемента то применить этот метод к левой половине массива, если x< среднего элемента, то применить этот метод к правой половине массива. Значение m=[(l+r)/2], где m – индекс среднего, l –первого, r – последнего элемента рассматриваемой части массива. Массив д.б. отсортирован При использ-и на каждом шаге область поиска сокращ-ся в 2 раза.;
begin
l:=1; r:=n; {на первом шаге рассмаривается весь массив}
f:=false;
while (l<=r)and not f do
begin
m:=(l+r)div2;
if a[m]=x then f:=true; {элемент найден. Поиск надо прекратить}
if a[m]<x then l:=m+1 {отбрасывается левая часть}
else r:=m-1; {отбрасывается правая часть}
end
end;
Анализ: Линейный поиск: число сравнений зависит от того, где располагается искомая запись. Если она окажется первой, выполняется только одно сравнение, если последней – n сравнений. Следовательно, успешный поиск требует в среднем (n+1)/2 сравнений. Неуспешный потребует n+1 сравнений с учетом барьерного эл-та. Бинарный поиск: каждое сравнение уменьшает число кандидатов в 2 раза, поиск применяется только в отсортированном массиве, тогда как последовательный поиск может работать в любом массиве. Поэтому, если необходимо произвести однократный поиск, лучше воспользоваться линейным поиском. 4)Поиск подстроки в строке. Прямой поиск. Сводится к послед-ым сравнениям отд-х символов. Поиск прод-ся до тех пор, пока не обнаруж-ся сравнение; 5)Поиск подстроки в строке. Алгоритм Бойера-Мура. Поиск ведется от начала строки, но с конца искомой подстроки, для которой форм-ся таблица, размерн-ть кот-й – 256. Эле-ми таблицы явл-ся расстояния от последнего символа искомой подстроки до ее каждого символа. Когда очередной символ подстроки не совпадает с очередным символов строки для последнего из таблицы расстояний опред-ся соответствующее расстояние, после чего конец искомой подстроки сдвиг-ся вправо на соответствующее число позиций, тем самым ряд позиций пропускается, сокращая время поиска. Всегда требуется меньше n сравнений, когда последний символ искомой строки x всегда попадает на несовпадающий символ строки s, число сравнений равно n/m, n – длина строки s, m – длина строки x; 6)Поиск подстроки в строке. Алгоритм Кнута-Мориса-Пратта. j – номер символа, входящего в образ, а d[j] – длина max последовательности символов образа x, предшествующих позиции j, которая совпадает полностью с началом образа.
ABCA ABCE d[4]:=3 | ABCABCA ABCABCE d[7]:=6 | ABCDE ABCDG d[5]:=4 |
Требует только n сравнений даже в самом плохом случае, где n – длина строки. Сравнение нач-ся с первого символа строки S.
Дата публикования: 2015-02-03; Прочитано: 230 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!