Обработка матрицы по столбцам
Пример 8. Задана матрица A[n][m], в которой Aij — оценка i–го студента на j–м экзамене. Найдём и сразу выведем, не формируя массив, количество плохих оценок по каждому предмету, т. е. в каждом столбце.
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 column %d“ , j, K);
}
Особенность таких задач в том, что внешний цикл строим по номеру столбца, то есть по второму правому индексу. Во внутреннем цикле, изменяя первый левый индекс, обрабатываем столбец как одномерный массив. Как и в задачах предыдущего типа, важна правильная расстановка фигурных скобок и место операторов K=0; и printf. Каждый из них выполняется m раз, то есть для каждого столбца.
Поскольку матрицы располагаются в памяти по строкам, то элементы столбца находятся не рядом, а на определённом удалении друг от друга. Поэтому обработка по столбцам малоэффективна с точки зрения времени выполнения программ. Такую обработку желательно избегать.
Обработка всей матрицы
К такому типу отнесём задачи, в которых выполняется анализ всей матрицы, а не отдельно каждой строки или столбца. В таких алгоритмах можно обрабатывать её как по строкам, так и по столбцам. Но так как элементы матрицы располагаются в памяти по строкам, то лучше внешний цикл по номеру строки, а внутренний — по номеру столбца.
Пример 9. Найдём наибольший элемент во всей матрице и номер строки и столбца, на пересечении которых он находится.
int MyMax= A[0][0], Imax=0, 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 = %d in %d row, %d column", MyMax, Imax, Jmax );
Обратим внимание, что операторы MyMax=A[0][0]; Imax=Jmax=0; располагаются вне всех циклов, так как мы находим общий наибольший элемент, т. е. одно число, а не для каждой строки или столбца отдельно. По этой же причине сprintf выполняется тоже один раз. Поэтому фигурные скобки расставлены по–другому, не так, как в задачах первых двух типов.
Упражнения.
1. Если наибольший элемент повторяется несколько раз, индексы какого из них мы найдём? Как найти индексы каждого наибольшего элемента?
2. Как наибольший элемент и его номер найти для каждой строки и выводить по мере получения без формирования массивов?
3. Что надо изменить, чтобы наибольший элемент и его номер находились для каждого столбца?
Обработка части матрицы
Рассмотрим алгоритм обработки элементов главной или побочной диагонали квадратной матрицы const n=5; int A[n][n]; котораяодним из ранее рассмотренных способов определена. Структуру циклов можно оставить такой же, как при решении аналогичной задачи для одномерного массива.
Пример 10. Найдём среднее значение главной диагонали квадратной матрицы .
Для этого необязательно писать два вложенных цикла:
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;
Сравните с задачей нахождения этого же параметра в одномерном массиве.
Пример 11. Найдём среднее значение побочной диагонали.
Для обработки побочной диагонали, как и при решении некоторых других типов задач, необходимо найти зависимость второго индекса от первого. Так как сумма индексов равна n-1, то второй индекс будет равен n-1-i, где i— номер строки. float Sum=0;
for (int i=0; i<n; i++) Sum+=A[i][ n-1-i];
Sum/=n;
Верхний треугольник квадратной матрицы относительно главной диагонали — это те элементы, у которых i<j, если главная диагональ не включается, или i<=j, если включается. Аналогично определяется нижний треугольник относительно главной диагонали и треугольники относительно побочной диагонали. Для обработки таких треугольников необходимо определить, как изменяются индексы.
Пример 12. Найти количество нулевых элементов верхнего треугольника относительно главной диагонали, включая и её.
В нулевой строке 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++)…
Упражнения. Эту же задачу решить для
a) нижнего треугольника относительно главной диагонали;
b) нижнего треугольника относительно побочной диагонали;
c) верхнего треугольника относительно побочной диагонали;
3.5. Преобразование матрицы
Пример 13. Перестановка двух строк, номера n1 и n2 которых извстны, выполняется следующим образом. Составим функцию для перестановки двух целых чисел: void RR( int &x, int &y) { int 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 заданы.
Пример 14. Удаление 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-1) строку.
Пример 15. Для вставки одной строки после к-й на первом этапе необходимо все строки с n–й до (к+1)-й в обратном порядке “опустить вниз”:
for (int i=n; 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];. Реально такой вариант будет маловероятным и память будет использоваться неэффективно.
Похожая проблема с памятью имеет место и при удалении строк. Более того, если перестановку, удаление или вставку строк надо выполнять несколько раз, то для больших матриц может возникнуть проблема и со временем выполнения программы. Поэтому на практике такое преобразование эффективнее выполнять с помощью динамических матриц или списков, которые будут изучены позже.
Построение матриц
Выделим некоторые подтипы таких задач.
1. Элементы матрицы зависят от своих же индексов, т. е. от номера строки и (или) столбца.
Пример 16 (см. пример 3).Построить матрицу по правилу Aij = (i+1)*(j+1);
2.При построении матрицы используется одно число.
Пример 17. Для заданных значений x и n построить квадратную матрицу размерности n:
1 x x2 x3 … xn-1
x 0 0 0 … xn-2
x2 0 0 0 … xn-3
… … … … … …
xn-1 xn-2 xn-3 x… 1
Предлагается следующий алгоритм. Очередной элемент “периметра” матрицы получаем так: умножаем предыдущий элемент на x и помещаем его в первую и последнюю строки, в первый и последний столбцы. Для этого достаточно одного цикла. const n=5; float A[n][n], x, T=1;
cin>> x; /* Ввели только одно число */
A[0][0]= A[n-1][n-1]=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.Матрицу можно построить, используя один или несколько одномерных массивов.
Пример 18. Дан одномерный массив b[n]. Построить матрицу A[n][m] по следующему правилу:
b0 b0+1 b0+2 … b0 +(m-1)
b1 b1+1 b1+2 … b1 +(m-1)
… … … …
bn-1 bn-1 +1 bn-1 +2 bn-1 +(m-1).
В таких задачах необходимо установить, от чего и как зависят индексы элементов матрицы и, возможно, значения её элементов. Получаем
for (int i=0; i<n; i++)
for (int j=0; j<m; j++) A[i][j]=b[i]+j;
4. Новая матрица строится на основе одной или нескольких определённых к этому времени матриц.
Пример 19. Из вещественной матрицы С[n][m]. получить новую матрицу такой же размерности A[n][m] по правилу: положительные числа исходной матрицы увеличим в 10 раз, а отрицательные уменьшим в 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;. В таком варианте матрица С задана, она же в результате преобразований изменяется, то есть новые значения заменяют старые на том же месте оперативной памяти. Новая матрица А в таком случае не нужна.
Этот параграф, безусловно, не претендует на полное исследование всех типов матричных алгоритмов. Приведены основные наиболее простые из них, которые можно использовать при начальном изучении программирования с минимальным знанием математической теории матриц. Более сложные задачи состоят, как правило, из отдельных рассмотренных выше “кирпичиков”.