Урок 22

---

Алгоритмизация и программирование

Ключевые слова:

• последовательный поиск

До сих пор мы работали с простыми типами данных. При решении практических задач данные часто объединяются в различные струк­туры данных, например в массивы. В языках программирования массивы используются для реализации таких структур данных, как последовательности (одномерные массивы) и таблицы (двумерные массивы).

---

Упорядоченное множество однотипных переменных (элементов масси­ва), которым можно присвоить общее имя, различающихся номерами (индексами), называют массивом.

---

Мы будем рассматривать одномерные массивы. Решение разнообразных задач, связанных с обработкой массивов, базируется на использовании таких типовых алгоритмов, как:

• суммирование значений элементов массива;

• поиск элемента с заданными свойствами;

• сортировка массива.​

 

2.2.5. Последовательный поиск в массиве

В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.

Можно выделить следующие типовые задачи поиска:

1. найти наибольший (наименьший) элемент массива;
2. найти элемент массива, значение которого равно заданному значению.

Для решения таких задач в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.

Рассмотрим подробно решение задач первого типа: нахождение наибольшего (наименьшего) элемента.

Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:

1) возьмём верхнюю карточку (первый элемент массива), запомним имеющееся на карточке число

 (запишем его мелом на доске) как наибольшее из просмотренных; уберём карточку в сторону;

2)возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, и запишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;

3)повторим действия, описанные в п. 2, для всех оставшихся карточек в стопке.

В итоге на доске будет записано самое большое значение элемента просмотренного массива.

Так как доступ к значению элемента массива осуществляется по его индексу, то при организации поиска наибольшего элемента в одномерном массиве можно искать его индекс. Обозначим искомый индекс imax. Тогда описанный выше алгоритм в сформированном нами массиве а на языке Паскаль можно записать так:

program n_4;	Заголовок программы
var
i, imax: integer;     a: array [1..10] of integer;	Блок описания переменных
begin	Программный блок
randomize;
for i:= 1 to 10 do
begin
a[i]:=random(100);	Заполнение и вывод массива
writeln (‘a[‘, I ,’]=’, a[i])
end;
imax:=1;	Поиск наибольшего элемента массива
for i:=2 to 10 do
if a[i]> a[imax] then imax:=i; writeln (‘Наибольший элемент массива’, a[imax])	Вывод результата
end.

Если в массиве несколько элементов, значения которых равны максимальному значению, то данная программа найдёт первый из них (первое вхождение). Подумайте, что следует изменить в программе, чтобы в ней находился последний из максимальных элементов. Как следует преобразовать программу, чтобы с её помощью можно было найти минимальный элемент массива?

Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:

• п — индекс элемента массива такой, что а[п] = х, где х — заданное число;
• сообщение о том, что искомого элемента в массиве не обнаружено.Программа поиска в сформированном нами массиве а значения,

равного х, может выглядеть так:

program n 5;	Заголовок программы
var	Блок описания переменных
i, n, x: integer;
a: array [1..10] of integer;
begin
randomize;	Программный блок
a[i]:=random(100);	Заполнение и вывод массива
writeln (‘a[‘, i, ‘]=’, a[i]);
writeln (‘x =’);
reading (x);	Ввод значения x
n:=0;
for i:=1 to 10 do
if a[i]=x then n:=i;	Поиск в массиве элемента, равного x
if n=0
then  writeln (‘Элемента со значением, равным заданному, в массиве нет')   else writeln ('Индекс элемента, равного заданному, ‘, n) end.	Вывод результата

В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдёт последний из них.

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

i:=0;

repeat

   i:=i+1;

until  (a[i]=x)  or  (i=10);

if a[i]=x then write(i)  else write('Нет')

Здесь выполнение алгоритма будет прервано в одном из двух случаев: 1) в массиве найден первый из элементов, равный заданному; 2) все элементы массива просмотрены.

Запишите полный текст программы и выполните её на компьютере.

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

Определите, количество каких элементов подсчитывается в следующем фрагменте программы.

к:=0;

for   i:=l   to   10  do

   if  a[i]>50   then   k:=k+l;

write(‘k=’, k)

Если требуется определить сумму значений элементов, то вводят переменную, к значению которой прибавляют значение найденного элемента массива.

Определите, какому условию удовлетворяют элементы массива, значе­ния которых суммируются в следующем фрагменте программы.

s:=0;

for  i:=l  to  10  do

   if   (a[i]>50)   and   (a[i]<60)  then  s:=s+a[i];

write('s⁼',   s)

Запишите полные тексты двух последних программ и выполните их на компьютере.

---

Вопросы и задания

1.Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику.Какими слайдами вы могли бы дополнить презентацию?

2.Что необходимо сделать для решения типовых задач?

3.Каким образом может быть представлен поиск наибольшего массива?

4.В каких случаях будет прервано выполнение алгоритма?

---

Самое главное

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