Некоторые  алгоритмы


обработки массивов

1  Суммирование двух массивов одинакового размера
2  Суммирование  элементов массива
3  Определение числа элементов массива, удовлетворяющих  заданному условию
4 Суммирование  элементов  массива, удовлетворяющих  заданному  условию
5  Инвертирование массива
6 Формирование массива из элементов другого массива, удовлетворяющих  заданному условию
7 Поиск  максимального  (минимального)  элемента в массиве с запоминанием  его  положения  в  массиве
8  Поиск  заданного элемента в  массиве
9  Циклический  сдвиг  элементов  массива
10  Упорядочение Массива
1  Суммирование двух массивов одинакового размера
Задано
:  массивы   A =(a1,a2,...,an) ,    B =(b1,b2,...,bn).

Сформировать: массив   C =(c1,c2,...,cn) , где Сi = Ai+Bi; i=1,2,...,n.

Задача сводится  к  организации цикла по i и вычислению Ci=Ai+Bi при каждом значении  i  от 1  до n.

Исходные данные:


N- размер массива; 

A, B - массивы слагаемые размером N;

Результат:   массив  С -  размером N;

Вспомогательные  переменные:  I - индекс - управляющая переменная цикла.

       

Procedure SUM_MAS (n : integer; A,B :mas; var C : mas);

{ где  mas  должен быть описан в главной программе в разделе описания типов , например так :

        type mas = array[1..100 ] of  real ;

тогда это будет процедура для суммирования двух одномерных массивов размером не более 100 элементов  }

          begin

                  for i := 1 to n do C[i] := A[i]+B[i];

          end;
2  Суммирование  элементов массива
Задано:  массив P = (P1,P2,...,Pn) .

Определить:  сумму элементов массива.

Исходные данные: 


N - размер массива; 

P - массив  размером N;

Результат:   S - сумма элементов;

Вспомогательная переменная: I - индекс - управляющая переменная цикла.

       

Procedure SUMMA (n : integer; A :mas; var S : real );

{ процедура для суммирования элементов одномерного массива }

        begin    S:=0; { обнуление переменной под сумму }

               for i := 1 to n do   S := S+P[i]

        end;
3  Определение числа элементов массива, удовлетворяющих  заданному условию
Задано:  массив  P = (P1,P2,...,Pn); T -  заданное число.

Определить: сколько элементов удовлетворяет заданному условию, например     Pi > T .

Исходные данные:


N - размер массива; 

P - массив  размером N;

T - заданное значение, с которым сравниваются элементы массива.

Результат:  K - число элементов массива P, удовлетворяющих условию.

Вспомогательная переменная:  I- индекс - управляющая переменная цикла.
 Procedure USLOVIE ( n : integer; P :mas; T: real; var K : integer);

{процедура  определения числа элементов, удовлетворяющих условию}

        begin

            k := 0;  { обнуление переменной под счетчик чисел }

              for  i := 1  to  n  do  if  P[ i ] > T  then  k := k+1

        end;
4 Суммирование  элементов  массива, удовлетворяющих  заданному  условию
Задано:  массив  P = (P1,P2,...,Pn); T -  заданное число.

Определить: сумму элементов массива  P, удовлетворяющих заданному условию, например  Pi > T .

Исходные данные:  


N - размер массива; 

P - массив  размером N;

T - заданное значение, с которым сравниваются элементы массива;

Результат:  S - сумма элементов массива P, удовлетворяющих  условию.

Вспомогательная переменная :  I - индекс - управляющая переменная цикла.
 Procedure SUM_USLOV ( n : integer; P :mas; T: real; var S : real);

{процедура определения суммы элементов, удовлетворяющих  условию}

        begin        S := 0;  {обнуление переменной под сумму  элементов}

              for  i := 1  to  n  do  if  P [ i ] > T  then  S := S+1

        end;
5  Инвертирование массива
Задано: массив C=(c1,c2,...,cn).

Требуется: изменить порядок следования элементов массива C на обратный, используя одну вспомогательную переменную.

