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

Перестановка двух строк, номера 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, внутри циклов и т. д. Такие рассмотренные выше фрагменты желательно оформлять в виде функций. Этому посвящён следующий параграф.