Библиотека программиста

Все, что необходимо начинающему и опытному программисту

Поиск в массиве

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

Рис. 8.7. Блок-схема алгоритма вычисления количества четных элементов массива

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

На первый взгляд задача кажется весьма простой: достаточно перебрать все элементы и проверить каждый на отрицательность. Это правильно. Но что же делать дальше? И как определить, что в массиве вообще нет отрицательных элементов? А если их несколько?

Данная задача может быть решена несколькими способами. Первый — самый простой — использовать флажок.

Пример 8.7.
Определение наличия в массиве отрицательного элемента с использованием флажка

program Searchl;
const N=10;
type mas=array [1. .N] of integer;
var a:mas;
i: integer;
fl:boolean; { Флажок указывает на успешность поиска }
begin
{ Заполним массив случайными числами }
randomize;
for i:=1 to N do
begin
a[i]:=-2+random(20);
write(a[i]:4)
end;
writeln;
{ Начало блока поиска }
{ Первый вариант поиска отрицательного элемента - использование флажка }
fl:=false; { Изначально флажок = false, так как мы еще ничего не нашли }
for i:=1 to N do
if a[i]<0 then { Проверяем каждый элемент на отрицательность }
fl:=true; { Если нашли отрицательный, устанавливаем флажок в состояние "истина'' }
if fl then "
writeln('В массиве есть отрицательный элемент')
else
writeln('В массиве нет отрицательных элементов');
{ Конец блока поиска }
readln
end.

Определение наличия в массиве отрицательных элементов путем вычисления их количества

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

Пример 8.8.
Определение наличия в массиве отрицательных элементов путем подсчета количества таких элементов

program Search2;
const N=10;
type mas=array [1..N] of integer;
var a:mas;
i:integer;
f1:integer; { Это уже не флажок, а счетчик количества найденных отрицательных элементов }
begin
{ Заполним массив случайными числами }
randomize;
for i:=l to N do
begin
a[i]:=-2+random(20);
write(a[i]:4)
end;
writeln;
{ Начало блока поиска }
{ Второй вариант поиска отрицательного элемента - количество отрицательных элементов }
f1:=0; { Изначально счетчик = 0, так как мы еще ничего не нашли }
for i:=1 to N do
if a[i]<0 then { Проверяем каждый элемент на отрицательность }
inc(fl); { Если нашли отрицательный - увеличиваем счетчик на единицу }
writeln('Количество отрицательных элементов=',fl);
if fl>0 then
writeln('B массиве есть отрицательный элемент')
е1se
writeln('B массиве нет отрицательных элементов');
{ Конец блока поиска }
readln
end.

Нахождение номера отрицательного элемента массива

Мы только что рассмотрели перебор элементов массива в поисках элементов с какими-то свойствами (в нашем случае отрицательных). Можно также использовать этот метод для поиска номера отрицательного элемента.

Пример 8.9.
Определение наличия в массиве отрицательного элемента путем вычисления его номера

program Search3;
const N=10;
type mas=array [1..N] of integer;
var a:mas;
i:integer;
fl:integer; { Индекс найденного отрицательного элемента }
begin
{ Заполним массив случайными числами }
randomize;
for i:=1 to N do
begin a[i]:=-2+random(20);
write(a[i]:4)
end;
writein;
{Начало блока поиска }
{ Третий вариант поиска отрицательного элемента - нахождение индекса отрицательного элемента }
fl: =0; { Изначально флажок (индекс) = 0, так как мы еще ничего не нашли }
for i :=1 to N do
if a[i]<0 then { Проверяем каждый элемент на отрицательность }
fl:=i; { Если нашли отрицательный, запоминаем его номер }
{ Теперь по значению переменной fl можно определить, был ли в массиве хоть один отрицательный элемент! Если fl остался равен нулю, значит проверка на отрицательность ни разу не выполнилась .}
if fl>0 then
writeln('Индекс отрицательного элемента=',fl)
else
writeln('B массиве нет отрицательных элементов');
{ Конец блока поиска }
readln
end.

 

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

А как нам найти первый отрицательный элемент?
Один из методов (на данный момент самый легкий) — исправить цикл так, чтобы он перебирал элементы с конца:

for k : = N downto 1 do...

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

Эти рассуждения подталкивают нас заменить цикл for, который перебирает все элементы, циклом while, который остановится в нужный нам момент:

k := 1:
while а[k]>= 0 do { Перебираем все не подходящие нам (то есть неотрицательные) элементы }
inc(k); { Берем номер следующего элемента }

Лирическое отступление.
В только что приведенном примере мы использовали оператор inc, который раньше не упоминали. Он увеличивает значение указанной переменной на единицу. То есть оператор inc(k) аналогичен оператору k := k + 1. По аналогии с inc, в Паскале имеется еще оператор dec. Он уменьшает значение указанной переменной на единицу.
Мы не привели эти операторы ранее, чтобы преждевременно не забивать ваши головы излишней информацией. Вы можете ими не пользоваться и продолжать писать k := k + 1 и k := k -1, как и ранее, вместо inc(k) и dec(k).

Рассмотренный метод поиска первого отрицательного элемента обладает одним серьезным недостатком: он не останавливается, если в массиве вообще нет отрицательных элементов.

Перебрав все элементы массива, цикл продолжит искать отрицательные элементы дальше. Это приведет или к зависанию компьютера, или к аварийному завершению программы в зависимости от настроек. Исправим ошибку. Для этого добавим еще одно условие окончания поиска — «если мы перебрали все элементы».

Пример 8.10.
Определение наличия в массиве отрицательного элемента и вычисление его номера (если такой есть)

program Search4;
const N=10:
type mas=array [1..N] of integer;
var а: mas;
i:integer; { Здесь нам не нужен флажок - счетчик цикла будет нашим флажком }
begin
{ Заполним массив случайными числами}
randomize;
for i:=1 to N do
begin a[i]:=-2+random(20);
write(a[i]:4)
end;
writeln;
{ Начало блока поиска }
{ Четвертый вариант поиска номера первого отрицательного элемента }
i:=1; { Так как используем цикл while вместо for, приходится самим заботиться, о счетчике цикла }
while (a[i]>=0) and (i<=N) do { Перебираем все не подходящие нам (неотрицательные) элементы. Кроме того, проверяем выход за границы массива }
inc(i); { Берем номер следующего элемента }
{ Цикл закончен. Проверим, по какому из двух условий это произошло }
if i>N then..........
{ Если в результате поиска вышли за границы массива - значит, отрицательного элемента нет }
writeln('Индекс отрицательного элементами')
else
writeln('B массиве нет отрицательных элементов');
{ Конец блока поиска }
readln
end.

 

Задание 8.8.
Определить, есть ли S массиве положительные Четные элементы, и если есть, вывести номер последнего из них.

<< Назад         В начало         Далее >>

Библиотека программиста. 2009.
Администратор: admin@programmer-lib.ru