Типовые алгоритмы работы с матрицами

1. Просуммировать элементы строк матрицы a. Результат получить в виде вектора (одномерного массива) b.

int[,] a = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

int[] b = new int[3];

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

{

int s = 0;

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

s += a[i, j];

b[i] = s;

}

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

Console.Write("{0:d} ", b[i]);

Console.WriteLine();

Console.ReadKey();

Аналогично осуществляется формирование одномерных массивов из значений максимальных (минимальных) элементов строк, индексов максимальных (минимальных) элементов строк и т.п. (см. соответствующие алгоритмы для одномерных массивов).

Если необходимо осуществить обработку столбцов матрицы, то внешний цикл необходимо организовать по номеру столбца, а внутренний - по номеру строки. В остальном алгоритмы аналогичны.

2. Поменять местами ii-ю и jj-ю строки матрицы.

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

int[,] a = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

int p = 0;

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

{

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

Console.Write("{0:d} ", a[i,j]);

Console.WriteLine();

}

int ii = 1, jj = 2;

for (int k = 0; k < 3; k++)

{

p = a[ii, k]; a[ii, k] = a[jj, k]; a[jj, k] = p;

}

Console.WriteLine();

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.ReadKey();

Столбцы меняются местами аналогично (цикл организуется по строкам).

3. Удалить k-ю строку матрицы.

Чтобы удалить строку, необходимо переместить все строки, расположенные после k-й, на одну позицию вверх. Для перемещения строки нужно организовать цикл по элементам строки, т.е. по столбцам:

int[,] a = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

int n = 3, m = 3;

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

n = n - 1;

int k = 1;

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

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

a[i, j] = a[i + 1, j];

Console.WriteLine();

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.ReadKey();

Удаление столбца осуществляется аналогично (внутренний цикл по элементам столбца, т.е. по строкам).

4. Вставить новую строку, заданную вектором b[m], после k-й строки матрицы.

Вначале нужно освободить место для новой строки, переместив строки, расположенные после k-й, на одну позицию вниз. (При объявлении матрицы предусмотреть необходимость соответствующего увеличения ее размера.)

Перемещение строк нужно начинать с последней строки (см. аналогичный алгоритм для одномерных массивов в п. 3.1):

int[,] a = new int[4, 3];

int[] b = new int[3] { 7, 5, 7 };

int n = 3, m = 3;

Random r = new Random();

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

{

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

{

a[i, j] = r.Next(55);

Console.Write("{0:d2} ", a[i, j]);

}

Console.WriteLine();

}

Console.WriteLine();

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

{

Console.Write("{0:d2} ", b[i]);

}

Console.WriteLine();

Console.WriteLine();

int k = 1;

for (int i = n - 1; i >= k; i--)

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

a[i + 1, j] = a[i, j];

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

a[k, j] = b[j];

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

{

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

Console.Write("{0:d2} ", a[i, j]);

Console.WriteLine();

}

Console.ReadKey();

Замечание. Здесь переменная r – экземпляр класса Random, который представляет генератор псевдослучайных чисел. Метод Next(maxValue) создает случайное число в диапазоне значений от нуля до числа maxValue, указанного в качестве аргумента метода. r.Next(55) – метод Next, определенный в классе Random и примененный к экземпляру класса r – генерирует следующее псевдослучайное число.

Вставка столбца осуществляется аналогично.

5. Найти сумму элементов матрицы.

Здесь нужно обратиться к каждому элементу матрицы и добавить его к сумме:

int[,] a = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

int n = 3, m = 3;

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

int s = 0;

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

{

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

s += a[i, j];

}

Console.WriteLine(s);

Аналогично осуществляется поиск максимального элемента во всей матрице.

Далее будут рассмотрены типовые алгоритмы для квадратной матрицы a размером n*n.

6. Найти сумму элементов, расположенных на главной диагонали (след матрицы).

