Простейшие алгоритмы обработки массивов

Лекция № 10

Простейшие алгоритмы обработки массивов

Цель: Рассмотреть простейшие алгоритмы работы с массивами, особенности организации циклов при обработке одномерных массивов (векторов) и двумерных массивов (матриц), организацию ввода-вывода массивов, а общие вопросы организации программ для обработки массивов.

1.  Ввод массива. Для ввода массивов необходимо составить программу, обеспечивающую изменение индексов и последовательное заполнение элементов массива данными.

Ввод одномерного массива

. . . . .

Write ('Введите количество элементов массива');

Readln (n);

     For i:=1 to n do

                 Read (Mass[i]);

. . . . .

Или

. . . . . .

Write ('Введите количество элементов массива');

Readln (n);

Randomize;

     For i:=1 to n do

                 Begin

Mass[i]=Random (10)-5; {диапазон: от –5 до 5}

Writeln(Mass[i]);

End;

            . . . . .

Особенностью выполнения этого фрагмента программы является то, что процедура Write (Mass[i]) выполняется n раз и при каждом ее выполнении выводится значение (очередной элемент массива).

При вводе двумерного массива необходимо организовать вложенный цикл: внешний – по номеру строки, внутренний – по номеру столбца.

Ввод двумерного массива по строкам.

. . . . .

Write ('Введите количество строк');

Readln (n);

Write ('Введите количество столбцов');

Readln (m);

For i:=1 to n do

     Begin

Write ('Введите', i, 'строку');

For j:=1 to m do

                    Read (Mass[i, j]);

Writeln;

     End;

. . . . .

Ввод по строкам является более естественным. Но при необходимости можно организовать ввод элементов массива и по столбцам. Для этого внешний цикл организуют по столбцам, а внутренний – по строкам с соответствующими границами изменения индексов.

Еще один способ ввода элементов массива с использованием процедуры GotoХY.

uses crt;

var

i, j, n, m:integer;

Mass: array [1..10, 1..10] of integer;

Begin

ClrScr;

readln (n, m);

randomize;

for i:=1 to n do

 for j:=1 to m do

begin

Mass [i, j]:= random (15)-5;

Gotoxy (10+5*j,i+1);

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

end;

readln;

end.

2.  Вывод массивов. При выводе массивов необходимо обеспечить наглядность и удобство восприятия полученных результатов.

Вывод одномерного массива, как правило, целесообразнее осуществлять в строку, сопровождая пояснительным текстом.

Вывод одномерного массива

. . . . . Write ('Вывод массива'); For i:=1 to n do    Write (Mass[i]:4); . . . . .

или

. . . . . Write ('Вывод массива'); For i:=1 to n do Writeln (i, 'элемент', Mass[i]); . . . . .

При выводе двух или более одномерных массивов одной размерности часто удобно располагать в виде параллельных столбцов:

. . . . .

Write ('Вывод массива');

For i:=1 to n do

Writeln (i, '  элемент 1-го массива', Mass1[i], '  2-го массива', Mass2[i]);

. . . . .

Вывод двух или более массивов различной размерности, как правило, осуществляется в строку. Вывод нового массива начинается с новой строки.

Вывод двумерного массива. Двумерные массивы необходимо выводить в привычном (по строкам) виде, начиная вывод новой строки массива в новой строке экрана.

Вывод двумерного массива по строкам.

. . . .

Write ('Вывод массива');

For i:=1 to n do

     Begin

For j:=1 to m do

        Write (Mass[i, j]:5);

Writeln;

     End;

. . . . .

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

3.  Суммирование элементов массива

_n

а) Для одномерного массива А={a₁, a₂,…., a_n} необходимо вычислить S = S a_i.

ⁱ⁼¹

. . .

S:=0;

For i:=1 to n do

S:= S + A[i];

{найдем среднее арифметическое }

S:= S / n;

. . . .

_{n  m}

б) Для двумерного массива B={b₁₁, ,…., b_nm} необходимо вычислить S=S  S b_ij.

^{i=1 j=1}

. . . .

S:=0;

For i:=1 to n do

For j:=1 to m do

S:= S + B[i, j];

. . . .

4.  Суммирование диагональных элементов массива (вычисление следа матрицы)

_n

Для матрицы размером N x N необходимо вычислить S=S a_ij.

ⁱ⁼¹

Writeln ('Вычисление следа матрицы');

S:=0;

For i:=1 to n do

S:= S + A[i, i];

{для обратной диагонали S:= S + A[i, n+1 – i]}

5.  Суммирование двух массивов.

Для одномерных массивов А и В размерности N необходимо вычислить

c_i = a_i + b_i,       i= 1, 2, …, n.

Writeln ('Суммирование векторов');

For i:=1 to n do

C[i]:= A[i] + B[i];

Для двумерных массивов А и В размерности N х М необходимо вычислить

c_ij = a_ij + b_ij,                 i = 1, 2, …, n;             j = 1, 2,…, m.

Writeln ('Суммирование матриц');

For i:=1 to n do

For j:=1 to m do

C[i, j]:= A[i, j] + B[i, j];

. . . .

6.  Суммирование  элементов заданной строки матрицы.

_m

Для двумерного массива А размерности N х М необходимо вычислить S = Sa_ij

^j=1

. . . .

Writeln ('Суммирование i-ой строки матрицы');

S:= 0;

For j:=1 to m do

S:= S + A[i, j];

. . . .

7.  Суммирование  элементов строк матрицы.

_m

Для двумерного массива А размерности N х М необходимо вычислить d_i = Sa_ij

^j=1

т.е. сумму элементов каждой строки матрицы А. Результат получим в виде вектора D.

. . . .

Writeln ('Суммирование матрицы по строкам');

For i:=1 to n do

Begin

S:= 0;

For j:=1 to m do

S:= S + A[i, j];

D[i] := S;

End;

. . . .

Замечание: На поиск в массиве элемента с заданным номером затрачивается время. Поэтому для эффективности работы программы при вычислении суммы каждой строки используется простая переменная S, что исключает многократное обращение к элементам массива D.

8.  Транспонирование матрицы.

Необходимо заменить строки матрицы ее столбцами, а столбцы – строками, т.е. вычислить b_ij := a_ji,    i= 1, …, n,      j=1, …, m. (Массив A[n, m], а массив B[m, n]).

. . . . .

Writeln ('Транспонирование матрицы');

For i:= 1 to n do

For j:= 1 to m do

B[i, j] := a[j, i] ;

. . . . .

Транспонированную матрицу можно получить и в исходном массиве А.

В случае квадратной матрицы размером N x N для получения