Массивы. Типы алгоритмов на обработку матриц. Построчная обработка. Обработка матрицы по столбцам. Обработка части матрицы

МАССИВЫ

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

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

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

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

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

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

5.1.  перестановка двух строк

5.2.  перестановка двух столбцов

5.3.  удаление строки

5.4.  вставка строки

5.5.  построение матриц:

5.5.1.  с элементами, зависящими от своих же индексов

5.5.2.  с использованием одного числа

5.5.3.  с использованием одномерных массивов

5.5.4.  с использованием одной или нескольких определенных ранее матриц

1. Построчная обработка: для каждой строки матрицы требуется найти некоторый параметр (сумму, количество элементов строки с некоторым условием, наибольший (наименьший) элементы, определенный элемент (например, 0) и т.д.

 Особенность: не обязательно надо анализировать все элементы строки.

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

Пример: пусть задана матрица A[n][m], в которой Аij – оценка i-го студента на j-м экзамене. Задача нахождения среднего балла каждого студента S[n] относится к рассматриваемому типу.

Рассмотрим вариант части программы:

double 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;

}

Замечания:

1. Массив S и переменная Sum должны объявляться с типом double  или возможен такой вариант: double S[n]; int Sum;…… S[i] = double (Sum)/m;
2. Массив S имеет размерность n (количество строк матрицы) и индекс его элемента совпадает с номером строки (i), а не столбца (j).
3. Оператор Sum = 0; должен располагаться между операторами for, так как для каждой строки суммирование необходимо начинать с начала.
4. Оператор S[i] = Sum/m; должен располагаться внутри внешнего, но вне внутреннего цикла.

2. Обработка матрицы по столбцам: аналогичные вычисления можно выполнять не для каждой строки, а для столбцов. Так как матрицы располагаются в памяти по строкам, то элементы столбца располагаются не рядом, а на определенном удалении друг от друга. Для больших матриц и «слабых» компьютеров обработка по столбцам малоэффективна с точки зрения времени выполнения программы. Поэтому такую обработку желательно избегать (например, транспонируя матрицу). В качестве примера такой обработки продолжим рассмотрение задачи предыдущего пункта: найдем сразу и выведем, не формируя массив, количество плохих оценок К по каждому предмету, т.е. проанализируем элементы каждого столбца:

int K, I;

for (int j=0; j<m; j++)              //цикл по столбцам-предметам j

{for (K=0, I=0; I<n; I++)            //цикл по строкам-студентам I

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

cout << j << ”  ” << K;

}

Особенность:  внешний цикл строим по номеру столбца. Во внутреннем цикле, изменяя первый «левый» индекс, обрабатываем столбец как одномерный массив. Обращаем внимание, что как и в предыдущем случае, важно место оператора обнуления счетчика K=0; и оператора вывода результата.

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

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

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;

}

cout << MyMax << ” ” << Imax <<”  ”<< Jmax;

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

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

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

double  Sum=0;

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

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

if (i==j) Sum +=A[i][j];

Sum /=n;

Так как для элементов главной диагонали оба индекса одинаковы, то это можно выполнить компактнее с помощью одного цикла:

double Sum=0;

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

Sum +=A[i][i];

Sum /=n;

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