Программирование на языке Turbo Pascal
       

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


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

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

Алгоритм:

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 {внутренний цикл, изменяется номер строки}

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

  • Случайными числами в заданном промежутке (n,m) с заданным интервалом k


    • for i:=1 to 10 do

    for j:=1 to 10 do

    a[i,j]:=random((n-m+1)/k)*k+n; {n,m k должны быть задано заранее}

    • Все строки заполнить одинаково, натуральными числами начиная с 1.


      • for i:=1 to 10 do

      for j:=1 to 10 do

      a[i,j]:=j;

      • Все графы заполнить одинаково, натуральными числами начиная с 1.


        • for j:=1 to 10 do

         for i:=1 to 10 do

        a[i,j]:=1;

        • По строкам, змейкой. Например, первая строка - 1 2 3 4 5, вторая -10 9 8 7 6, третья - 11

          12 13 14 15 и т.д.


          • K:=1

          for i:=1 to 10 do            begin

          for j:=1 to 10 do begin

          a[i,j]:=k; k:=k+1; end;

          i:=i+1;

          for j:=10 downto 1 do begin

          a[i,j]:=k; k:=k+1;          end;

                                           end;

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

          • Найти максимальный (минимальный) элемент


            • max:=a[1];

            n:=1;m:=1;

            for i:=1 to 10 do

            for j:=1 to 10 do

            if a[I,j]>max then begin  max:=a[I,j]; n:=i;m:=j;  end;

            • Найти максимум главной диагонали




              • max:=a[1];

              n:=1;

              for i:=1 to 10 do

              if a[i,i]>max then begin  max:= a[i,i];n:=i;  end;

              • Найти минимум побочной диагонали (размерность массива 10Х 10)


                • min:=a[1];

                n:=1;

                for i:=1 to 10 do

                if a[i,11-i]>min then begin  min:= a[i,11-i];n:=i;  end;

                 

                Преобразование массивов

                Заменить все элементы, отвечающие данному условию (>a), на заданную величину (c).

                for i:=1 to 10 do

                for j:=1 to 10 do

                if a[i,j]>a then begin  a[I,j]:=c;  end;

                • Найти сумму каждой строки матрицы и записать в отдельный одномерный массив.


                  • program mas4;

                   uses crt;

                   const n=4; m=4;

                   type t=array[1..n,1..m] of integer; w=array[1..4] of integer;

                   var a:t;i,j,b,s,d:integer; c:w;

                  begin

                   clrscr;

                   for i:=1 to n do

                       begin

                             writeln ('Введите строку элементов матрицы (4 элемента)');

                                   for j:=1 to m do  read(a[i,j]);

                               writeln;

                       end;

                   for i:=1 to n do

                       begin   for j:=1 to m do  begin  textcolor (14);  write(a[i,j]:3); end;

                   writeln;

                       end;

                   writeln; {Расчёт суммы}

                   for i:=1 to n do

                       begin    s:=0;    for j:=1 to m do

                                                     begin   s:=s+ a[i,j];     end;

                          c[i]:=s;

                          textcolor (10);

                          write(c[i]:6);

                       end;

                  repeat until keypressed;

                  end.

                  • Выполнить транспонирование матрицы. Транспонированная матрица это матрица, получающаяся из данной (прямоугольной или квадратной) матрицы после замены строк соответствующими столбцами.


                    • program mas2;

                     uses crt;

                     const n=8; m=8;

                     type t=array[1..n,1..m] of integer;

                     var a:t;

                         i,j:integer;

                    begin

                     clrscr;

                     textcolor (9);

                     for i:=1 to n do     begin

                      for j:=1 to m do              begin    a[i,j]:=random (10);    write (a[i,j]:3);   end;

                                                             writeln;

                                                  end;

                     writeln;

                     textcolor (14);

                     for i:=1 to n do  begin

                      for j:=1 to m do       begin    write (a[j,i]:3);    end;

                                                      writeln;

                                              end;

                    repeat until keypressed;  end.



                    • Рисование многоугольников  Двумерные массивы в графике.


                      • ²      Процедура drawpoly (<число вершин> + 1, <двумерный массив координат вершин>) прямое назначение процедуры – вычерчивание ломаной!!! Поэтому отправную вершину надо ещё раз указать в последней строке массива.

                      ²      Процедура fillpoly позволяет рисовать закрашенные многоугольники.

                      program graphsb;

                      uses graph, crt;

                       const t:array [1..5, 1..2] {Массив с координатами вершин пятиугольника}

                                    of integer = ((50,50),(125,25),(200,50),(150,150),(50,200));

                                f:array [1..4, 1..2] {Массив с координатами вершин треугольника}

                                    of integer=((250,50),(350,25),(400,150),(250,50));

                       var gd,gm,c:integer;

                      begin

                       gd:=detect;

                       initgraph (gd,gm,'');

                       setcolor (14); setbkcolor (1);

                       setfillstyle (8,10); {Тип заливки}

                       fillpoly (5,t); {Закрашенный пятиугольник}

                       drawpoly (4,f); {Контурный треугольник}

                      repeat until keypressed;

                      end.

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

                      • Дана матрица b, состоящая из целых. Получить матрицу r, значения которой равны удвоенным значениям матрицы b


                        • program mas5;

                         uses crt;

                         const n=4; m=4;

                         type t=array[1..n,1..m] of integer;

                         var r,b:t;i,j:integer;

                        begin

                         clrscr;

                         textcolor (15);

                         for i:=1 to n do

                             begin

                             writeln ('Введите строку матрицы (4 элемента)');

                             for j:=1 to m do

                                 begin

                                 read (b[i,j]);

                                 end;  writeln;

                             end;

                         for i:=1 to n do

                         for j:=1 to m do

                         r[i,j]:=b[i,j]*2;

                         writeln;

                         for i:=1 to n do

                             begin

                             for j:=1 to m do

                                 begin

                                 textcolor (10);

                                 write (r[i,j]:3);

                                 end;

                             writeln;

                             end;

                        repeat until keypressed;

                        end.

                        • Одномерный массив из 10 элементов заполнить произвольными числами от 0 до 9 и выдать его на экран.


                          • program pt1;

                          uses crt;

                          type t=array[1..10] of integer;

                          var a:t;i:integer;

                          begin

                          clrscr;

                          randomize;

                          for i:=1 to 10 do

                          begin

                          a[i]:=trunc(random(10));



                          write(a[i]:4);

                          end;

                               readln;

                               end._

                          • Двумерный массив размерностью 4 х 5 заполнить целыми двузначными числами и выдать его на экран.


                          program pt2;

                          uses crt;

                          type t=array[1..4,1..5] of integer;

                          var a:t;i,j:integer;

                          begin

                          clrscr;

                          randomize;

                          for i:=1 to 4 do

                          		 begin

                          for j:=1 to 5 do

                          begin

                          a[i,j]:=trunc(random(90))+10;

                          write(a[i,j]:4);

                          end;

                          writeln;

                          end;

                               readln;

                               end._
                          • Двумерный массив размерностью 4 х 5 заполнить целыми числами в интервале от –10 до 20 с шагом 5 и выдать его на экран.


                          program pt3;

                          uses crt;

                          type t=array[1..4,1..5] of integer;

                          var a:t;i,j:integer;

                          begin

                          clrscr;

                          randomize;

                          for i:=1 to 4 do

                          		 begin

                          for j:=1 to 5 do

                          begin

                          a[i,j]:=trunc((random(7))*5)-10;

                          write(a[i,j]:4);

                          end;

                          writeln;

                          end;

                               readln;

                               end._
                          • Двумерный массив размерностью 4 х 5 заполнить целыми числами в интервале от –10 до 20 с шагом 5 и выдать его на экран. Найти максимальный элемент массива и его координаты.


                          program pt4;

                          uses crt;

                          type t=array[1..4,1..5] of integer;

                          var a:t;i,j,j1,i1,ms:integer;

                          begin

                          clrscr;

                          randomize;

                          ms:=-10;

                          for i:=1 to 4 do

                          begin

                          		 for j:=1 to 5 do

                          begin

                          a[i,j]:=trunc((random(7))*5)-10;

                          write(a[i,j]:4);

                          if ms<a[i,j] then begin; ms:=a[i,j]; i1:=i; j1:=j; end;

                          end;

                          writeln;

                          end;

                          writeln('MS=',ms:4,i1:4,j1:4);

                               readln;

                               end._
                          • Заполнить одномерный массив размерностью М (М ввести с клавиатуры) целыми числами от –30  до 39 и выдать на экран. Все отрицательные элементы массива заменить на 0 и выдать массив на экран.  Поменять местами 2-й и предпоследний элемент массива, выдать массив на экран.


                          program pt5;

                          uses crt;

                          const n=100;

                          type t=array[1..n] of integer;

                          var a:t;i,r,m:integer;

                          begin

                          clrscr;

                          randomize;

                          writeln('vvedite N');

                          readln(m);

                          for i:=1 to m do

                          begin

                          a[i]:=trunc(random(70))-30;

                          		 write(a[i]:4);

                          if a[i]<0 then a[i]:=0;

                          end;

                          writeln;

                          for i:=1 to m do

                          begin

                          write(a[i]:4);

                          end;

                          r:=a[2]; a[2]:=a[m-1];a[m-1]:=r;

                          writeln;

                          for i:=1 to m do

                          write(a[i]:4);

                           readln;  end._
                          <


                          • Заполнить одномерный массив размерностью М (М ввести с клавиатуры) целыми числами от –30  до 39 и выдать на экран. Отсортировать массив по убыванию и  выдать  на экран.


                          program pt6;

                          uses crt;

                          const n=100;

                          type t=array[1..n] of integer;

                          var a:t;i,j,k,r,m:integer;

                          begin

                          clrscr;

                          randomize;

                          writeln('vvedite N');

                          readln(m);

                          for i:=1 to m do

                          begin

                          a[i]:=trunc(random(70))-30;

                          write(a[i]:4);

                          		 end;

                          writeln;

                          for i:=1 to m-1 do

                          begin

                          for j:=i to m do

                          begin

                          if a[i]<a[j] then begin r:=a[i]; a[i]:=a[j];a[j]:=r; end;

                          end;

                          end;

                          writeln;

                          for k:=1 to m do

                          write(a[k]:4);

                          readln;   end._

                          Содержание раздела