Исходные данные:


N - размер массива;

C - массив  размером N;

Результат:


C - инвертированный  массив;

Вспомогательные переменные:

I -индекс, управляющая переменная цикла; 

M=n/2 - вычисляется до входа в цикл для уменьшения объема вычислений; P - используется при перестановке двух элементов массива.
Procedure INVER_MAS ( n : integer; C :mas; var C : mas);

Var   m :  integer;   p   : real;  { локальные переменные }

        begin  m := n div 2 ;  {  целочисленное деление }

             for i := 1 to  m do

                begin  p := C[ i ];  C[i] := C[N-i+1]; C[N-i+1] := p  end;

        end;
6 Формирование массива из элементов другого массива, удовлетворяющих  заданному условию
Задано: массив A=(a1,a2,...,an), T - заданное число.

Сформировать: массив B=(b1,b2,...,bn), состоящий из элементов массива, удовлетворяющих условию Ai>T.

Заметим, т .к. индексы элементов массивов A и B не совпадают (не все элементы массива Ai>T), то для обозначения индексов массива B  должна быть предусмотрена другая переменная.

Исходные данные: 


N - размер массива;

A - массив размером N; 

T - заданное значение;

Результат:     


B - массив размером не больше N;

Y - число элементов массива  B;

Вспомогательная переменная: I - индекс - управляющая переменная цикла.
        Procedure MAS_NEW (n:integer;T:real;A:mas;var B: mas; var Y: byte);

{ где  mas  должен быть описан в главной программе в разделе описания типов , например так :

        type mas = array[1..100 ] of  real ;

тогда это будет процедура для суммирования двух одномерных массивов размером не более 100 элементов  }

{ процедура включения в новый массив  элементов, удовлетворяющих условию }

        begin   Y := 0; { обнуление ячейки под счетчик элементов массива В }

             for i := 1 to n do

               If  A[ i ] > T then  begin Y := Y+1; B[ Y ] := A[ i ]  end;

        end;
7 Поиск  максимального  (минимального)  элемента в массиве с запоминанием  его  положения  в  массиве
 Задано
:  массив  A=(a1,a2,...,an).

 Найти:  max (min)  элемент  массива  A  и  его индекс.

 Исходные данные: 

N - размер массива;

A - массив размером  N;

Результат:

A_max  максимальный  элемент  массива A;

K -  его индекс.

Вспомогательная переменная: I - индекс управляющая переменная цикла.
Procedure MAX_MAS1(n:integer; A :mas; var A_max :real; var K byte);

{ процедура поиска  максимального элемента массива и его номера }

        begin    A_max := A[1]; K := 1;

           for i := 2 to n do

              If  A_max<A[i] then  begin K := i; A_max := A[i]  end;

        end;
