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

      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.