Элементы, расположенные на главной диагонали, имеют одинаковые индексы (номера строк и столбцов совпадают) и представляют, таким образом, одномерный массив:

int s = 0;

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

{

s += a[i, i];

}

Аналогично можно организовывать и другие алгоритмы для работы с диагональными элементами (нахождение максимального элемента и т.п.).

7. Найти сумму элементов, расположенных ниже главной диагонали (включая диагональ), т.е. просуммировать элементы нижнего треугольника матрицы.

Здесь во внешнем цикле (по строкам) номера строк изменяются от 0 до n–1, но в каждой i-й строке суммируются только элементы, расположенные до диагонального элемента этой строки, т.е. до i-го:

int s = 0;

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

{

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

s += a[i, j];

}

8. Транспонирование матрицы с получением результата в том же массиве. Для квадратной матрицы размером n´ n требуется переставлять элементы, расположенные симметрично относительно главной диагонали.

int p = 0;

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

{

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

{

p = a[i, j]; a[i, j] = a[j, i]; a[j, i] = p;

}

}

Для прямоугольной матрицы размером n´ m транспонированная матрица может быть получена на месте исходной, если последняя размещена в массиве размером не менее чем n´n (предполагается, что n>m). При этом можно использовать приведенный выше алгоритм. Фиктивные столбцы, дополняющие исходную матрицу до квадратной, помещаются в этом случае в фиктивные строки транспонированной матрицы.

9. Умножение матрицы на вектор.

Требуется умножить матрицу а размером n´m на вектор b размером m. Для этого необходимо вычислить

c[i] = а[i, j] b[j], i = 0, ..., n – 1 .

int[,] a = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

int[] b = new int[3] { 3, 4, 1 };

int[] c = new int[3];

int n = 3, m = 3;

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

int s;

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

{

s = 0;

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

{

s = s + a[i, j] * b[j];

}

c[i] = s;

}

Console.WriteLine();

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

{

Console.Write("{0:d} ", c[i]);

}

Console.WriteLine();

Console.ReadKey();

10. Умножение матрицы на матрицу. Требуется умножить матрицу а размером n´ k на матрицу b размером k´m. Для этого необходимо вычислить

…, …,m – 1.

int[,] a = new int[3, 3] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

int[,] b = new int[3, 3] { { 3, 4, 1 }, { 1, 2, 4 }, { 2, 4, 3 } };

int[,] c = new int[3, 3];

int n = 3, m = 3, k = 3;

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.WriteLine();

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

{

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

Console.Write("{0:d} ", b[i, j]);

Console.WriteLine();

}

int s;

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

{

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

{

s = 0;

for (int l = 0; l < k; l++)

{

s = s + a[i, l] * b[l, j];

}

c[i, j] = s;

}

}

Console.WriteLine();

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

{

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

Console.Write("{0:d} ", c[i, j]);

Console.WriteLine();

}

Console.WriteLine();

Console.ReadKey();

11. Определение номера k (нумерация начинается с 0) элемента a[i, j] матрицы размера n´m (нумерация n и m начинается с 1), заданной в виде одномерного массива по строкам:

k =(i-1)m+j-1;

12. Определение номера k (нумерация начинается с 0) элемента a[i, j] симметрической матрицы размером n´n (нумерация n – с 1), заданной своим верхним треугольником в одномерном массиве b размером (n+1)n/2:

k = (2n – (i–1) +1)(i – 1)/2 + j – (i – 1) – 1 , i = 1, 2, ..., n; j = i, i+1, ..., n.

Элементы нижнего треугольника определяются как

a[i, j] = a[j, i], i = 2, ..., n; j = 1, ..., i – 1.

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

const int n = 5;

int k = 0;

const int m = (n * (n + 1)) / 2;

int[] b = new int[m];

int[,] a = new int[n, n];

Console.WriteLine("Введите верхний треугольник матрицы по строкам");

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

{

b[i] = int.Parse(Console.ReadLine());

}