Примечание:  Если в массиве несколько max элементов (имеют одно и то же значение), то  в  K  будет запоминаться первый из них, а чтобы запоминался индекс последнего нужно заменить условие  на A_max<=A(I). Поиск минимального элемента аналогичная процедура.
8  Поиск  заданного элемента в  массиве
Задано: массив P=(p1,p2,...pn); элемент L (массив может быть как числовым так и символьным.

Найти: Есть ли в массиве P, элемент равный L. Результат присвоить символьной переменной.

Исходные данные:

N - размер массива;

P - массив размером N;

L - значение, которое ищется в массиве;

Результат: R - имеет значение "элемент, равный L есть" или "элемента, равного  L  нет" в  зависимости от результата поиска;

Вспомогательная переменная: I - индекс управляющая переменная цикла.
Procedure POISK ( n:integer; P :mas; L :integer; var R :string);

{ процедура поиска заданного значения среди элементов массива }

          Label  m ;

           begin

              R :=" элемента равного L в массиве нет " ;

                     for i := 1 to n do

                       If  P[i] = L  then

                         begin  R := " элемент , равный  L  есть  ";  Goto m   end;

         m:     end;
Примечание. Если элемент, равный L, найден, то чтобы завершить цикл используется оператор безусловного перехода Goto m , где локальная метка  m  обязательно  должна  быть  описана  в  процедуре.
9
  Циклический  сдвиг  элементов  массива
Задано:  массив A=(a1,a2,...,an); N - размер массива;  m – число позиций, на которые надо сдвинуть массив  вправо ( влево ).

Сформировать: сдвинутый массив,  например : исходный массив A=(a1,a2,a3,a4,a5,), а сдвинутый вправо на  2  позиции A=(a4,a5,a1,a2,a3).

Исходные данные:

N - размер массива;

A - массив размером N;

M - число позиций сдвига;

Результат:  A - массив,  циклически  сдвинутый на M позиций вправо;

Вспомогательные  переменные:

I - индекс - управляющая переменная цикла;

P - массив размером не менее N  (вариант 1)  для временного хранения "хвоста" массива;

P - переменная  (вариант 2)  для временного хранения элемента  массива A; Y - управляющая переменная внутреннего цикла (вариант 2).
Вариант  1: "хвост" массива пересылается  во вспомогательный массив, остальные элементы перемещаются вправо на M позиций. Порядок перемещения обратный, прямой привел бы к искажениям массива. Далее в первые элементы массива A пересылаются элементы вспомогательного массива. Эта процедура повторяется М  раз.
Procedure SDVIG_VAR1( n, m : integer; A : mas; var A : mas ;);

{ процедура сдвига элементов массива на m позиций  по первому варианту }

          Var  P : mas;

           begin

             for i := 1 to m do

                                 P[ i ] := A [ n - m + i ];

                for i := n - m  downto 1 do

                                                A [ i+m ] := A[ i ];

                    for i := 1  to  m  do  A [ i ] := P [ i ] ;

           end;
Вариант  2.  Во вспомогательную переменную каждый раз пересылается последний элемент массива А, затем все элементы сдвигаются вправо на одну позицию (в обратном порядке) и на место первого элемента помещается содержимое вспомогательной переменной.
Procedure SDVIG_VAR2( n, m : integer; A : mas; var A : mas ;);

{ где   mas  должен быть описан в главной программе, см 7.1.}

{   сдвиг   элементов  массива   на  m  позиций  по второму варианту}

        Var  P : real;

           begin

              for i := 1 to  m  do

                                begin   P := A [ n ] ;

                                   for y := n  downto 2 do A[ y ] := A [ y-1] ;

                                          A [1] := P ;

                                end

           end;
При сравнении двух вариантов сдвига элементов массива на m  позиций вправо можно отметить, что в варианте 1 потребуется больше памяти, а  в варианте 2 - больше  затрат  времени.
10  Упорядочение Массива
Задано:  массив А=(a1,a2,...an).

Требуется: расположить элементы массива А в порядке возрастания (убывания).

Существует много различных методов. Рассмотрим один из них, основанный на поиске минимального (максимального) элемента массива или его части.

Исходные данные: 

N - размер массива;

A - массив размером N;

Результат: 

А - массив, упорядоченный по возрастанию;

Вспомогательные переменные:

P - переменная для хранения промежуточного значения минимального элемента;

K - индекс минимального элемента;

I - индекс элемента упорядоченного массива (управляющая переменная внешнего цикла);

J - индекс элемента части массива, в котором ищется минимальный элемент (управляющая переменная внутреннего  цикла).
Вначале найдем минимальный элемент массива и поменяем его местами с первым элементом, затем определим минимальный элемент из оставшихся элементов (кроме первого) и поменяем его местами со вторым элементом.
 Procedure SORTIROV (n : integer; A :mas; var A : mas; var K : integer);

{ где  mas  должен быть описан в главной программе, см 7.1.}

{ процедура  упорядочивания  одномерного  массива   по  возрастанию}

         Var  p : real ;  i, j :  integer ; {  локальные переменные }

            begin

             for i := 1 to n - 1 do

                begin   P := A [ i ] ; k := i ;

                         for   j := i + 1 to  n  do

                       If  A [ i ] <  P then  begin P := A [ i ] ; k := j  end;

                          A [ k ] := A [ i ] ; A [ i ] := P

                end

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

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

       

Пример 1.

Упорядочить по возрастанию одномерный массив  A размером  N.


program primer_1;

const N = 5;

var A            :  array [ 1..N ] of real;

       p            :   real;

       i, j, k, g  :   integer;

 begin

 writeln('упорядочение массива по возрастанию');

 writeln('введите элементы массива через пробел в  конце  ENTER ');

        for i := 1 to N do  read (A [ i ] );    writeln;

{  второй вариант ввода одномерного массива }

{ for i := 1 to N do

       begin write (' введите  A [', i:2 ,' ] = ' ) ;  readln ( A[i] );  end;}

  {  для упорядочивания массива задействуем промежуточные

      переменные  p - для запоминания минимального значения массива,

      k - для запоминания его местонахождения }

    for  i := 1 to N - 1 do

          begin

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

                for j := i + 1 to  N  do

                 if  A [ j ] <  p  then  begin   p := A[ j ];  k := j ;  end;

                  A [ k ] := A [ i ] ; A [ i ] := p ;

           end;

       for i := 1 to N  do

          begin   write( ' A [ i ] =');  writeln( A [ i ] : 8 : 5 ); end;

 end.

       
В следующем примере представлен более удобный вариант оформления программ, где самостоятельные части работы вынесены в процедуры. Главная программа ( вызывающая ) получается тогда очень короткой, а отладка таких программ значительно проще.
 Пример 2.

Программа для умножения сцепленных матриц A = ?aik? размера m x n  и B = ?bik? размера r x s ( матрицы называются сцепленными, если число столбцов первой матрицы равно числу строк второй ). Произведение AB двух сцепленных матриц есть матрица C=?cik?  размера m x s, где      cik  = ? aijbjk.
        program primer_2;

         uses CRT;

          const  n = 3; m = 2; r = 3; s = 3;

          type massiv = array [1..10,1..10] of real;

          var a,b,c   : massiv;

                sum     : real;

                  i, j, k    : integer;

                    ch      : char;

          procedure VVOD_2(n,m:integer;ch:char;var a:massiv);

            { процедура ввода двумерной матрицы построчно}

            begin

              writeln( '  введите элементы массива ');

               for i := 1 to n do

                 begin

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

                     writeln;  { для перехода на новую строку}

                         end;

             end;

          procedure PRINT_MAS(n,m:integer;ch:char;a:massiv);

             {   печать матрицы построчно }

             {  n,m  - размер матрицы }

                     {  ch - название матрицы , для обозначения при выводе }

            begin

               writeln('      Элементы массива  ',ch);

                    for i := 1 to n do

                     begin

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

                        writeln; { для перехода на новую строку }

                     end;

           end;
          begin    {---------- main ------------------}
    { В рассматриваемом примере размеры матриц A, B, C заданы с помощью

констант. Заметим, что  лучше это сделать вводом с клавиатуры или  чтени-

ем данных из файла }

        VVOD_2(m,n,'A',a); { вызов процедуры VVOD_2 для ввода матрицы A }

          VVOD_2(r,s,'B',b); { вызов процедуры VVOD_2 для ввода матрицы B }

      { формирование матрицы C равной произведению матриц A*B }

               for i := 1 to m do

                for  k := 1 to s do

                    begin

                     sum := 0; { обнуление переменной для вычисления суммы }

                    for j := 1 to N do  sum := sum + a[ i , j ] * b [ j , k ] ;

                             c[ i , k ] := sum;

                    end;

            { вывод на экран исходных данных и результатов }

              PRINT_MAS(m,n,'A',a);      { m,n - размеры матрицы A }

                     PRINT_MAS(r,s,'B',b);      { r,s - размеры матрицы B }

                        PRINT_MAS(m,s,'C',c);      { m,s - размеры матрицы C }

           end.