Задача
Пусть даны две прямоугольные матрицы $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