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

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

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

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

В таких программах внешний цикл строится по номеру строки, а в одном или нескольких внутренних циклах обрабатывается строка как одномерный массив. При этом полученные характеристики строк можно запоминать в одномерном массиве размерности 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 приводится (преобразуется) к вещественному типу. При этом в других операциях она остаётся целочисленной.

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

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

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.

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

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

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

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

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

textcolor(10);

cprintf(" \n\r Max element= %d in %d row, %d column", MyMax,Imax, Jmax);

Обратим внимание, что операторы MyMax=A[0][0]; Imax=Jmax=0; располагаются вне всех циклов, так как мы находим общий наибольший элемент, т. е. одно число, а не для каждой строки или столбца отдельно. По этой же причине сprintf выполняется один раз. Поэтому фигурные скобки расставлены по–другому, не так, как в задачах первых двух типов. Заметим, что при “цветном” выводе с помощью cprintf для перехода в начало следующей строки недостаточно одного управляющего символа ‘\n’, а надо использовать и символ ‘\r’.

Упражнения.

1. Если наибольший элемент повторяется несколько раз, индексы какого из них мы найдём?

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

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

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

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

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

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 K0=0;

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

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

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

Если диагональные элементы не надо анализировать, то заголовок внутреннего цикла будет таким:

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

Упражнение. Эту же задачу решить для нижнего (верхнего) треугольника относительно побочной диагонали.

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

Перестановка двух строк, номера 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–й семестр).

Упражнения.

1. Переставить строки, в которых находится наибольший и наименьший элементы матрицы.

Указание. На первом этапе необходимо найти номера строк (n1 и n2), в которых находятся эти элементы. И если n1!= n2, то переставляем эти строки так, как показано выше.

2. Из матрицы удалить все нулевые строки, т. е. строки, состоящие из одних нулей.

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

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

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

1. Элементы новой матрицы зависят от своих же индексов, т. е. от номера строки и (или) столбца (см. § 1 гл. 5).

2. При построении матрицы используется одно число. Например, для заданных значений x и n построить матрицу A:

1 x x² x³ … x^n-1

x 0 0 0 … x^n-2

x² 0 0 0 … x^n-3

… … … … … …

x^n-1 x^n-2 x^n-3 … 1

Предлагается следующий алгоритм. Очередной элемент “периметра” матрицы получаем так: умножаем предыдущий элемент на x и помещаем его в первую и последнюю строки, в первый и последний столбцы. Для этого достаточно одного цикла. Все “центральные” элементы обнуляем.

const n=5; float x, A[n][n], T;

cin>> x; // Вводим только одно число

A[0][0]= A[n-1][n-1]=1;

T=1;

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

{ T*=x;

A[0][i]= // Элементы 0 –й строки

A[i][0]= // Элементы 0 –го столбца

A[n-1][n-1-i]= // Элементы (n-1) –й строки

A[n-1-i][n-1]= T; // Элементы (n-1) –го столбца

}

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

for (int j=1; j<n-1; j++)

A[i][j]=0;

3.Матрицу можно построить, используя один или несколько одномерных массивов. Например, задано b[n]. Cформировать двумерный массив по следующему правилу:

b₀ b₀+1 b₀+2 … b₀ +(n-1)

b₁ b₁+1 b₁+2 … b₁ +(n-1)

… … … …

b_n-1 b_n-1 +1 b_n-1 +2 b_n-1 +(n-1).

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

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

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

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

4. Новая матрица строится на основе одной или нескольких определённых к этому времени матриц.

Например, задана С[n][m]. Получим новую матрицу A[n][m] такой же размерности по следующему простому правилу: положительные числа исходной матрицы увеличим в 10 раз, а отрицательные уменьшим во столько же раз:

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

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

{ t= C[i][j];

A[i][j] = t>0? t*10: t/10;

}

Заметим, что старая матрица С сохранилась без изменения, а построенная разместилась на новом месте.

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

t= C[i][j]; С[i][j] = t>0? t*10: t/10;

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

Замечание.

Этот параграф, безусловно, не претендует на абсолютно полное исследование всех типов задач по теме “Матрицы”. Здесь приведены только наиболее простые из них, которые можно использовать при начальном изучении программирования. Многие, более сложные, задачи состоят, как правило, из рассмотренных выше и других типов задач как из отдельных “кирпичиков”, подсоединяемых один к одному последовательно. В реальных задачах такие блоки могут представлять собой также “матрёшки”, вложенные одна в другую в ветвях if, switch, внутри циклов и т. д. Такие рассмотренные выше фрагменты желательно оформлять в виде функций. Этому посвящён следующий параграф.