Console.WriteLine("Верхний треугольник по строкам");

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

{

for (int l = 0; l < i; l++) Console.Write(" ");

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

{

Console.Write("{0:d} ", b[k]); k = k + 1;

}

Console.WriteLine();

}

Console.WriteLine();

//Формирование матрицы

k = 0;

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

{

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

{

if (j < i)

{

a[i, j] = 0;

}

else

{

a[i, j] = b[k]; k = k + 1;

}

}

}

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.WriteLine();

Console.ReadKey();

Замечание.В приведенном окне первые строки (с вводимыми элементами матрицы) обрезаны.

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

Номера строк в верхней половине матрицы изменяются от 0 до n/2. Индексы суммируемых элементов в строке изменяются от i до n–i.

const int n = 5;

const int m = (n + 1) / 2;

int s = 0;

int[,] a = new int[n, n];

Console.WriteLine("Введите элементы матрицы");

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

{

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

{

a[i, j] = int.Parse(Console.ReadLine());

}

}

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.WriteLine();

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

{

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

{

s += a[i, j];

}

}

Console.WriteLine("{0:d} ", s);

Console.ReadKey();

Замечание.В приведенном окне первые строки (с вводимыми элементами матрицы) обрезаны.

Пример 3.7.Для квадратной матрицы поменять местами минимальный и максимальный элементы главной диагонали, используя перестановку строк и столбцов.

const int n = 5;

int[,] a = new int[n, n];

Console.WriteLine("Введите элементы матрицы");

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

{

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

{

a[i, j] = int.Parse(Console.ReadLine());

}

}

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.WriteLine();

int amax = a[0, 0]; int imax = 0;

int amin = a[0, 0]; int imin = 0;

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

{

if (a[i, i] > amax)

{

amax = a[i, i]; imax = i;

}

if (a[i, i] < amin)

{

amin = a[i, i]; imin = i;

}

}

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

{

int p = a[imax, j];//Переменная p – локальная.

//Она действует только в пределах данного цикла.

a[imax, j] = a[imin, j]; a[imin, j] = p;

}

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

{

int p = a[i, imax];

a[i, imax] = a[i, imin]; a[i, imin] = p;

}

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

{

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

Console.Write("{0:d} ", a[i, j]);

Console.WriteLine();

}

Console.ReadKey();

См. замечание к предыдущей программе.

Пример 3.8. Поменять местами максимальный элемент нижнего треугольника (включая главную диагональ) матрицы х размером 6 * 6 с максимальным элементом верхнего треугольника.

const int n = 6;

int[,] x = new int[n, n];

Console.WriteLine("Введите элементы матрицы");

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

{

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

{

x[i, j] = int.Parse(Console.ReadLine());

}

}

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

{

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

Console.Write("{0,5:d} ", x[i, j]);

Console.WriteLine();

}

Console.WriteLine();

int xd = x[0, 0], id = 0, jd = 0;

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

{

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

{

if (x[i, j] > xd)

{

xd = x[i, j]; id = i; jd = j;

}

}

}

int xu = x[0, 0], iu = 0, ju = 0;

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

{

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

{

if (x[i, j] > xu)

{

xu = x[i, j]; iu = i; ju = j;

}

}

}

int t = x[id, jd]; x[id, jd] = x[iu, ju]; x[iu, ju] = t;

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

{

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

Console.Write("{0,5:d} ", x[i, j]);

Console.WriteLine();

}

Console.ReadKey();

Пример 3.9. В матрице a размером 5*4, представленной в виде одномерного массива по строкам (размер одномерного массива равен 20), удалить строку, содержащую максимальный элемент во 2-м столбце (нумерация с 0).

const int n = 20;

int[] a = new int[n];

Console.WriteLine("Введите элементы матрицы");

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

{

a[i] = int.Parse(Console.ReadLine());

}

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

{

Console.Write("{0,2:d} ", a[i]);

if ((i + 1) % 4 == 0) Console.WriteLine();

}

Console.WriteLine();

Console.WriteLine();

int amax = a[2], imax = 0;

for (int il = 0; il <= 4; il++)

{

if (a[il * 4 + 2] > amax)

{

amax = a[il * 4 + 2]; imax = il;

}

}

for (int il = imax; il < 4; il++)

{

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

{

a[il * 4 + j] = a[(il + 1) * 4 + j];

}

}

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

{

Console.Write("{0,2:d} ", a[i]);

if ((i + 1) % 4 == 0) Console.WriteLine();

}

Console.WriteLine();

Console.ReadKey();

Замечание.В листинге приведены только выводимые данные.

Вопросы для самопроверки

1. Матрица. Описание матрицы. Ввод матрицы по строкам, по столбцам. Вывод матрицы.

2. Суммирование элементов матрицы. Суммирование элементов матрицы, удовлетворяющих условию.

3. Нахождение максимального (минимального) элемента матрицы.

4. Суммирование элементов строк (столбцов) матрицы с формированием одномерного массива.

5. Операции со строками (столбцами) матрицы (поиск максимального элемента, включение, удаление элемента, перестановка элементов и т.п.)

6. Удаление строки (столбца) матрицы. Включение одномерного массива в качестве строки (столбца) в матрицу.

7. Операции с главной диагональю, с побочной главной диагональю.

8. Обработка фрагмента матрицы (верхнего, нижнего треугольника; верхней, нижней, правой, левой четверти; периметра и т.п.).

9. Особенности обработки матрицы, заданной в виде одномерной последовательности.

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

Задание для самостоятельного выполнения. Программу составить в двух вариантах, представляя матрицу а) в виде двухмерного массива; б) в виде одномерной последовательности.

1. Найти сумму элементов матрицы А размером 5 * 7.

2. Найти среднее среди положительных элементов матрицы А размером 5 * 7 .

3. Найти след (сумму диагональных элементов) квадратной матрицы А размером 4 * 4).

4. Определить номер строки и столбца, содержащих минимальный элемент матрицы А размером 3 * 6.

5. Определить значение и номер первого отрицательного элемента заданного столбца матрицы А размером 5 * 4.

6. Сформировать одномерный массив из индексов минимальных элементов строк матрицы А размером 4 * 7.

7. Сформировать одномерный массив из значений максимальных элементов столбцов матрицы А размером 3 * 5.

8. Сформировать одномерный массив из средних значений среди положительных элементов строк матрицы А размером 4 * 6.

9. Поменять местами максимальный и 1-й элементы строк матрицы А размером 5 * 7.

10. В матрице А размером 5 * 7 поменять местами строку, содержащую максимальный элемент в 3-м столбце, с 4-й строкой.

11. Удалить строку матрицы А размером 5 * 7, содержащую минимальный элемент в 1-м столбце.

12. В матрице А размером 6 * 7 удалить столбец и строку, на пересечении которых находится максимальный элемент матрицы.

13. В матрице А размером 5 * 5 поменять местами 4-й столбец со столбцом, содержащим максимальный элемент на диагонали.

14. Сформировать одномерный массив из количеств отрицательных элементов столбцов матрицы А размером 4 * 3.

15. Преобразовать матрицу А размером 5 * 7, умножив максимальный элемент каждой строки на номер этой строки.

16. В каждой строке матрицы А размером n * m максимальный элемент поместить в конец строки, сохранив порядок остальных элементов.

17. В каждой строке матрицы В размером n * m минимальный элемент поместить в начало строки, сохранив порядок остальных элементов.

18. В каждой строке матрица D размером n * m максимальный среди элементов, расположенных до первого отрицательного, поменять местами с последним отрицательным в этой строке.

19. В каждой строке матрицы С размером n * m все отрицательные элементы, расположенные перед максимальным, разделить на максимальный элемент.

20. В каждой строке матрицы F размером n * m максимальный элемент заменить на полусумму первого и последнего отрицательного в строке.

21. В матрице Н размером 5 * 7 заполнены первые 6 столбцов. Поместить в качестве предпоследнего столбца столбец, состоящий из максимальных элементов строк.

22. Матрица Z размером 6 * 8. Максимальный элемент матрицы заменить средним арифметическим положительных элементов матрицы.

23. Матрица G размером 5 * 7. Заполнены первые 6 столбцов. В каждой строке продублировать мах элемент, расположив новый элемент равный мах, сразу после мах.

24. Матрица Y размером 6 * 5. В каждой строке заменить отрицательные элементы, расположенные перед мах, на среднее среди положительных элементов, расположенных после мах.

25. Матрица X размером 6 * 5. Поменять местами строки, содержащие минимальное и максимальное число отрицательных элементов.

26. Матрица А размером 5 * 7. Строку, содержащую мах элемент в шестом столбце, заменить заданным вектором В размером 7.

27. Матрица В размером 5 * 7. Четвертый столбец матрицы заменить одномерным массивом, состоящим из мах элементов строк, расположенных в обратном порядке (т. е 1 элемент 4 столбца – это мах элемент пятой строки и.т. д.).

28. Матрица А размером 7 * 5. Удалить строку с максимальной суммой положительных элементов строки.

29. Матрица А размером 5 * 7. В каждой строке заменить мах элемент средним среди положительных элементов строки.

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

31. В матрице размером 5 * 7 переставить столбцы таким образом, чтобы количества отрицательных элементов в столбцах следовали в порядке возрастания.

32. В матрице размером 7 * 5 переставить строки таким образом, чтобы минимальные элементы строк следовали в порядке убывания.

33. Матрица В размером 6 * 6. Поменять местами мах элементы 1-й и 2-й строк, 3-й и 4-й, 5-й и 6-й.

34. Матрица F размером 5 * 7. Удалить столбец, расположенный после столбца, содержащего минимальный по модулю элемент во 2-й строке.

35. Строку, содержащую мах элемент главной диагонали матрицы В размером 5 * 5 поменять местами со строкой, содержащей первый (от начала столбца) отрицательный элемент в 3-м столбце.

36. В матрице А размером 6 * 6 найти мах элемент на главной диагонали. Заменить нулями элементы матрицы, расположенные правее главной диагонали в строках, расположенных выше строки, содержащей мах элемент на главной диагонали.

37. В матрице А размером 5 * 8 заполнены первые 7 столбцов. Поместить вектор В размером 5 после столбца, содержащего min элемент в 5-й строке.

38. Сформировать одномерный массив из отрицательных элементов матрицы А размером 5 * 7.

39. Сформировать матрицу размером n´3n, составленную из трех единичных квадратных матриц размером n´n.

40. Заполнить нулями элементы квадратной матрицы, расположенные по ее периметру (использовать один цикл).

41. Для квадратной матрицы размером n´n просуммировать элементы, расположенные на диагоналях, параллельных главной, включая главную диагональ. Результат получить в виде вектора размером 2n–1.

42. Для матрицы размером n´n заполнить единицами нижнюю половину (включая среднюю строку, если n нечетное) за исключением элементов, расположенных справа от главной диагонали.

43. Задана матрица размером n´n. Найти максимальный по модулю элемент матрицы. Перестановкой строк и столбцов перевести максимальный по модулю элемент на пересечение k-ой строки и k-го столбца (1 £ k £ n).

44. Задана матрица размером n´n. Сформировать два одномерных массива: в один переслать по строкам верхний треугольник матрицы, включая элементы главной диагонали, в другой - нижний треугольник. Вывести верхний и нижний треугольники по строкам.

45. Перемножить две симметрические матрицы, заданные в одномерных массивах верхними треугольниками по строкам (см. пп. 10, 12 введения к п.3.3). Результат получить в одномерном массиве. Вывести в привычном виде исходные матрицы и матрицу-результат.