5.1.  Линейный поиск

Рассмотрим, как осуществляется поиск для данных, хранящихся в массиве.

Среди разновидностей простей­ших задач поиска, встречающихся на практике, можно выделить следующие типы:

1. Найти хотя бы один элемент, равный заданному элементу X. В ре­зультате необходимо получить i — индекс (номер) элемента массива, такой, что a[i] = X.
2. Найти все элементы, равные за­данному X. В результате необходимо получить количество таких элементов и (или) их индексы.

Иногда поиск организуется не по совпадению с элементом X, а по выпол­нению некоторых условий. Примером может служить поиск элементов, удо­влетворяющих условию: X₁ J a[i] J X₂, где X₁ и X₂ заданы.

Если нет никакой добавочной ин­формации о разыскиваемых данных, то самый простой подход — последова­тельный просмотр элементов массива.

5.2. Поиск одного элемента, удовлетворяющего условию поиска

Пример 5.1. Задан одномерный массив из n чисел. Определить, есть ли в нем хотя бы один элемент, рав­ный x (значение x вводится).

I. Исходные данные: массив a, ко­личество чисел n, искомое число x.

II. Результат: вывод сообщения «Элемент найден» или «Элемент не найден».

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Пусть p — переменная ло­гического типа, которая имеет значение «истина», если элемент в массиве найден, и «ложь» — в противном случае. До просмотра элементов массива p := false.
3. В цикле будем просматривать все числа в массиве и сравнивать их с числом x.
4. После окончания поиска воз­можна одна из двух ситуаций:

4.1. Искомый элемент найден (p := true), т. е. в массиве есть такой элемент a[i], что a[i] = x.

4.2. Весь массив просмотрен, и совпадений не обнаружено (p := false).

5. Вывод результата.

IV. Описание переменных: а — array[1..10] of integer; n, x — integer; p: boolean.

Часто требуется не только опреде­лить, есть ли в массиве искомый эле­мент, но и установить, на каком месте он находится.

Будем хранить индекс найденного элемента (пример 5.2) в переменной k. После выполнения данного алгорит­ма по значению переменной k мож­но определить, есть ли в массиве ис­комый элемент, и если есть, то где он стоит. Если в массиве несколько таких элементов, то в переменной k будет храниться номер последнего из них. Если такого элемента нет, то значение переменной k не изменится (k останется равным 0).

На практике операцию поиска при­ходится выполнять достаточно часто, и скорость работы программы нахо­дится в прямой зависимости от ис­пользуемого алгоритма поиска.

В рассмотренных выше алгоритмах требуется просмотреть весь массив, да­же в том случае, если искомый элемент находится в массиве на первом месте.

Для сокращения времени поиска можно останавливаться сразу после того, как элемент найден. В этом слу­чае весь массив придется просмотреть только тогда, когда искомый элемент последний или его нет вообще (при­мер 5.3). Цикл заканчивает работу, когда будет найден искомый элемент либо когда k = n + 1, т. е. элемента, совпадающего с x, не существует.

*При такой реализации на каждой итерации цикла требуется увеличи­вать индекс k и вычислять логическое выражение. Ускорить поиск можно, упростив логическое выражение. По­местим в конец массива дополнитель­ный элемент со значением х. Тогда со­впадение с х обязательно произойдет, и можно не проверять условие a[k] < > x. Такой вспомогательный элемент ча­сто называют «барьером» или «часо­вым», так как он препятствует вы­ходу за пределы массива. В исходном массиве теперь будет n + 1 элемент (пример 5.4).

5.3. Нахождение всех элементов, удовлетворяющих условию поиска

Если требуется определить коли­чество элементов, удовлетворяющих какому-либо условию, то для этого определяют отдельную переменную, значение которой увеличивают на 1 каждый раз, когда найден нужный элемент. Такую переменную называ­ют счетчиком. До начала просмотра

начальное значение, или, дру­гими словами, инициализировать значение переменной. В случае под­счета количества элементов, удовлет­воряющих условию, счетчик ини­циализируется нулем. Для решения задачи нужно просматривать весь массив.

Пример 5.5. Задан одномерный массив из n чисел. Определить коли­чество элементов, кратных x в линей­ном массиве.

I. Исходные данные: массив a, ко­личество чисел n, искомое число x.

