Tag Archives: произведение матриц

e-olymp 1482. Умножение матриц

by

0

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где:
$$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

Входные данные

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

Выходные данные

В первой строке вывести размерность итоговой матрицы $C$: $n_c$ и $m_c$. В последующих $n_c$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $-1$.

Тесты

Входные данные Выходные данные
2 3
1 3 4
5 -2 3
3 3
1 3 2
2 1 3
0 -1 1		 2 3
7 2 15
1 10 7
3 3
1 5 3
2 6 1
7 -1 -3
3 2
3 6
-1 1
3 1		 3 2
7 14
3 19
13 38
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
4 4
1 0 0 0
0 1 0 0
0 0 1 0		 4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
3 3
5 7 -1
8 9 3
0 -6 17
2 3
7 -15 1
8 8 2		 -1
2 3
57 -49 31
89 11 -37
3 1
19
-19
0		 2 1
2014
1482

Код программы

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Умножение матриц на Wikipedia

Класс для хранения матриц

by

2

Задача

Напишите класс для хранения матриц и реализуйте основные операции работы с ними.

Тесты

№ Операция Входная матрица А Входная   матрица В Результат
 1 Транспони-рования 33 34 12
33 19 10
12 14 17
84 24 51
43 71 21		 — 33 33 12 84 43
34 19 14 24 71
12 10 17 51 21
 2 Сложения -1   1   -1
1   -1   1
-1   1   -1		 1   -1   1
-1    1  -1
1   -1   1		 0   0   0
0   0   0
0   0   0
 3 Вычитания -1   1   -1
1   -1   1
-1   1   -1		 1   -1   1
-1    1  -1
1   -1   1		 -2   2   -2
2   -2   2
-2   2   -2
 4 Умножения 33  34  12
33  19  10
12  14  17
84  24  51
43  71  21		 10  11  34  55
33  45  17  81
45  63  12  16		 1992 2649 1844 4761
1407 1848 1565 3514
1347  1833 850 2066
3927 5217 3876 7380
3718 4991 2921 8452

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Класс  Matrix  имеет следующие поля:  n, m  — размеры основной матрицы, и сама матрица  mainMatrix , представлена в виде двумерного массива целочисленного типа. Также данный класс имеет два конструктора: первый из которых принимает как параметры размеры создаваемой матрицы public Matrix(int n, int m) , второй же принимает как параметр двумерный массив(матрицу)  public Matrix(int [][] paramMatrix) .

Данный класс имеет следующие методы:

  1. public int getElement(int n, int m)  — метод для получения элемента матрицы по индексам;
  2. public void setElement(int n, int m, int value)  — метод задания элемента по индексам;
  3. public int getVerticalLength() — метод получения количества строк в матрице;
  4. public int getHorizontalLength()  — метод получения количества столбцов в матрице;
  5. public void fillRandomValues()  — метод заполнения матрицы рандомными значениями;
  6. public void displayMatrix()  — метод вывода матрицы;
  7. public static int[][] transpone(int[][] paramMatrix)  — метод транспонирования матрицы, с двумерным массивом как параметр;
  8. public static Matrix transpone(Matrix paramMatrix)  — метод транспонирования матрицы, с объектом класса  Matrix , как параметр;
  9. public static Matrix add(Matrix first, Matrix second)  — метод нахождения суммы двух матриц;
  10. public static Matrix subtract (Matrix first, Matrix second)  — метод вычитания одной матрицы из другой;
  11. public static Matrix multiply (Matrix first, Matrix second)  — метод произведения двух матриц.

Для последних трех методов был написан псевдокласс NotEqualLengthsOfMatrixException  наследник класса  Exception , чтобы при несовпадении размеров заданных матриц генерировать исключительную ситуацию.