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

1.

ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК В
МАССИВАХ
Урок 1
Учитель: Н.В. Фоменко

2.

ЗАДАЧИ ПОИСКА
Поиск максимального (минимального)
элемента массива
Поиск индекса максимального (минимального)
элемента массива
Поиск элемента массива, значение которого
равно заданному
Поиск индекса элемента, значение которого
равно заданному
Для решения таких задач в программе необходимо
организовать последовательный просмотр элементов
массива и сравнение значения очередного
просматриваемого элемента с неким образцом

3.

ПОИСК НАГЛЯДНО
Представим себе одномерный массив в виде
стопки карточек, на каждой из которых написано
число. Тогда идея поиска наибольшего элемента
массива может быть представлена следующим
образом:
1) Возьмём верхнюю карточку (первый элемент массива), запомним
имеющееся на карточке число (запишем его мелом на доске) как
наибольшее из просмотренных; уберём карточку в сторону;
2) Возьмём следующую карточку; сравним числа, записанные на
карточке и на доске; если число на карточке больше, то сотрём число,
записанное на доске, и запишем там то же число, что и на карточке;
если же новое число не больше, то на доске оставим имеющуюся
запись; уберём карточку в сторону;
3) Повторим действия, описанные в п. 2, для всех оставшихся карточек
в стопке.
4) В итоге на доске будет записано самое большое значение элемента
просмотренного массива.

4.

РЕШЕНИЕ ЗАДАЧИ НА ЯЗЫКЕ PASCAL
const n=20;
var a: array[1..n] of integer; i, max :integer;
begin
randomize;
for i:=1 to n do
begin
Внимание! За максимум берется
a[i]:=random(100);
первый элемент массива
write(a[i]:4)
end;
writeln;
max:=a[1];
for i:=2 to n do
if a[i]>max then max:=a[i];
writeln (max);
end.

5.

НЕСКОЛЬКО ЭЛЕМЕНТОВ С
МАКСИМАЛЬНЫМ ЗНАЧЕНИЕМ
Если в массиве несколько элементов, значения
которых равны максимальному, то программа
найдет первый из них
ЧТО НАДО СДЕЛАТЬ, ЧТОБЫ ПРОГРАММА
НАШЛА ПОСЛЕДНИЙ ИЗ МАКСИМАЛЬНЫХ
ЭЛЕМЕНТОВ?
max:=a[n];
for i:=n-1 downto 1 do
if a[i]>max then max:=a[i];

6.

ЧТО НАДО ИЗМЕНИТЬ, ЧТОБЫ НАЙТИ НОМЕР
МАКСИМАЛЬНОГО ЭЛЕМЕНТА?
const n=20;
max :integer;
var a: array[1..n] of integer; i, imax
begin
randomize;
for i:=1 to n do
Можно находить одновременно и то и
begin
другое, можно только imax, ведь по
a[i]:=random(100);
нему легко найти и сам максимальный
элемент a[imax]
write(a[i]:4)
end;
writeln;
imax:=1; ;
max:=a[1]
for i:=2 to n do
imax:=i;
max
if a[i]> a[imax]
then max:=i;
imax );
writeln ( max
end.

7.

ЧТО НАДО ИЗМЕНИТЬ, ЧТОБЫ НАЙТИ
МИНИМАЛЬНЫЙ ЭЛЕМЕНТ?
const n=20;
max :integer;
var a: array[1..n] of integer; i, min
begin
randomize;
for i:=1 to n do
begin
a[i]:=random(100);
write(a[i]:4)
end;
writeln;
min
max :=a[1];
for i:=2 to n do
min :=a[i];
if a[i] >max
< min then max
min );
writeln ( max
end.

8.

ЗАДАЧА НАХОЖДЕНИЯ ЭЛЕМЕНТА МАССИВА,
ЗНАЧЕНИЕ КОТОРОГО РАВНО ЗАДАННОМУ
Имеет 2 решения:
k – индекс элемента, равного заданному
Сообщение о том, что такого элемента в массиве
нет
writeln(‘введите искомое число’);
readln(x); k:=0;
for i:=1 to n do
if a[i]=x then k:=i;
if k>0 then writeln (‘k= ‘, k)
else writeln(‘ такого числа в массиве нет’);
Индекс какого элемента будет найден, если в массиве
окажется несколько элементов, значение которых равны искомому?

9.

ПОИСК НОМЕРА ПЕРВОГО ЭЛЕМЕНТА,
РАВНОГО ЗАДАННОМУ
Во многих случаях требуется найти первый из элементов,
имеющих соответствующее значение, после чего дальнейший
поиск прекратить
for i:=1 to n do
if a[i]=x then
begin
k:=i; break
end;