II. Результат: количество элемен­тов, удовлетворяющих условию, — k.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика.
3. В цикле будем просматривать все числа в массиве и сравнивать с нулем их остатки от деления на число x. Если остаток равен нулю, то счетчик увеличиваем на 1.
4. Вывод результата.

IV. Описание переменных: а — array[1..10] of integer; n, x, k — integer.

Если необходимо не только посчи­тать, сколько элементов удовлетворя­ют условию, но и сохранить индексы таких элементов, то для этого мож­но воспользоваться дополнительным массивом. Создадим новый массив b. Как только будет найден необходи­мый элемент, его индекс будет зано­ситься в массив b. Переменная k бу­дет хранить номер последнего заня­того места в массиве b. Вначале k = 0 (пример 5.6).

После завершения работы первые k элементов массива b будут содер­жать индексы искомых элементов.

Если для решения задачи потребу­ются значения всех найденных эле­ментов, то в программе возможно та­кое обращение к элементам массива: a[b[i]]. Адрес элемента в массиве а будет определяться значением элемен­та массива b по адресу i. Для вывода значений элементов в примере 5.6 по­следний цикл нужно заменить на

for var i := 1 to k do write(a[b[i]],'  ');

5.4. Решение задач с использованием алгоритма линейного поиска

Пример 5.7. Известны результа­ты ЦТ по математике для n человек. Определить, есть ли среди них хотя бы один человек с баллом выше x. Значе­ние x вводится с клавиатуры. Резуль­таты экзамена получить случайным образом.

I. Исходные данные: массив а, ко­личество чисел n, число x.

II. Результат: сообщение соответ­ствует условию задачи.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Просмотр элементов с нача­ла. Как только элемент найден, остановимся.
3. Если весь массив просмо­трен, значит, в исходном массиве нет элемента, удовлетворяющего условию задачи, иначе выводим номер найденного элемента.

IV. Описание переменных: а — array[1..20] of integer; n, x, k — integer.

Пример 5.8. В двух линейных мас­сивах x и y, заданных случайным об­разом, хранятся координаты точек плоскости (-200 J X[i], Y[i] J 200). Определить, каких точек больше — лежащих внутри или снаружи обла­сти, ограниченной окружностью ра­диуса R с центром в начале координат (будем считать, что точки, лежащие на окружности, лежат внутри обла­сти). Построить окружность и точки. Точки, принадлежащие внутренней области, нарисовать красным цветом, а внешней области — синим цветом.

I. Исходные данные: X, Y — масси­вы чисел, R — радиус окружности, n — количество точек.

II. Результат: рисунок, соответству­ющий условию задачи, и сообщение: «Внутри точек больше», «Снаружи то­чек больше» или «Точек поровну».

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчиков: k1:= 0; k2:= 0.
3. Будем просматривать все точ­ки и для каждой проверять при­надлежность области. Если X² + Y² ≤ R², то точка лежит внутри области, тогда увеличим значение счетчика k1 на 1, если нет, то уве­личим на 1 значение счетчика k2.
4. Сравним значения k1 и k2 и выведем результат.
5. Поскольку координаты точек принадлежат отрезку [-200, 200], то оси координат можно нарисо­вать пересекающимися в точке с координатами (200, 200). Для преобразования координат точек в экранные нужно к значению абсциссы прибавить 200, а значение ординаты нужно отнять от 200 (ось Y на экране направлена вниз, поэтому нужно поменять знак ор­динаты). Строить точки можно в том же цикле, в котором проис­ходит проверка.

IV. Описание переменных: X, Y — array[1..1000] of integer; n, k1, k2, R — integer.

Пример 5.9. На складе хранятся пустые ящики для упаковки товара. Известно, что масса одного пакета с конфетами x кг. Какова суммарная масса пакетов с конфетами, которые можно упаковать в такие ящики, за­полнив ящик целиком?

I. Исходные данные: массив а, ко­личество чисел n, число x.

II. Результат: количество ящиков — k, суммарная масса — S.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика и значения суммы: k := 0; S := 0.
3. Просматривая массив, про­верим, является ли текущий эле­мент числом, кратным x (в этом случае ящик будет заполнен цели­ком). Как только элемент найден, увеличим счетчик k на 1, а пере­менную S — на значение найден­ного элемента массива.
4. Вывод результата.

IV. Описание переменных: а — array[1..20] of integer; n, x, k, S — integer.

