Умножение матриц

@xolyspirit · Регистрация: 04.10.2013

Студворк — интернет-сервис помощи студентам

Помогите найти ошибку плз.
Задание:
Аня недавно узнала, что такое квадратная матрица размерности n. Это таблица n×n с целыми числами в ячейках. Число, стоящее на пересечении i-ой строки и j-ого столбца матрицы A, кратко обозначается A[i, j]. Матрицы можно умножать, и Аня быстро освоила, как запрограммировать эту операцию с помощью циклов. Результатом умножения двух матриц A и B будет матрица C, элементы которой определяются следующим образом:

Матрицы ей понадобились для конкретной задачи, в которой надо узнать определенный элемент произведения нескольких матриц. Это уже достаточно сложная задача для Ани, но она усложняется тем, что все вычисления ведутся по модулю некоторого простого числа p, то есть если при арифметических операциях получается число, большее, либо равное p, оно заменяется на остаток при делении на p.

Помогите Ане вычислить нужный ей элемент.

Входные данные
В первой строчке входного файла INPUT.TXT стоят два числа: m - количество матриц, n - размер каждой из матриц (1 ≤ m ≤ 130, 1 ≤ n ≤ 130). В следующей строчке содержатся номер строки и столбца, интересующего Аню элемента 1 ≤ a ≤ n, 1 ≤ b ≤ n. В третьей строке содержится простое число p ≤ 1000. Далее следует описание m матриц. Описание каждой матрицы состоит из n строк. В каждой из строк содержится n неотрицательных целых чисел, меньших p. Соседние числа в строке разделены пробелом, а перед каждой матрицей пропущена строка.

Выходные данные
В выходной файл OUTPUT.TXT выведите нужный Ане элемент произведения матриц.

при ручном тестировании все работает - программа выдает правильные ответы.
А вот при автоматическим тестировании через сайт - выдает неправильный ответ.
Подозреваю подвох где то в работе с потоками, но никак не могу обнаружить где именно.
Заранее спасибо

Java
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package solution;
 
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
 
public class Main {
    public int n;
    public int p;
 
    public static void main(String[] args) throws IOException {
    Main main = new Main();
    main.matrixMultiplication();
    }
 
    private void matrixMultiplication() throws IOException {
        //define veriables
        Scanner scanner = new Scanner(new File("INPUT.TXT"));
        int m = scanner.nextInt();
        n = scanner.nextInt();
        int line = scanner.nextInt()-1;
        int column = scanner.nextInt()-1;
        p = scanner.nextInt();
        int[][] c;
        int[][][] allMatrix = new int[m][n][n];
 
        //init start matrix
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    allMatrix[i][j][k] = scanner.nextInt();
                }
            }
        }
        c = allMatrix[0];
        for (int i = 1; i <m; i++) {
            c = mult(c,allMatrix[i]);
        }
 
        FileWriter writer = new FileWriter("OUTPUT.TXT");
        writer.write(String.valueOf(c[line][column]));
        writer.close();
    }
 
    private int[][] mult(int[][] a, int[][] b){
        int n = a.length;
        int[][] c = new int[n][n];
 
        //multiply matrix
        for (int i = 0; i <n; i++) {
            new Thread(new Mythread(i,a,b,c)).start();
        }
        return c;
    }
 
    class Mythread implements Runnable{
        private int result;
        private int i;
        private int[][] a;
        private int[][] b;
        private int[][] c;
 
        public Mythread(int i,int[][] a,int[][] b, int[][] c){
        this.i = i;
        this.a = a;
        this.b = b;
        this.c = c;
        }
 
        @Override
        public void run() {
            for (int j = 0; j <n; j++) {
                result = 0;
                for (int k = 0; k <n; k++) {
                    result+= a[i][k] * b[k][j];
                }
                if(result>=p){
                    result  = result%p;
                }
                c[i][j] =result;
            }
        }
    }
}

@iSmokeJC · 27.01.2018, 18:58

Сообщение от xolyspirit

Подозреваю подвох где то в работе с потоками

А зачем здесь потоки?

@xolyspirit · 27.01.2018, 19:00 **[ТС]**

Нужно выполнить умножение очень быстро.
Рассчитываю что потоки ускорят процесс.

@iSmokeJC · 27.01.2018, 19:06

