Алгоритмы обработки массивов · Интерактивный конспект
§ 5. Поиск элементов с заданными свойствами
Научимся искать в массиве элементы, равные заданному или удовлетворяющие условию: определять, есть ли такой элемент, на каком месте он стоит и сколько таких элементов.
Алгоритм, при котором для поиска нужного элемента последовательно просматривают все элементы массива в порядке их записи, называется линейным или последовательным поиском.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Линейный поиск элемента, равного x
Модель просматривает элементы по порядку и сравнивает каждый с x. Нажимайте «Один шаг →»: таблица показывает, совпал ли элемент. Проверьте данные примера 5.1: 1 2 3 4 5 и x = 4, затем 1 3 5 7 9 и x = 6.
Человек постоянно сталкивается с задачами поиска информации: работает со справочниками, библиотечной картотекой, ищет сведения в сети Интернет. Чтобы поиск был результативным и быстрым, разрабатывают эффективные алгоритмы поиска. Важную роль играет способ хранения данных; одна из самых простых структур для этого — массив.
Среди простейших задач поиска в массиве выделяют два типа:
1. Найти хотя бы один элемент
Найти элемент, равный заданному X. Результат — индекс (номер) i элемента массива, такой, что a[i] = X.
2. Найти все элементы
Найти все элементы, равные заданному X. Результат — количество таких элементов и (или) их индексы.
Иногда поиск организуется не по совпадению с элементом X, а по выполнению некоторого условия, например X1 ≤ a[i] ≤ X2, где X1 и X2 заданы. Если нет никакой добавочной информации о разыскиваемых данных, то самый простой подход — последовательный просмотр элементов массива.
Алгоритмы поиска делят на алгоритмы, использующие неупорядоченные наборы данных, и алгоритмы, работающие с предварительно упорядоченным набором. Поиск тетради конкретного учащегося в стопке тетрадей, сданных на проверку, — поиск в неупорядоченном наборе: возможно, придётся пересмотреть все тетради. Поиск в словаре — поиск в упорядоченном наборе, так как все слова расположены в алфавитном порядке.
Главная мысль: Алгоритм, при котором для поиска нужного элемента последовательно просматривают все элементы массива в порядке их записи, называется линейным или последовательным поиском.
2
Поиск одного элемента, удовлетворяющего условию
Найден ли элемент, показывает логическая переменная p или индекс k; цикл while позволяет закончить поиск сразу после того, как элемент найден.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Последнее, первое совпадение и барьер
Сравните цели поиска. «Последнее совпадение» — как в примере 5.2 (k := i при каждом совпадении), «Первое совпадение» — как в примере 5.3 с циклом while, «Первое с барьером» — пример 5.4: в ячейку n + 1 записано x. Введите 1 3 3 3 5 и x = 3.
Пример 5.1. Задан одномерный массив из n чисел. Определить, есть ли в нём хотя бы один элемент, равный x (значение x вводится). Пусть p — переменная логического типа: «истина», если элемент в массиве найден, и «ложь» — в противном случае. До просмотра элементов p := false. В цикле просматриваем все числа массива и сравниваем их с x. После поиска либо p = true (в массиве есть такой a[i], что a[i] = x), либо весь массив просмотрен и p = false.
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.
Тестирование: для 1 2 3 4 5 и x = 4 — «Элемент найден»; для 1 3 5 7 9 и x = 6 — «Элемент не найден».
Пример 5.2. Часто нужно не только определить, есть ли искомый элемент, но и установить, на каком месте он находится. Индекс найденного элемента храним в переменной k. Если таких элементов несколько, в k будет номер последнего из них; если такого элемента нет, k останется равным 0. Для массива 1 3 3 3 5 и x = 3 программа выведет «Элемент найден на месте 4».
//линейный поиск элемента (пример 5.2)
k := 0;
for var i := 1 to n do
if a[i] = x then
k := i;
if k = 0 then
writeln('Элемент не найден')
else
writeln('Элемент найден на месте ', k);
В этих алгоритмах просматривается весь массив, даже если искомый элемент стоит на первом месте. Для сокращения времени поиска можно останавливаться сразу после того, как элемент найден (пример 5.3). Тогда весь массив просматривается, только если искомый элемент последний или его нет вообще. Цикл заканчивает работу, когда найден искомый элемент либо когда k = n + 1, т. е. элемента, совпадающего с x, не существует.
//линейный поиск элемента (пример 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*. На каждой итерации такого цикла нужно увеличивать k и вычислять логическое выражение. Ускорить поиск можно, упростив выражение: поместим в конец массива дополнительный элемент со значением x. Тогда совпадение с x обязательно произойдёт, и условие k ≤ n можно не проверять. Такой вспомогательный элемент называют «барьером» или «часовым»: он препятствует выходу за пределы массива. В массиве теперь n + 1 элемент, поэтому его размер должен быть хотя бы на 1 больше n.
//линейный поиск с барьером (пример 5.4)
a[n + 1] := x;
k := 1;
while a[k] <> x do
k := k + 1;
if k = n + 1 then
writeln('Элемент не найден')
else
writeln('Элемент найден на месте ', k);
Тестирование: для 1 5 6 7 1 и x = 7 — «Элемент найден на месте 4»; для 1 2 3 4 5 и x = −2 — «Элемент не найден».
Главная мысль: Найден ли элемент, показывает логическая переменная p или индекс k; цикл while позволяет закончить поиск сразу после того, как элемент найден.
3
Нахождение всех элементов, удовлетворяющих условию
Количество найденных элементов считает счётчик, которому до просмотра массива задают начальное значение 0; индексы найденных элементов сохраняют в дополнительном массиве.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Счётчик и индексы найденных элементов
Выберите цель «Все совпадения» и свойство «Кратно d» (пример 5.5): модель проверяет условие a[i] mod d = 0, считает подходящие элементы и показывает их индексы — как массив b в примере 5.6. Введите 6 3 2 4 5 и d = 2: найдено 3 элемента на местах 1, 3, 4.
Если требуется определить количество элементов, удовлетворяющих условию, то определяют отдельную переменную, значение которой увеличивают на 1 каждый раз, когда найден нужный элемент. Такую переменную называют счётчиком. До начала просмотра массива счётчику задают начальное значение, или, другими словами, инициализируют переменную. При подсчёте количества элементов счётчик инициализируется нулём. Для решения такой задачи нужно просмотреть весь массив.
Пример 5.5. Задан одномерный массив из n чисел. Определить количество элементов, кратных x. В цикле просматриваем все числа массива и сравниваем с нулём их остатки от деления на x; если остаток равен нулю, счётчик k увеличиваем на 1.
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('В массиве ', k, ' элемент(-а,-ов), кратный(-х) ', x);
end.
Тестирование: для 1 2 3 4 5 и x = 2 программа выведет «В массиве 2 элемент(-а,-ов), кратный(-х) 2».
Пример 5.6. Чтобы не только посчитать подходящие элементы, но и сохранить их индексы, используют дополнительный массив b. Как только найден нужный элемент, его индекс заносится в b; переменная k хранит номер последнего занятого места в массиве b, вначале k = 0. После завершения работы первые k элементов массива b содержат индексы искомых элементов.
//пример 5.6: a, b: array[1..10] of integer
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('В массиве ', k, ' элемент(-а,-ов), кратный(-х) ', x);
writeln('Местоположение ');
for var i := 1 to k do
write(b[i], ' ');
Тестирование: для 6 3 2 4 5 и x = 2 — «В массиве 3 элемент(-а,-ов), кратный(-х) 2», местоположение 1 3 4.
Главная мысль: Количество найденных элементов считает счётчик, которому до просмотра массива задают начальное значение 0; индексы найденных элементов сохраняют в дополнительном массиве.
4
Решение задач с использованием линейного поиска
Задачи поиска различаются условием отбора: сравнение с числом, кратность, попадание точки в круг, свойство числа или строки; сложное условие удобно проверять отдельной функцией.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Поиск по условию
Выберите свойство: «От L до R включительно» соответствует условию X1 ≤ a[i] ≤ X2, «Больше нуля» — отбору положительных элементов, «Кратно d» — условию a[i] mod d = 0. Составьте свои данные и проверьте, сколько элементов и на каких местах найдено.
Пример 5.7. Известны результаты ЦТ по математике для n человек (получены случайным образом). Определить, есть ли среди них хотя бы один человек с баллом выше x. Просматриваем элементы с начала и останавливаемся, как только элемент найден. В качестве барьера в ячейку n + 1 записываем x + 1 — это число больше x, поэтому цикл обязательно остановится.
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.
Тестирование: для 48 12 96 48 9 95 5 71 77 24 и x = 80 — «Это человек с № 3, его балл - 96».
Пример 5.8. В массивах X и Y (заданы случайным образом, −200 ≤ X[i], Y[i] ≤ 200) хранятся координаты точек плоскости. Определить, каких точек больше — лежащих внутри или снаружи круга радиуса R с центром в начале координат (точки на окружности считаем внутренними). Построить окружность и точки: внутренние — красным цветом, внешние — синим. Если X[i]² + Y[i]² ≤ R², точка лежит внутри, и счётчик k1 увеличиваем на 1, иначе увеличиваем k2. Оси координат пересекаются в точке экрана (200, 200): к абсциссе прибавляют 200, а ординату вычитают из 200, так как ось Y на экране направлена вниз. Затем сравнивают k1 и k2 и выводят «Внутри больше», «Снаружи больше» или «Поровну».
//пример 5.8: подсчет и построение точек
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;
Пример 5.9. На складе хранятся пустые ящики для упаковки товара. Масса одного пакета с конфетами — x кг. Какова суммарная масса пакетов с конфетами, которые можно упаковать в такие ящики, заполнив ящик целиком? Ящик заполняется целиком, если его вместимость кратна x; для таких ящиков увеличиваем счётчик k и прибавляем вместимость к сумме S.
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.
Тестирование: для вместимостей 15 23 64 27 35 10 48 13 и x = 5 — «На складе 3 ящ.», «Суммарная масса 60». Условию задачи удовлетворяют ящики вместимостью 15, 35 и 10: 15 + 35 + 10 = 60.
Пример 5.10. Имеется список мальчиков 10 «В» класса и результаты их бега на 100 м (массивы fam и r). Для сдачи норматива нужно пробежать дистанцию не более чем за 16 с. Вывести фамилии учащихся, которые не выполнили норматив, и их количество: если r[i] > 16, выводим fam[i] и увеличиваем счётчик. Для результатов 13.5, 14.0, 21, 16.1, 15.9 норматив не сдали двое — Сидоров (21) и Королев (16.1).
//пример 5.10: fam — фамилии, r — результаты бега
k := 0;
for var i := 1 to n do
if r[i] > 16 then
begin
k := k + 1;
writeln(fam[i]);
end;
writeln('Не сдали норматив: ', k);
Пример 5.11*. Определить, сколько элементов массива являются числами Смита. Число Смита — составное число, сумма цифр которого равна сумме цифр всех его простых сомножителей. Например, 202 = 2 × 101: 2 + 0 + 2 = 4 и 2 + 1 + 0 + 1 = 4. Функция sum возвращает сумму цифр числа, функция check раскладывает число на простые множители (делит сначала на 2, пока делится, затем на 3, 4, 5 и т. д., пока число не станет равным 1) и возвращает true для чисел Смита. Простое число раскладывается на один множитель — само себя, поэтому для него суммы тоже равны; чтобы оно не попало в ответ, считаем множители (c > 1).
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, c: integer;
begin
s1 := sum(x); s2 := 0; d := 2; c := 0;
//разложение на простые множители
while x > 1 do
begin
while x mod d = 0 do
begin
s2 := s2 + sum(d);
x := x div d;
c := c + 1; //количество простых множителей
end;
d := d + 1;
end;
check := (s1 = s2) and (c > 1); //простое число не подходит
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(a[i], ' ');
end;
writeln;
writeln('Всего - ', k);
end.
Тестирование: для 202 3 323 85 117 — числа Смита 202 и 85, всего 2 (85 = 5 × 17: 8 + 5 = 5 + 1 + 7); для 8 8 8 8 8 — всего 0.
Пример 5.12*. Задан массив из n строк, каждая — предложение из слов, разделённых пробелами. Вывести предложения с нечётным количеством слов. Перед каждым словом, кроме первого, стоит пробел, а слово начинается с символа, который пробелом не является. Добавим пробел перед первым словом — тогда количество слов равно количеству пар символов «пробел и не пробел». При вводе строк после каждого предложения нажимают Enter: компилятор считает ввод строки законченным именно по Enter, а то, как строка выглядит в окне вывода, зависит от его ширины.
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;
//в основной программе:
for var i := 1 to n do
if check(a[i]) mod 2 <> 0 then
begin
inc(k);
writeln(a[i]);
end;
Главная мысль: Задачи поиска различаются условием отбора: сравнение с числом, кратность, попадание точки в круг, свойство числа или строки; сложное условие удобно проверять отдельной функцией.
Интерактивная практика
Исследуйте и примените
Проверьте на модели программы примеров 5.1–5.3: введите данные из таблицы упражнения 1 и сравните ответы при поиске первого и последнего совпадения.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Лаборатория: таблица из упражнения 1
Введите массив и x из строки таблицы, например 2 14 7 20 16 и x = 20. Выберите цель «Первое совпадение» (пример 5.3), затем «Последнее совпадение» (пример 5.2) и выполните все шаги. Подумайте, когда ответы различаются.
Соберём главное
Шесть выводов
01
Алгоритм, при котором для поиска нужного элемента последовательно просматривают все элементы массива в порядке их записи, называется линейным или последовательным поиском.
02
Найден ли элемент, показывает логическая переменная p или индекс k; цикл while позволяет закончить поиск сразу после того, как элемент найден.
03
Количество найденных элементов считает счётчик, которому до просмотра массива задают начальное значение 0; индексы найденных элементов сохраняют в дополнительном массиве.
04
Задачи поиска различаются условием отбора: сравнение с числом, кратность, попадание точки в круг, свойство числа или строки; сложное условие удобно проверять отдельной функцией.
05
Барьер — дополнительный элемент a[n + 1] := x: совпадение обязательно произойдёт, поэтому в условии цикла не нужно проверять выход за пределы массива.
06
Если нужны значения найденных элементов, а в массиве b хранятся их индексы, к элементам обращаются так: a[b[i]].
Самопроверка
Тест: 10 вопросов
Один верный ответ. За ответ — 1 балл. Откройте и проверьте себя.