Пример 5.10. Имеется список маль­чиков 10 В класса и результаты их бега на 100 м. Для сдачи норматива

необходимо пробежать дистанцию не более чем за 16 с. Вывести фамилии учащихся, которые не выполнили норматив по бегу. Сколько таких уча­щихся в классе?

I. Исходные данные: массивы fam (фамилии учащихся) и r (результаты бега в секундах), количество учащих­ся n.

II. Результат: фамилии тех уча­щихся, которые не выполнили норма­тив по бегу.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика: k := 0.
3. Будем просматривать массив с результатами и проверять, явля­ется ли текущий элемент числом больше 16 (норматив не сдан). Ес­ли такое значение найдено, то вы­ведем элемент массива fam с соот­ветствующим номером и увеличим значение счетчика на 1.
4. Вывод значения счетчика.

IV. Описание переменных: fam — array[1..20] of string; r — array[1..20] of real, n, k — integer.

Пример 5.11*. Задан одномерный массив из N целых чисел. Определить количество элементов, которые явля­ются числами Смита. (Число Смита — это такое составное число, сумма цифр которого равна сумме цифр всех его простых сомножителей.) Например, числом Смита является 202 = 2 *101, поскольку 2 + 0 + 2 = 4, и 2 + 1 + 0 + 1 = 4.

I. Исходные данные: а — массив чи­сел, n — количество чисел в массиве.

II. Результат: числа Смита и их ко­личество в массиве.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика: k := 0.
3. Будем просматривать каж­дый элемент массива и опреде­лять, является ли он числом Смита. Для проверки создадим функцию check, которая будет по­лучать в качестве параметра эле­мент массива, а также возвращать значение true, если число являет­ся числом Смита, и false в про­тивном случае.

3.1. Найдем сумму цифр числа.

3.2. Будем раскладывать чис­ло на простые множители и для каждого множителя находить сумму цифр.

3.3. Для разложения числа на простые множители будем делить его сначала на 2 (пока делится), затем на 3. На 4 чис­ло уже делиться не будет, будем делить его на 5 и т. д. Закончит­ся разложение тогда, когда по­сле всех делений число станет равным 1.

4. Также нам понадобится функция sum, которая для чис­ла будет возвращать его сумму цифр.

IV. Описание переменных: a — ar- ray[1..100] of integer; n, k — integer.

Пример 5.12*. Задан одномерный массив из n строк. Каждая строка яв­ляется предложением из слов, разде­ленных пробелами. Найти и вывести те предложения, в которых нечетное количество слов.

I. Исходные данные: а — массив строк, n — количество строк в массиве.

II. Результат: искомые строки и их количество.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика: k := 0.
3. Будем просматривать каж­дую строку и определять, сколько в ней слов. Для проверки созда­дим функцию check, которая бу­дет получать в качестве параметра элемент массива и возвращать ко­личество слов в строке. Если ко­личество слов является нечетным числом, то выведем строку и уве­личим значение счетчика.

3.1. Перед каждым словом предложения, кроме первого, стоит пробел, слово начинается с символа, который пробелом не является.

3.2. Добавим пробел перед первым словом, тогда коли­чество слов будет определять­ся количеством сочетаний пар символов: пробел и не пробел.

IV. Описание переменных: a — array[1..100] of string; n, k — integer.

При вводе данных для тестирования программы нужно помнить, что после каждого предложения необходимо нажимать клавишу Enter.

В данном случае строка как тип данных может не соответствовать строке в окне вывода. В примере 5.12 вводятся 3 строки:

1. «Многие компании разрабатыва­ют свои правила по оформлению кода».
2. «В них прописаны также прави­ла именования переменных».
3. «Компания Microsoft использует так называемую «венгерскую нотацию».

В окне вывода количество строк может быть больше (на рисунке их 6).

То, как будут выглядеть вводимые строки в окне вывода, зависит от ши­рины окна приложения PascalABC. NET. На большом мониторе, если окно приложения развернуто на весь экран, строк может быть три.

Компилятор определяет, что ввод строки закончен, если была нажата клавиша Enter. Внешний вид строк в окне вывода для компилятора не имеет значения.

Чтобы поиск был результативным и быстрым, разрабатывают эффективные алгоритмы поиска. Важную роль в про­цессе поиска информации играет спо­соб хранения данных. Одной из самых простых структур для этого является массив.

Алгоритмы поиска можно разделить на алгоритмы, использующие неупо­рядоченные наборы данных, и на алго­ритмы, работающие с предварительно упорядоченным набором данных.

Примером поиска в неупорядочен­ном наборе данных может служить по­иск тетради конкретного учащегося в стопке тетрадей, сданных на проверку. Чтобы найти нужную тетрадь, возмож­но, придется пересмотреть все. Поиск в словаре — поиск в упорядоченном набо­ре данных, т. к. все слова расположены в алфавитном порядке.

Пример 5.1.
V. Программа:

var a: array[1..10] of integer;
      n, x: integer;
      p: boolean;
begin
write (' Количество n = '); 
readln(n) ;
writeln( 'Элементы массива') ;
for var i := 1 to n do
read (a [i]) ;
write ('Число x = '); 
readln(x) ;
//линейный поиск элемента 
p := false;
for var i := 1 to n do
if a[i] = x then p := true;
if p then writeln('Элемент найден')
else writeln('Элемент не найден');
end.

VI. Тестирование

Пример 5.2
V. Программа

var a: array[1. .10] of integer;
      n, x, k: integer;
 begin
write ('Количество n = ');
 readln (n) ;
writeln ('Элементы массива');
for var i := 1 to n do read (a [i]); 
write ('Число x = '); 
readln (x) ;
//линейный поиск элемента 
k := 0;
for var i := 1 to n do if a[i] = x then k := i;
if k = 0 then writeln ('Элемент не найден')
else
writeln ('Элемент найден на месте ', k) ;
end.

VI. Тестирование.

Пример 5.3.
Фрагмент программы:

//линейный поиск элемента
k:=1;
while (k<=n) and (a[k]<>x) do k:=k+1;
if k = n+1 then
writeln ('Элемент не найден')
else
writeln ('Элемент найден на месте ', k);.

Пример 5.4*.
Фрагмент программы:

//линейный поиск с барьером
a[n + 1] := х;
k := 1;
while a[k]<>x do k := k + 1;
if k = n + 1 then
writeln('Элемент не найден')
else
writeln('Элемент найден на месте ', k);

VI. Тестирование.

В современных языках программи­рования используются библиотеки, содержащие функции для поиска эле­ментов в массивах (и других структу­рах данных). В PascalABC.Net такие функции реализованы только для ди­намических массивов (размер массива может изменяться во время выполне­ния программы, элементы нумеруют­ся с нуля). Описание функций можно найти в справочнике в разделе «Мето­ды расширения одномерных динамиче­ских массивов». Пример использования функции поиска всех элементов масси­ва, больших 5:

var c : array of integer;
begin
setlength(c, 10);
for var i := 0 to 9 do c[i] := random(1, 10);
println(c) ;
c.FindAll(p -> p > 5). Println;
end.

Пример 5.5
V. Программа

var a: array[1. .10] of integer;
      n, x, k: integer;
begin
write ('Количество n =  ');
readln (n);
writeln('Элементы массива');
for var i := 1 to n do read (a [i]); 
write ('Число x = ');
readln(x); 
k := 0;
for var i := 1 to n do if a [i] mod x = 0 then k := k + 1;
writeln('B массиве ', k,' элемент (-а, -ов), кратный (-х)', x) ;
end.

VI. Тестирование.

Пример 5.6.
V. Программа:

var a, b: array[1.. 10] of integer;
      n, x, k: integer;
begin
write ('Количество n = ');
readln (n) ;
writeln('Элементы массива');
for var i := 1 to n do read (a [i]);
write ('Число x = ');
readln(x); 
k := 0;
for var i := 1 to n do if a [i] mod x = 0 then
begin
k := k + 1; 
b[k] := i;
end;
writeln('B массиве ', k, ' элемент (-а,-ов), кратный(-х) ', x);
writeln('Местоположение ');
for var i := 1 to k do write (b[i],'  ');
end.

VI. Тестирование.

Пример 5.7.
V. Программа:

var a: array[1. .20] of integer;
      n, x, k: integer;