xolyspirit, вроде нужен один элемент, зачем матрицы целиком перемножать?

@xolyspirit · 27.01.2018, 19:08 **[ТС]**

мысль интересная, но слабо представляю как ее реализовать

@iSmokeJC · 27.01.2018, 19:13

Считываешь матрицу, берешь нужный элемент в переменную, считываешь следующую матрицу, берешь нужный элемент, перемножаешь, считываешь следующую....

Добавлено через 40 секунд
Один цикл

Добавлено через 2 минуты
Кидани сюда пример входного файла

@xolyspirit · 27.01.2018, 19:18 **[ТС]**

3 2
1 2
239

1 2
3 4

4 2
1 3

1 2
2 1

Кажись понял, сейчас попробую реализовать

@iSmokeJC · 27.01.2018, 19:27

Я думал, там матриц 100500

Добавлено через 6 минут
xolyspirit, смотри -
дано: 3 матрицы, 2х2
нужный элемент - [1][2]
это как? считают с 1?

@xolyspirit · 27.01.2018, 19:28 **[ТС]**

да, считают с 1.
это 1 строка 2 столбик

@iSmokeJC · 27.01.2018, 19:30

Ну, тогда типа...

Java
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
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("test.txt"));
        int m = scanner.nextInt();              //Kол-во матриц
        int n = scanner.nextInt();              //Размер
        int row = scanner.nextInt() - 1;
        int col = scanner.nextInt() - 1;
        int p = scanner.nextInt();              //Модуль
 
        int res = 1;
        for (int i = 0; i < m; i++) {
            int[][] matrix = new int[n][n];
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    matrix[j][k] = scanner.nextInt();
                }
            }
            res *= matrix[row][col];
            if (res >= p) res %= p;
        }
        System.out.println(res);
    }
}

@xolyspirit · 27.01.2018, 19:33 **[ТС]**

Это же матрицы. Их нельзя так умножать.
Надо умножать всю строку на весь столбик

@iSmokeJC · 27.01.2018, 19:35

Можно вообще матрицы не считывать, кстати

Добавлено через 1 минуту
xolyspirit, я лошара, согласен

@xolyspirit · 27.01.2018, 20:04 **[ТС]**

идеи закончились?)

@iSmokeJC · 27.01.2018, 20:08

Идея та же, формулу поменять надо

@korvin_ · 27.01.2018, 22:22

Сообщение от xolyspirit

Нужно выполнить умножение очень быстро.
Рассчитываю что потоки ускорят процесс.

Зря расчитываешь.

Сообщение от xolyspirit

3 2
1 2
239
1 2
3 4
4 2
1 3
1 2
2 1

Серьёзно? Для этого потоки?

@xolyspirit · 27.01.2018, 23:14 **[ТС]**

Ну это ведь просто набор для образца. Во время тестирования там совсем другого размера наборы, но составленные по тем же правилам.

Добавлено через 2 минуты
Вариант с потоками и меня вполне получился. На моей машине запускается и отрабатывает норм, а вот во время тестирования на сервера почему то бросает рантайм.

Java
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
 
public class Main {
    public int n;
    public int p;
 
    public static void main(String[] args) throws IOException {
    Main main = new Main();
    main.matrixMultiplication();
    }
 
    private void matrixMultiplication() throws IOException {
        //define veriables
        Scanner scanner = new Scanner(new File("INPUT.TXT"));
        int m = scanner.nextInt();
        n = scanner.nextInt();
        int line = scanner.nextInt()-1;
        int column = scanner.nextInt()-1;
        p = scanner.nextInt();
        int[][] c;
        int[][][] allMatrix = new int[m][n][n];
 
        //init start matrix
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    allMatrix[i][j][k] = scanner.nextInt();
                }
            }
        }
        c = allMatrix[0];
        for (int i = 1; i <m; i++) {
            c = mult(c,allMatrix[i]);
        }
 
        FileWriter writer = new FileWriter("OUTPUT.TXT");
        writer.write(String.valueOf(c[line][column]));
        writer.close();
    }
 
    private int[][] mult(int[][] a, int[][] b){
        int n = a.length;
        int[][] c = new int[n][n];
 
        //multiply matrix
        for (int i = 0; i <n; i++) {
            new Thread(new Mythread(i,a,b,c)).start();
        }
        return c;
    }
 
    class Mythread implements Runnable{
        private int result;
        private int i;
        private int[][] a;
        private int[][] b;
        private int[][] c;
 
        public Mythread(int i,int[][] a,int[][] b, int[][] c){
        this.i = i;
        this.a = a;
        this.b = b;
        this.c = c;
        }
 
        @Override
        public void run() {
            for (int j = 0; j <n; j++) {
                result = 0;
                for (int k = 0; k <n; k++) {
                    result+= a[i][k] * b[k][j];
                }
                if(result>=p){
                    result  = result%p;
                }
                c[i][j] =result;
            }
        }
    }
}

Добавлено через 35 минут
Есть еще один вариант этой программы. Но он тоже почему то бросает рантайм на сервере.

Java
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package solution;
 
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
 
public class Test {
    public static int count = 0;
    public static int p;
 
    public static void main(String[] args) throws IOException {
        matrixMultiplication();
    }
 
    private static void matrixMultiplication() throws IOException {
        //define veriables
        Scanner scanner = new Scanner(new File("INPUT.TXT"));
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int line = scanner.nextInt() - 1;
        int column = scanner.nextInt() - 1;
        p = scanner.nextInt();
        int answer = 0;
        int[][] c, lastMatr;
        int[][][] allMatrix = new int[m - 1][n][n];
        lastMatr = new int[n][n];
        //init start matrix
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    allMatrix[i][j][k] = scanner.nextInt();
                }
            }
        }
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                lastMatr[j][k] = scanner.nextInt();
            }
        }
        c = mult(allMatrix);
        answer = sumRowCol(line, column, c, lastMatr);
        FileWriter writer = new FileWriter("OUTPUT.TXT");
        writer.write(String.valueOf(answer));
        writer.close();
    }
 
    private static int[][] mult(int[][]... args) {
        int n = args[0].length;
        final int[][][] m1 = {new int[n][n]};
        final int[][][] m2 = {new int[n][n]};
 
        if (args.length > 2) {
            int half = args.length / 2;
            half = args.length % 2 == 0 ? half : ++half;
 
            int[][][] c1 = new int[half][n][n];
            int[][][] c2 = new int[args.length - half][][];
 
            for (int i = 0; i < half; i++) {
                c1[i] = args[i];
            }
            for (int i = 0; i < args.length - half; i++) {
                c2[i] = args[i + half];
            }
 
            m1[0] = mult(c1);
            if (!(args.length - half == 1)) {
                m2[0] = mult(c2);
            } else {
                return multiply(m1[0], c2[0]);
            }
            return multiply(m1[0], m2[0]);
        }
        return multiply(args[0], args[1]);
    }
 
    private static int[][] multiply(int[][] a, int[][] b) {
        int n = a.length;
        int[][] c = new int[n][n];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = sumRowCol(i, j, a, b);
            }
        }
        return c;
    }
 
    private static int sumRowCol(int row, int col, int[][] m1, int[][] m2) {
        int res = 0;
        for (int i = 0; i < m1.length; i++) {
            res += m1[row][i] * m2[i][col];
            count++;
        }
        if (res >= p) {
            res %= p;
        }
        return res;
    }
}

@КОП · 28.01.2018, 02:27

Сообщение от xolyspirit

Нужно выполнить умножение очень быстро.
Рассчитываю что потоки ускорят процесс.

ты содаешь каждую итерацию ровно один поток получая накладные расходы на его создание. При этом всем программа все равно работает в 1 поток, так как ты ждешь результата выполнения каждого из них. Итог - отрицательная оптимизация.

Далее, у тебя по итогу сложность алгоритма О(m*n*n*n), хотя если порисуешь на бумажке как все вычисляется, быть может придешь к О(m*n*n)

И последнее, BufferedReader вместо Scanner. Разница мягко говоря на порядок. В 10м тесте одно только чтение выходит за таймлимит

@xolyspirit · 28.01.2018, 23:10 **[ТС]**

Спасибо, вечером попробую.

Добавлено через 15 часов 19 минут
Переделал под использование BufferedReaderа. Но явно опять что то сделал не так. ибо теперь приложение жрет уйму памяти.

