§ 3. Типы алгоритмов на обработку матриц

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

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

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

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

Например, пусть задана матрица A[n][m], в которой A_ij — оценка i–го студента (школьника) на j–м экзамене. Задача нахождения среднего балла каждого студента (школьника) относится к рассматриваемому типу.

Приведём вариант части программы (определение матрицы и вывод опускаем), в которой формируем массив S[n], каждый элемент которого содержит средний балл одного студента (школьника):

float S[n], Sum;

… … …

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

{ Sum=0;

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

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

S[i]=Sum/m;

}

Здесь важно обратить внимание на следующее:

• оператор Sum=0; должен располагаться именно в этом месте, то есть между операторами for, так как для каждой строки суммирование необходимо начинать с начала;

• важны также расстановка фигурных скобок и место оператора S[i]=Sum/m. Он должен выполняться n раз и поэтому располагается внутри внешнего, но вне внутреннего цикла. В качестве упражнения предлагается рассмотреть другие варианты расстановки фигурных скобок;

• массив S имеет размерность n (количество строк матрицы), и индекс его элемента i, а не j, т. е. совпадает с параметром внешнего цикла;

• массив S и переменная Sum должны объявляться с типом float. Если объявить их как int, то в массиве сохранится результат целочисленного деления без дробной части. Например, при делении 37/5 вместо 7.4 получили бы целое число 7. Заметим, что недостаточно объявить только массив как float, оставив int Sum. В таком случае получится число 7 как результат целочисленного деления, а в массиве оно будет представлено как число с плавающей точкой. Это проблему типов данных можно решить и так: float S[n]; int Sum; … S[i]=(float)Sum/m; Здесь при вычислении выражения переменная Sum приводится (преобразуется) к вещественному типу. При этом в других операциях она остаётся целочисленной.

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

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

int K, I ;

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

{ for (K=0, I =0; I <n; I ++)

if (A[I][j]==1 || A[I][j]== 2 || A[I][j] == 3) K++ ;

printf(“ \n%d-й столбец %d“ , j, K);

}

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

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