Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход — простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
1. Элемент найден, т.е. ai = x.
2. Весь массив просмотрен и совпадения не обнаружено.

Это дает нам линейный алгоритм:
i := 0;
WHILE (i < N) AND (a[i] <> x) DO
i := i+1 ;
END;
Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:
(0 ? i < N) AND (Ak : 0 ? k < i : ak ? x)
Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие:
((i = N) OR (ai = x)) AND (Ak : 0 ?  k < i : ak ? x)
Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.
Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.
Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск ?
Единственная возможность — попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению — сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент «барьером», ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так:
a: ARRAY[0..N] OF INTEGER
и алгоритм линейного поиска с барьером выглядит следующим образом:
a[N] := x;
i := 0;
WHILE a[i] <> x DO
i := i+1;
END;
Результирующее условие, выведенное из того же инварианта, что и прежде:
(ai=x) AND (Ak : 0 ? k < i : ak ? x)
Ясно, что равенство i = N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

Поиск делением пополам (двоичный поиск).

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники