Java
В двумерном массиве arr[m][n], по соглашению, первое значение — количество строк, второе — столбцов.
Применение умножения матриц можно найти, например,при программировании поведения объектов в трехмерном пространстве.
public class MatrixMultiplection < public static void main(String[] args) < int[][] mA = , , , , >; int[][] mB = , , >; int m = mA.length; int n = mB[0].length; int o = mB.length; int[][] res = new int[m][n]; for (int i = 0; i < m; i++) < for (int j = 0; j < n; j++) < for (int k = 0; k < o; k++) < res[i][j] += mA[i][k] * mB[k][j]; >> > for (int i = 0; i < res.length; i++) < for (int j = 0; j < res[0].length; j++) < System.out.format("%6d ", res[i][j]); >System.out.println(); > > > /** Output: 1992 2649 1844 4761 1407 1848 1565 3514 1347 1833 850 2066 3927 5217 3876 7380 3718 4991 2921 8452 */ Данный алгоритм имеет сложность O(n 3 ). Алгоритм Копперсмита — Винограда может делать это за O(n 2.3727 ).
9 комментариев:
это не верное решение, в ответе количество строк матрицы «А» всегда равно количеству строк матрицы «В».
http://www.youtube.com/watch?v=llwuoLzPbdE
Ответить Удалить
Вы немного ошиблись. В ответе количество строк матрицы А должно быть равно количеству столбцов матрицы В. В данном случае в роли матрицы А у меня выступает ma2, а в роли B, соответственно ma1 Удалить
Перемножать можно матрицы А и В, если количество столбцов матрицы А равно количеству строк матрицы В. В данном примере размерность ma1 — 3 на 4, ma2 — 5 на 3, 4 не равно 5. Ошибка уже при инициализации матриц.
Размер результирующей матрицы, как верно было замечено, это количество строк матрицы А на количество столбцов матрицы В. Вторая ошибка в строке » int[][] res = new int[m][q];» :
m рассчитано как количество столбцов ma1, a q — как количество строк ma1.
Должно быть:
int a= ma1.length;
int b= ma2[0].length;
int[][] res = new int[a][b]; Ответить Удалить
Привет всем, я Иисус Маккинни из Техаса, и я просто хочу сказать очень громкое спасибо финансовым кредитным службам от Бенджамина Ли за их искренность, открытость, прозрачность, правдивость, любовь и поддержку во время и после получения от них ссуд. Я через многое прошел, и время не позволяет мне рассказать обо всем, через что я прошел онлайн в гостях или получить ссуду, чтобы получить дом здесь, в США, но Бог ответил на мои молитвы через поддержку и любовь со стороны Бенджамина Ли, который обнял меня и понял меня, несмотря на мои первоначальные сомнения и несерьезность, и с его добрым сердцем и любовью, я теперь являюсь владельцем дома через его 2 процентных ссудных фонда, и я клянусь распространить эту новость, а также рассказать миру, что все еще есть настоящие и Есть несколько хороших онлайн-кредитных компаний, которые могут помочь, а также оживить сухую кость. не упустите возможность послушать и прочитать это свидетельство, потому что это настоящий жизненный опыт, и любой, кто нуждается в таком изменении, не должен колебаться или сомневаться в этом потому что я доказал и клянусь богом на небесах, что эта история реальна, а также история моего опыта с ними. свяжитесь с ними сегодня. Текст в WhatsApp: (+1 989-394-3740) электронная почта: 247officedept@gmail.com Ответить Удалить
Java для начинающих: решаем задачу умножения матриц
Для тех, кто только начинает учиться программировать на языке Java, часто бывает непросто найти задачу по плечу — и чтобы научиться чему-то новому, и чтобы не застрять где-то посередине задачи, разбираясь с подводными камнями.
В этой статье я покажу пример задачи, которая более-менее подходит к этим требованиям. Мы немного потренируемся в реализации алгоритмов, использующих циклы, а также в использовании консольного ввода-вывода. Нам потребуются математические знания на уровне школьной математики, а для реализации я буду использовать JDK 11.
Сергей Чеботарев
Алгоритм умножения матриц
В математике есть понятие числовой матрицы. Условно говоря, это таблица, заполненная числами:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Для матриц доступна процедура умножения. Данная операция используется в различных алгоритмах машинного обучения, нейронных сетях и других областях. Как же это делается?
Во-первых, не всякие 2 матрицы можно перемножить. Для этого количество столбцов (=длине строки) первой матрицы должно совпадать с количеством строк (=длине столбца) второй матрицы. А правило, по которому их умножают, следующее:
При умножении матрицы A, размером m строк на n столбцов, и B, размером n строк на k столбцов, получаем матрицу M, размером m строк на k столбцов.
При этом ячейки матрицы-результата будут вычисляться вот так (1-й индекс — номер строки, 2-й — номер столбца):
Таким образом, числа очередной строки первой матрицы перемножаются на соответствующие числа очередного столбца второй матрицы и получившиеся произведения складываются. Например, перемножим эти матрицы A и B:
1 2 3 4 * 9 8 4 5 6 7 8 7 6 3 5 4 2 3 2 1 Так как у нас 2 строки в первой матрице и 3 столбца во второй, то такие будут и размеры матрицы-результата M:
1 2 3 4
5 6 7 8
9 8 4
7 6 3
5 4 2
3 2 1
Результат записываем в матрицу:
1 2 3 4
5 6 7 8
9 8 4
7 6 3
5 4 2
3 2 1
Матрица становится вот такой:
Рассмотрев данный несложный алгоритм, идём дальше.
Требования к программе
Наша учебная цель — написать на Java программу, которая будет работать в консоли, брать матрицы из ввода пользователя и выдавать на экран результат перемножения этих матриц.
Несмотря на то что алгоритм подсчёта довольно простой, нам предстоит решать проблемы, связанные с пользовательским вводом-выводом.
Как легче всего пользователю вводить числовые матрицы?
Мне представляется, что легче всего вводить их так, как мы их видим в тексте: между числами пробелы, каждая строка матрицы отделяется нажатием Enter.
Надо также учитывать, что пользователь может вводить разное количество пробелов между числами для того, чтобы матрицы выглядели красиво. Аналогично наша программа, выдавая результат, должна выравнивать числа так, чтобы числа из одного столбца были одно над другим, независимо от того, сколько цифр в числе.
Реализуем требования
Далее каждое требование будет реализовываться в отдельных методах. Я рекомендую делать так сразу, так как код в таком случае получается хорошо читабельным и его дальнейшее развитие (добавление новой функциональности, исправление ошибок) значительно упрощается.
Первым делом реализуем то, как пользователь будет вводить матрицы. Для этого нам понадобится класс java.util.Scanner. Сначала введём количество строк, затем количество столбцов, а потом уже сами числа матрицы:
static int[][] inputMatrix(final Scanner scanner) < System.out.println("Введите количество строк матрицы:"); final var rows = scanner.nextInt(); System.out.println("Введите количество столбцов матрицы:"); final var cols = scanner.nextInt(); final var matrixA = new int[rows][cols]; System.out.println("Введите матрицу:"); for (var i = 0; i < rows; i++) < for (var j = 0; j < cols; j++) < matrixA[i][j] = scanner.nextInt(); >> return matrixA; > Как видите, я оформил ввод матрицы как отдельный метод. Так как нам придётся ввести две матрицы, мы будем вызывать его 2 раза. Обратите внимание, что большинство требований по вводу реализованы с помощью использования класса Scanner из стандартной библиотеки Java, а не стандартного потока ввода. У него множество преимуществ, например, он учитывает, что пользователь может вводить разное количество пробелов между числами, и игнорирует их. Мы будем предполагать, что пользователь не ошибается при вводе данных (как минимум, не вводит слова вместо чисел).
Далее, нам понадобится функция, которая делает собственно умножение двух матриц. Реализуем это умножение через несколько вложенных циклов. Предварительно нам нужно будет проверить, можно ли перемножать данные нам матрицы:
static int[][] multiply(final int[][] matrixA, final int[][] matrixB) < if (matrixA[0].length != matrixB.length) < System.err.println("Эти матрицы нельзя перемножить"); return null; >final var matrixM = new int[matrixA.length][matrixB[0].length]; for (var i = 0; i < matrixM.length; i++) < for (var j = 0; j < matrixM[0].length; j++) < matrixM[i][j] = 0; for (var k = 0; k < matrixA[0].length; k++) < matrixM[i][j] += matrixA[i][k] * matrixB[k][j]; >> > return matrixM; > Здесь, очевидно, проверка размерности матриц достаточно упрощена. Мы проверяем размеры не всех строк, а только первой. Это сделано сознательно; если хочется, здесь можно расширить проверку.
Перемножив матрицы, теперь нам нужно вывести результат на экран. При этом нам нужно реализовать требование о том, что столбцы матрицы красиво выровнены, то есть при разной длине чисел все числа столбца будут строго один над другим. Для простоты мы можем посчитать, какое у нас максимальное число в матрице, и выравнивать согласно количеству цифр в нём (то есть если у нас максимальное число — трёхзначное, мы будем добавлять пробелы так, чтобы каждое число в матрице занимало на экране 3 знака). Для этого напишем функцию, которая будет вычислять количество цифр максимального числа:
private static int max_len(final int[][] m) < // Сначала вычислим максимальное число матрицы: var max = m[0][0]; for (var i = 0; i < m.length; i++) < for (var j = 0; j < m[0].length; j++) < if (m[i][j] >max) < max = m[i][j]; >> > // С помощью логарифма вычислим количество цифр в числе. Кто с ходу скажет, как это сделать проще? return Double.valueOf(Math.log10(max)).intValue() + 1; > С помощью форматирования текста, зная максимальную длину числа, мы теперь можем красиво вывести матрицу на экран:
final var len = max_len(matrixM); final var format = "%" + len + "." + len + "s "; for (var i = 0; i < matrixM.length; i++) < for (var j = 0; j < matrixM[0].length; j++) < System.out.printf(format, matrixM[i][j]); >System.out.println(); > Реализовав все требования, собираем программу воедино:
package ru.ya.prak; import java.util.Scanner; public class Matrixes < public static void main(final String[] args) < final var scanner = new Scanner(System.in); System.out.println("1я матрица:"); final var matrixA = inputMatrix(scanner); System.out.println("2я матрица:"); final var matrixB = inputMatrix(scanner); final var matrixM = multiply(matrixA, matrixB); if (matrixM == null) < return; >System.out.println("Матрица-результат:"); final var len = max_len(matrixM); final var format = "%" + len + "." + len + "s "; for (var i = 0; i < matrixM.length; i++) < for (var j = 0; j < matrixM[0].length; j++) < System.out.printf(format, matrixM[i][j]); >System.out.println(); > > private static int max_len(final int[][] m) < var max = m[0][0]; for (var i = 0; i < m.length; i++) < for (var j = 0; j < m[0].length; j++) < if (m[i][j] > max) < max = m[i][j]; >> > return Double.valueOf(Math.log10(max)).intValue() + 1; > private static int[][] multiply(final int[][] matrixA, final int[][] matrixB) < if (matrixA[0].length != matrixB.length) < System.err.println("Эти матрицы нельзя перемножить"); return null; >final var matrixM = new int[matrixA.length][matrixB[0].length]; for (var i = 0; i < matrixM.length; i++) < for (var j = 0; j < matrixM[0].length; j++) < matrixM[i][j] = 0; for (var k = 0; k < matrixA[0].length; k++) < matrixM[i][j] += matrixA[i][k] * matrixB[k][j]; >> > return matrixM; > static int[][] inputMatrix(final Scanner scanner) < System.out.println("Введите количество строк матрицы:"); final var rows = scanner.nextInt(); System.out.println("Введите количество столбцов матрицы:"); final var cols = scanner.nextInt(); final var matrixA = new int[rows][cols]; System.out.println("Введите матрицу:"); for (var i = 0; i < rows; i++) < for (var j = 0; j < cols; j++) < matrixA[i][j] = scanner.nextInt(); >> return matrixA; > > Запустим нашу программу и попробуем пересчитать наш пример из описания алгоритма:
1я матрица: Введите количество строк матрицы: 2 Введите количество столбцов матрицы: 4 Введите матрицу: 1 2 3 4 5 6 7 8 2я матрица: Введите количество строк матрицы: 4 Введите количество столбцов матрицы: 3 Введите матрицу: 9 8 4 7 6 3 5 4 2 3 2 1 Матрица-результат: 50 40 20 146 120 60 Готово! Разумеется, эта реализация не является идеальной — в ней есть недостатки. Например, можно поэкспериментировать с неверным пользовательским вводом и подумать, как правильно обрабатывать ошибки, которые из-за него возникают.
Если считаете, что нужно что-то улучшить, то можете реализовать эти улучшения, а я готов обсудить их в комментариях 🙂
