Задача
Пусть даны две прямоугольные матрицы $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 |
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int na = scanner.nextInt(); int ma = scanner.nextInt(); int[][] a = new int[na][ma]; for (int i = 0; i < na; i++) { for (int j = 0; j < ma; j++) { a[i][j] = scanner.nextInt(); } } int nb = scanner.nextInt(); int mb = scanner.nextInt(); if (ma != nb) { System.out.print(-1); return; } int[][] b = new int[nb][mb]; for (int i = 0; i < nb; i++) { for (int j = 0; j < mb; j++) { b[i][j] = scanner.nextInt(); } } int[][] c = new int[na][mb]; for (int i = 0; i < na; i++) { for (int j = 0; j < mb; j++) { for (int r = 0; r < ma; r++) { c[i][j] += a[i][r] * b[r][j]; } } } System.out.print(na + " " + mb + "\n"); for (int i = 0; i < na; i++) { for (int j = 0; j < mb; j++) { System.out.print(c[i][j]); if (j + 1 != mb) System.out.print(" "); } System.out.print("\n"); } } } |
Решение
Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C$.
Ссылки
Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Умножение матриц на Wikipedia