Циклический сдвиг элементов массива

 

Задано: массив 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 - больше затрат времени.

 

Упорядочение Массива

 

Задано: массив А=(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.