Мониторинг обменных курсов валют
18c0693f

Поиск элемента в упорядоченном массиве


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

Поиск ведется методом дихотомии.

Алгоритм:

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

2.      Вводится искомая величина (m) и сравнивается со средним элементом. Если a[i]>m, то заданный элемент – в левой половине и поэтому индекс k правой границы устанавливается =i, иначе искомый элемент в правой половине и сдвигается начальный индекс p и p:=i.

3.      Процесс повторяется пока (k-p)<=1, т.е. пока p и k не сдвинутся вплотную. При этом величина искомого индекса =p.

Примеры программ:

Задача.

Из массива a составить массив b, который содержит только чётные элементы массива a.

program massiv1;

 uses crt;

 type mas=array[1..5] of integer;

 var a,b:mas;       i,k,nmin:integer;     min:integer;

begin

 clrscr;

 textcolor (15);

 for i:=1 to 5 do {Блок заполнения массива}

  begin

   writeln ('Введите значение элемента');

   readln (a[i]);

  end;

 k:=0;

 for i:=1 to 5 do   if a[i] mod 2=0 then  {Поиск чётного элемента}

                              begin  k:=k+1;   b[k]:=a[i]; end; {Формирование нового массива} 

 if k=0 then

        begin textcolor (12);  writeln ('Чётных элементов нет.');  writeln ('Формирование нового массива невозможно!');

        end

            else   begin    nmin:=1; min:=b[1]; {Поиск минимального в новом массиве}  

                     for k:=1 to k do  if b[k]<min then

                                                  begin   min:=b[k];   nmin:=k;  end;

  for i:=1 to 5 do {Вывод элементов массива а}

   begin   textcolor (14);   writeln ('Элемент ',i, ' массива a ',a[i]);

   end;

   for i:=1 to k do {Вывод элементов массива b}

   begin


    textcolor (9);    writeln ('Элемент ',i, ' массива b ',b[i]);

   end;

    textcolor (10);

    writeln (' Минимальный элемент среди чётных элементов массива=',min);

    writeln ('Номер этого элемента=',nmin);

 end;

repeat until keypressed; end.

Базовые алгоритмы работы с двухмерными массивами

Перемещение по массиву:

Про матрицу, имеющую m строк и n столбцов, говорят, что она имеет размер m*n

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

Перемещение по строке:

for i:=1 to m do {внешний цикл, изменяется номер строки}

…

for j:=1 to n do {внутренний цикл, изменяется номер столбца}

Перемещение по столбцу:

for j:=1 to n do {внешний цикл, изменяется номер столбца}

…

for i:=1 to m do {внутренний цикл, изменяется номер строки}

Заполнение массива