begin
write ('Количество n = '); 
readln(n) ;
writeln( 'Элементы массива');
for var i := 1 to n do 
begin
a[i] := random(0,100); 
write (a [i],' ');
end;
writeln;
write ('Число x ='); 
readln(x) ;
//линейный поиск с барьером 
a[n+1] := x + 1; 
k := 1;
while (a[k] <= x) do k := k + 1; 
if k = n+1 then writeln('Нет таких')
else
writeln('Это человек с № ',k, ', его балл - ', a[k]);
end.

VI. Тестирование.

Пример 5.8.
V. Программа:

uses graphABC;
var X,Y: array [1..1000] of integer;
      n, k1, k2, R: integer;
begin
write ('Количество точек n = ');
read(n);
writeln(n) ;
for var i := 1 to n do
begin
X[i]:= random(-200,200);
Y[i]:= random(-200,200);
end;
writeln('Радиус окружности'); 
read(R); 
writeln(R) ;
{Построение окружности и осей координат} 
circle(200,200,R); 
line(0,200,400,200); 
line (200,0,200,400); 
k1 := 0;
k2 := 0; 
for var i := 1 to n do if X[i]*X[i]+Y[i]*Y[i]<=R*R then begin
k1 := k1 + 1;
SetPixel (X[i]+200,200-Y[i], clred);
end
else
begin
k2 := k2 + 1;
SetPixel (X[i]+200,200-Y[i],clblue);
end;
if k1 > k2 then
writeln('Внутри больше')
else
if k1<k2 then
writeln('Снаружи больше')
else
writeln( 'Поровну')
end.

VI. Тестирование.

Пример 5.9.
V. Программа:

var a: array [1..20] of integer;
      n, x, k, S: integer;
begin
write ('Количество ящиков:'); 
readln(n) ;
writeln('Вместимость ящиков');
for var i : = 1 to n do read (a [i]) ;
write ('Масса конфет:'); 
read(x); 
k := 0; 
S := 0;
for var i := 1 to n do if a[i] mod x = 0 then
 begin
k := k + 1;
S := S + a[i];
end;
writeln('На складе ', k,' ящ.'); 
writeln('Суммарная масса', S);
end.

VI. Тестирование.

Пример 5.10.
V. Программа:

var r: array [1..20] of real;
       fam: array [1..20] of string;
       n, k: integer;
begin
writeln( 'Количество учащихся: ');
readln(n);
writeln( 'Фамилия и результат: ');
for var i := 1 to n do
begin
readln(fam[i]);
readln(r[i]);
end;
writeln('Фамилии не сдавших норматив:');
k := 0;
for var i := 1 to n do if r[i] >16 then 
begin
k := k + 1;
writeln(fam[i]);
end;
writeln('Не сдали норматив: ', k);
end.

VI. Тестирование. 

Пример 5.11*.
V. Программа:

var a: array [1..100] of integer;
n, k: integer;
function sum(x: integer): integer;
var s: integer;
begin
s := 0;
while x > 0 do
 begin
s := s + x mod 10;
x := x div 10;
end;
sum := s;
end;
function check(x: integer):
boolean;
var s1, s2, d: integer;
begin
s1 := sum(x); s2 := 0; d := 2;
//разложение на простые множители
while x <> 1 do
begin
while x mod d = 0 do 
begin
s2 := s2 + sum(d); x := x div d;
end;
d := d + 1;
end;
check := s1 = s2;
end;
begin
writeln( 'Количество');
readln(n);
writeln( 'Элементы');
for var i := 1 to n do read(a[i]);
k := 0;
writeln('Числа Смита');
for var i := 1 to n do if check(a[i]) then
begin
inc(k);
write (а [i], '  ');
end;
writeln;
writeln('Всего - ', k);
end.

VI. Тестирование. 

Пример 5.12.
V. Программа:

var a: array [1..100] of string;
       n, k: integer;
function check(x: string): integer;
var s, len: integer;
begin
s := 0;
x := '  ' + x;
len := length(x);
for var i := 1 to len - 1 do
if (x[i] = '  ') and (x[i + 1] <> '  ')
then
inc(s);
check := s;
end;
begin
writeln( 'Количество');
readln(n);
writeln(' Элементы');
for var i := 1 to n do readln(a[i]);
k := 0;
writeln;
writeln('Искомые строки:');
for var i := 1 to n do
if check(a[i]) mod 2 <> 0 then
begin
inc(k);
writeln(a[i]);
end;
writeln('Всего - ', k);
end.

VI. Тестирование.