Пусть имеется некоторый набор данных и
требуется определить, где в этом наборе находится заданный элемент ( и
есть ли он в наборе ). Такая задача называется задачей поиска.
Большинство задач поиска сводится к поиску в таблице ( массиве )
элемента с заданным значением.
Пример
Написать программу поиска элемента x в массиве из n элементов. Значение элемента x вводится с клавиатуры.
Решение
Пусть имеются следующие описания:
Const n = 10; { размерность массива }
Var a: array ( 1...n ) Of Integer;
{ массив из n элементов целого типа }
x: Integer; { искомый элемент целого типа }
В данном случае известно только значение разыскиваемого элемента,
никакой дополнительной информации о нем или о массиве, в котором его
надо искать, нет. Проверка одного элемента не дает никакой информации об
остальных. Поэтому для решения задачи разумно применить очевидный метод
- последовательный просмотр массива и сравнение значения очередного
рассматриваемого элемента с данным. Если значение очередного элемента
совпадает с x, то запомним его номер в переменной к.
For i: =1 To n Do If a[i] = x Then k: = i;
Этот способ решения поставленной задачи, безусловно, приводит к цели, но обладает рядом существенных недостатков:
• если значение x встречается в массиве несколько раз, то найдено будет последнее из них;
• после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется n сравнений.
Разумно прекратить просмотр сразу после
обнаружения заданного элемента. Так как в этом случае число повторений
не известно, необходимо использовать цикл с предусловием. В результате:
- либо будет найден искомый элемент, то есть найдется такой индекс i, что а [ i ] = x;
- либо будет просмотрен весь массив, и искомый элемент не обнаружится.
Таким
образом, поскольку нужно продолжать поиск до обнаружения искомого
элемента или до конца массива, условие окончания цикла может выглядеть
так:
While ( i <= n ) And ( a[ i ] x ) Do Inc ( i );
Примечание: Необходимо обратить внимание на порядок простых условий в
составном условии цикла. Здесь предполагается, что второе условие не
проверяется, если результат логического выражения ясен после проверки
первого условия. В противном случае возникнет отказ из-за выхода индекса
за границы массива.
Программа линейного поиска:
program n6;
const n=5;
var a:array[1..n] of integer;
{ массив из n элементов целого типа }
x:integer; { искомый элемент целого типа }
i,k:integer;
begin
writeln('Введите исходный массив:');
for i:=1 to n do read(a[i]);
writeln('Введите x');
readln(x);
for i:=1 to n do if a[i]=x then k:=i;
while (i<=n) and (a[i]x) do inc(i);
writeln('a[',k,']=',x,'=x');
end.
