Задачи поиска

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

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

Предположим, что о расположении данных в таблице нет никаких сведений. Тогда проверка одного элемента не дает никакой информации об остальных. Самый разумный способ поиска в этом случае — последовательный перебор.

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

Пример 1. Пусть дан массив A, состоящий из n элементов: a₁, a₂, a₃, …, a_n. Найти индекс первого элемента массива, значение которого равно нулю, если таковой существует.

Вариант 1.

program MAS2_F7;

var

a:array[1..100] of integer;

i,n,k,p:integer;

Begin

readln(n);

for i:=1 to n do

read(a[i]);

k:=0;

for i:=1 to n do

if (a[i]=0) and (k=0) then begin writeln(i); k:=1 end;

if k=0 then writeln(‘Net takix elementjb’);

End.

Вариант 2.

program MAS2_F7W;

var a:array [1..100] of integer;

i,n:integer;

begin

readln (n);

for i:=1 to n do read (a[i]);

i:=1;

While (i<= n) and (a[i]<>0)do i:=i+1;

if i>n then writeln('NO') else writeln(i);

end.

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

Следует обратить внимание на порядок записи простых условий в составных условиях цикла и утверждения. Здесь предполагается, что второе условие не проверяется, если результат логического выражения ясен после проверки первого условия. В противном случае при k>N возникает отказ из-за выхода индекса за границы массива.

Пример 2. Пусть дан массив A, состоящий из n элементов: a₁, a₂, a₃, …, a_n. Поменять местами первый положительный и последний отрицательный.

program a6;

var

i,n,b,k1,k2:integer;

a:array[1..100]of integer;

begin

readln(n);

for i:=1 to n do read(a[i]);

i:=1;

While (i<=n) and ( a[i] <0) do i:=i+1;

if i>n then writeln('NO')

else begin

k1:=i; i:=n;

While (i>=1) and ( a[i]>0) do i:=i-1;

if i<1 then writeln('NO')

else begin

k2:=I;

b:=a[k1];

a[k1]:= a[k2];

a[k2]:=b;

for i:=1 to n do write(a[i],’ ‘);

end;

end;

end.

Пример 3. Пусть дан массив A, состоящий из n элементов: a₁, a₂, a₃, …, a_n.Найти максимальный элемент и его номер среди четных элементов одномерного массива.

program a3;

var

i,n,m,k,z:integer;

a:array[1..100]of integer;

begin

readln(n);

for i:=1 to n do read(a[i]);

i:=1;

While (i<=n) and ( a[i] mod 2<>0) do i:=i+1;

if i>n then writeln('NO')

else begin

m:=a[i]; k:=i; z:=i;

for i:=z+1 to n do

if ( a[i] mod 2=0) and(a[i]>m) then

Begin

m:=a[i]; k:=i;

end;

writeln(m,’ ‘,k);

end;

end.