Типы алгоритмов на обработку матриц (двухмерных массивов)

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

Построчная обработка

К такому типу относятся задачи, в которых для каждой строки матрицы требуется найти её некоторый параметр. Таким параметром может быть, например, сумма, количество всех элементов строки или элементов с некоторым условием, наименьший (наибольший) элемент среди всех или части элементов строки и т. д. К этому классу можно отнести и задачи типа “есть ли нуль в строке матрицы?”. Их особенность в том, что не обязательно надо анализировать все элементы строки.

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

Обработка матрицы по столбцам

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

Особенность таких задач в том, что внешний цикл строим по номеру столбца. Во внутреннем цикле, изменяя первый “левый” индекс, обрабатываем столбец как одномерный массив. Как и в задачах предыдущего типа, важна правильная расстановка фигурных.

Замечание. Поскольку матрицы располагаются в памяти по строкам, то элементы столбца находятся не рядом, а на определённом удалении друг от друга. Поэтому обработка по столбцам малоэффективна для больших матриц и “слабых” компьютеров с точки зрения времени выполнения программ. Такую обработку желательно избегать, сформировав по–другому матрицу. Например, перед вводом матрицу можно транспонировать.

Обработка всей матрицы

Это задачи, в которых выполняется анализ матрицы не отдельно для каждой строки или столбца, а для всей матрицы в целом. В таких алгоритмах можно обрабатывать её как по строкам, так и по столбцам. Внешний цикл отвечает за перебор строк, а внутренний —столбцов.

Найдём наибольший элемент во всей матрице и номер строки и столбца, на пересечении которых он находится:

int MyMax, Imax, Jmax;

MyMax=A[0][0]; Imax=Jmax=0;

for (int i=0; i<n; i++)

for (int j=0; j<m; j++)

if ( A[i][j]>MyMax)

{ MyMax= A[i][j];

Imax=i;

Jmax=j; }

printf(" \n Максимум= %d в %d строке, %d столбце", MyMax,Imax, Jmax);

Обратим внимание, что операторы MyMax=A[0][0];Imax=Jmax=0; располагаются вне всех циклов, так как мы находим общий наибольший элемент, т. е. одно число, а не для каждой строки или столбца отдельно.

Обработка части матрицы

Выделим некоторые подтипы таких задач.

Обработка элементов главной или побочной диагонали квадратной матрицы, объявленной, например, так: const n=5; int A[n][n]; Структура циклов останется такой же, как при решении аналогичной задачи для одномерного массива. Например, найти среднее арифметическое элементов главной диагонали, т.к. для элементов главной диагонали оба индекса одинаковы, то это можно обойтись одним циклом:

float Sum=0;

for (int i=0; i<n; i++)

Sum+=A[i][i];

Sum/=n;

Для обработки побочной диагонали, как и при решении некоторых других типов задач, необходимо найти зависимость второго индекса от первого. Легко видеть, что сумма индексов равна n-1, поэтому второй индекс для элемента побочной диагонали будет равен n-1-i, и соответствующая часть программы будет такой:

float Sum=0;

for (int i=0; i<n; i++)

Sum+=A[i][ n-1-i];

Sum/=n;

Обработка верхнего треугольника квадратной матрицы относительно главной диагонали — это те элементы, у которых i<j, если главная диагональ не включается, или i<=j, если включается. Аналогично определяется нижний треугольник относительно главной диагонали и треугольники относительно побочной диагонали.

Для обработки таких треугольников необходимо определить, как изменяются индексы. Анализируя, например, верхний треугольник, можно видеть, что в нулевой строке j изменяется от 0 до n-1, в первой строке — от 1 до n-1, во второй строке — от 2 до n-1 и так далее. Значит, в произвольной i-й строке индекс j изменяется от i до n-1. Поэтому, например, подсчёт количества нулевых элементов верхнего треугольника, включая и главную диагональ, будет выглядеть следующим образом:

int K=0;//количество нулей в верхнем треугольнике

for (int i=0; i<n; i++)

for (int j=i; j< n; j++)

if (A[i][j] ==0) K++;

Преобразование матрицы

Выделим некоторые подтипы таких задач.

Перестановка двух строк, номера n1 и n2 которых заданы, выполняется следующим образом. Составим функцию для перестановки двух целых чисел:

void RR( int &x, int &y)

{ int t; t=x; x=y; y=t;}

В другой функции или в main выполняем поэлементную перестановку каждой пары элементов:

for (int j=0; j<m; j++)

RR( A[n1][ j] , A[n2][j]);

В качестве упражнения с помощью той же функции выполните перестановку m1–го и m2–го столбцов, если m1 и m2 заданы.

Удаление k–й строки, где k известно, выполняется так:

for (int i=k; i<n-1; i++)

for (int j=0; j<m; j++)

A[i][j]=A[i+1][j];

Здесь на место k–й строки помещаем каждый элемент (k+1)–й строки, на место (k+1)–й — (к+2)–ю строку и так далее. Наконец, на место (n-2)–й копируем (n-1)–ю строку. Таким образом, все строки, начиная с (к+1)–й, “поднимаем на одну вверх”. При этом объём зарезервированной памяти для матрицы не изменяется. По-прежнему в памяти находится n строк, то есть физически ни одну строку из памяти мы не удаляли. Но после удаления одной строки количество обрабатываемых строк на одну уменьшается. Последняя строка в обработке уже не должна участвовать.

Для вставки одной строки после к-й на первом этапе необходимо все строки с (n-1)–й до (к+1) в обратном порядке “опустить вниз”:

for (int i=n-2; i>=k+1; i - -)

for (int j=0; j<m; j++)

A[i+1][j]=A[i][j];

Затем на место освободившейся (k+1)–й строки надо поместить вставляемую строку, например, одномерный массив B такой же размерности m, что и строка матрицы:

for (int j=0; j<m; j++)

A[k+1][j]=B[j];

При объявлении матрицы необходимо учесть, что после вставки количество строк увеличится. Поэтому если по условию вставляется одна строка, то объявляем так: int A[n+1][m]. Если после каждой строки с некоторым условием (например, в строке больше половины нулей) надо вставить новую строку, то матрицу надо объявить так: int A[2*n][m]. В этом случае резервируется максимальный объём памяти в предположении, что после каждой строки надо вставлять новую. Реально такой вариант будет маловероятным и память будет использоваться неэффективно.

Похожая проблема с памятью имеет место и при удалении строк. Более того, если перестановку, удаление или вставку строк надо выполнять несколько раз, то для больших матриц может возникнуть проблема и с временем выполнения программы. Поэтому

на практике такое преобразование эффективнее выполнять с помощью динамических матриц или списков (2–й семестр).

Построение матриц

Выделим некоторые подтипы таких задач.

Элементы новой матрицы зависят от своих же индексов.

Элементы матрицы используют одно число.

Построение матрицы на одном или нескольких одномерных или двухмерных массивах.