Java
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
    matrixMultiplication();
    }
 
    private static void matrixMultiplication() throws IOException {
        //define veriables
        BufferedReader reader = new BufferedReader(new FileReader("INPUT.TXT"));
        StringBuilder str = new StringBuilder();
        String s;
            while((s = reader.readLine())!=null) {
                str.append(s).append(" ");
            }
            reader.close();
 
        String [] sar = str.toString().split(" ");
 
        int m = Integer.parseInt(sar[0]);
        int n = Integer.parseInt(sar[1]);
        int line = Integer.parseInt(sar[2])-1;
        int column = Integer.parseInt(sar[3])-1;
        int p = Integer.parseInt(sar[4]);
        int[][] c;
        int[][][] allMatrix = new int[m][n][n];
        int l = 6;
        //init start matrix
        for (; l <sar.length; ) {
            for (int i = 0; i < m ; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                         allMatrix[i][j][k] = Integer.parseInt(sar[l]);
                        l++;
                    }
                }
                l++;
            }
        }
        c = allMatrix[0];
        for (int i = 1; i <m; i++) {
            c = mult(c,allMatrix[i],p);
        }
 
        FileWriter writer = new FileWriter("OUTPUT.TXT");
        writer.write(String.valueOf(c[line][column]));
        writer.close();
    }
 
    private static int[][] mult(int[][] a, int[][] b, int p){
        int n = a.length;
        int result;
        int[][] c = new int[n][n];
        int[][] bt = new int[n][n];
 
        //multiply matrix
        for (int i = 0; i <n; i++) {
            for (int j = 0; j <n; j++) {
                result = 0;
                for (int k = 0; k <n; k++) {
                    result+= a[i][k] * b[k][j];
                }
                if(result>=p){
                    result %=p;
                }
                c[i][j] =result;
            }
        }
        return c;
    }
}

@КОП · 28.01.2018, 23:23

Сообщение от xolyspirit

Но явно опять что то сделал не так

Сообщение от КОП

Далее, у тебя по итогу сложность алгоритма О(m*n*n*n), хотя если порисуешь на бумажке как все вычисляется, быть может придешь к О(m*n*n)

буффер это лишь 50% нужных оптимизаций

@xolyspirit · 28.01.2018, 23:33 **[ТС]**

После оптимизации все заработало как надо.
Строки строит считывать по отдельности, так тратиться на порядок меньше памяти.
Всем советчикам - спасибо.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	27.01.2018, 19:00 [ТС]
	Нужно выполнить умножение очень быстро. Рассчитываю что потоки ускорят процесс. 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	27.01.2018, 19:06
	xolyspirit, вроде нужен один элемент, зачем матрицы целиком перемножать? 1

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	27.01.2018, 19:08 [ТС]
	мысль интересная, но слабо представляю как ее реализовать 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	27.01.2018, 19:13
	Считываешь матрицу, берешь нужный элемент в переменную, считываешь следующую матрицу, берешь нужный элемент, перемножаешь, считываешь следующую.... Добавлено через 40 секунд Один цикл Добавлено через 2 минуты Кидани сюда пример входного файла 0

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	27.01.2018, 19:18 [ТС]
	3 2 1 2 239 1 2 3 4 4 2 1 3 1 2 2 1 Кажись понял, сейчас попробую реализовать 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	27.01.2018, 19:27
	Я думал, там матриц 100500 Добавлено через 6 минут xolyspirit, смотри - дано: 3 матрицы, 2х2 нужный элемент - [1][2] это как? считают с 1? 0

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	27.01.2018, 19:28 [ТС]
	да, считают с 1. это 1 строка 2 столбик 0

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	27.01.2018, 19:33 [ТС]
	Это же матрицы. Их нельзя так умножать. Надо умножать всю строку на весь столбик 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	27.01.2018, 19:35
	Можно вообще матрицы не считывать, кстати Добавлено через 1 минуту xolyspirit, я лошара, согласен 0

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	27.01.2018, 20:04 [ТС]
	идеи закончились?) 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	27.01.2018, 20:08
	Идея та же, формулу поменять надо 0

@xolyspirit 1 / 1 / 1 Регистрация: 04.10.2013 Сообщений: 65
	28.01.2018, 23:33 [ТС]
	После оптимизации все заработало как надо. Строки строит считывать по отдельности, так тратиться на порядок меньше памяти. Всем советчикам - спасибо. 0

Умножение матриц

Решение