Java для начинающих: решаем задачу умножения матриц

Для тех, кто только начинает учиться программировать на языке Java, часто бывает непросто найти задачу по плечу — и чтобы научиться чему-то новому, и чтобы не застрять где-то посередине задачи, разбираясь с подводными камнями.

В этой статье я покажу пример задачи, которая более-менее подходит к этим требованиям. Мы немного потренируемся в реализации алгоритмов, использующих циклы, а также в использовании консольного ввода-вывода. Нам потребуются математические знания на уровне школьной математики, а для реализации я буду использовать JDK 11.

Сергей Чеботарев

Наставник на курсе «Java-разработчик»

Алгоритм умножения матриц

В математике есть понятие числовой матрицы. Условно говоря, это таблица, заполненная числами:

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 столбцов.

Сокращённо:

A^{m х  n} * B^{n х k} = M^{m х k}

При этом ячейки матрицы-результата будут вычисляться вот так (1-й индекс — номер строки, 2-й — номер столбца):

M_{p,q} = \sum_{i=1}^{n} A_{p,i} * B_{i,q}

Таким образом, числа очередной строки первой матрицы перемножаются на соответствующие числа очередного столбца второй матрицы и получившиеся произведения складываются. Например, перемножим эти матрицы 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:

Посчитаем ячейку

M_{1,1}= 1*9 + 2*7 + 3*5 + 4*3 = 50

1 2 3 4
5 6 7 8

*

9 8 4
7 6 3
5 4 2
3 2 1

Результат записываем в матрицу:

50

Далее, ячейка

M_{1,2}= 1*8 + 2*6 + 3*4 + 4*2 = 40

1 2 3 4
5 6 7 8

*

9 8 4
7 6 3
5 4 2
3 2 1

Матрица становится вот такой:

50

40

И так далее, получим:

50

40

20

146

120

60

Рассмотрев данный несложный алгоритм, идём дальше.

Требования к программе

Наша учебная цель — написать на 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(&quot;1я матрица:&quot;);     final var matrixA = inputMatrix(scanner);     System.out.println(&quot;2я матрица:&quot;);     final var matrixB = inputMatrix(scanner);     final var matrixM = multiply(matrixA, matrixB);     if (matrixM == null) {         return;     } System.out.println(&quot;Матрица-результат:&quot;);     final var len = max_len(matrixM);     final var format = &quot;%&quot; + len + &quot;.&quot; + len + &quot;s &quot;;     for (var i = 0; i &lt; matrixM.length; i++) {         for (var j = 0; j &lt; 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 &lt; m.length; i++) {         for (var j = 0; j &lt; m[0].length; j++) {             if (m[i][j] &gt; 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(&quot;Эти матрицы нельзя перемножить&quot;);         return null;     }     final var matrixM = new int[matrixA.length][matrixB[0].length];     for (var i = 0; i &lt; matrixM.length; i++) {         for (var j = 0; j &lt; matrixM[0].length; j++) {             matrixM[i][j] = 0;             for (var k = 0; k &lt; matrixA[0].length; k++) {                 matrixM[i][j] += matrixA[i][k] * matrixB[k][j];             }         }     }     return matrixM; }  static int[][] inputMatrix(final Scanner scanner) {     System.out.println(&quot;Введите количество строк матрицы:&quot;);     final var rows = scanner.nextInt();     System.out.println(&quot;Введите количество столбцов матрицы:&quot;);     final var cols = scanner.nextInt();     final var matrixA = new int[rows][cols];     System.out.println(&quot;Введите матрицу:&quot;);     for (var i = 0; i &lt; rows; i++) {         for (var j = 0; j &lt; 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  

Готово! Разумеется, эта реализация не является идеальной — в ней есть недостатки. Например, можно поэкспериментировать с неверным пользовательским вводом и подумать, как правильно обрабатывать ошибки, которые из-за него возникают.

Если считаете, что нужно что-то улучшить, то можете реализовать эти улучшения, а я готов обсудить их в комментариях 🙂


ссылка на оригинал статьи https://habr.com/ru/company/yandex_praktikum/blog/723510/

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *