Произведение матриц O(n^2)

@AvengerAlive · Регистрация: 30.07.2011

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

Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (

@grizlik78 · 09.08.2011, 12:59

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

Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)?

Для (квадратных) матриц общего вида вряд ли такое возможно. Может у матриц есть какие-то особенности?

@Olga_ · 09.08.2011, 13:05

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

Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (

А под n подразумевается количество умножений?

Добавлено через 2 минуты
Grizlik78, еще раз простите за xor, глупо вышло

@AvengerAlive · 09.08.2011, 13:09 **[ТС]**

grizlik78, Матрица квадратная. Ну вообще то прочитав разбор задачи там посоветовали взять вектор из 0 и 1 и перемножить B и С на него, потом A на полученный из B. Потом сравнить. Если равны то с вероятностью 50% AB=C. Но это тупо. Если поменять число там где 0 в векторе то он покажет что они равны. А вектор 010101... брать тоже глупо по той же причине. Генератор чисел rand()%2 тоже, может сгенерировать 0000... Что делать не пойму.

Olga_, n это размер матрицы, но в таких случаях это количество операций.

@grizlik78 · 09.08.2011, 13:14

AvengerAlive, проблема в том, что нам предлагается решить не ту задачу, которую нужно решить на самом деле. Вдруг оказалось, что надо не перемножить матрицы, а проверить на равенство AB и С.
Может задачу покажешь?

@Olga_ · 09.08.2011, 13:18

Иногда можно столбцы первой матрицы превратить в обычные числа, а умножение будет линейной комбинацией этих чисел

@AvengerAlive · 09.08.2011, 13:31 **[ТС]**

Вот условие:

В лесу графини Мордвиновой. Петергоф. 1891. С годами у художника развилось обостренное цветовое видение. Теперь он видит и может передать кистью изменчивость цветов в зависимости от освещения и от рефлексов соседних предметов. Живописец выписывает мягкие переходы зеленых, желтоватых и сероватых оттенков стволов елей, хвои и мха. Но тонкие колористические изменения не самоцель для художника: ими он стремится донести до зрителя реальную жизнь природы. Картина вызывает у зрителя впечатление, что он находится внутри лесного пространства, дает прочувствовать окружающую атмосферу сосновой чащобы.

Даны три квадратные матрицы A, B, C, каждая из которых имеет размер n х n. Необходимо проверить равенство: A х B = C.

Технические условия
Входные данные

Каждый тест начинается значением n (n ≤ 500). Далее следуют три матрицы A, B, C, каждая из которых представляется n строками, содержащих в точности n чисел. Элементы матриц А и В по модулю не превышают 1000. Последний тест содержит n = 0 и не обрабатывается. Например, в первом тесте следует проверить равенство

Выходные данные

Для каждого теста в отдельной строке вывести "YES" или "NO" в зависимости от того, имеет ли место равенство A х B = C или нет.

Информация о задаче
Лимит времени: 3 секунды
Лимит памяти: 64 MB

Пример
Пример входных данных
2
1 2
3 4
1 3
2 3
5 9
11 21
2
1 2
3 4
1 3
2 3
5 9
10 21
0
Пример выходных данных
YES
NO

@grizlik78 · 09.08.2011, 14:16

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

Ну и переполнение 32-битного int с заданными ограничениями получить не так уж сложно.

@AvengerAlive · 09.08.2011, 15:29 **[ТС]**

grizlik78, написал с единичным вектором

C++

#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
 
int main()
{
 int n,i,j,t,v;
 int a[500][500];
 bool ok;
 while (cin >> n)
  {
   if (!n) break;
   ok=true;
   for (i=0; i<n; i++)
   for (j=0; j<n; j++)
   cin >> a[i][j];
   for (i=0; i<n; i++) 
    { 
     v=0;
     for (j=0; j<n; j++) 
      {
       cin >> t; v+=t; 
      } 
     for (j=0; j<n; j++) { a[j][i]*=v; a[j][i]+=a[j][i-1]; }
    }
   for (i=0; i<n; i++) 
    {
     v=0;
     for (j=0; j<n; j++) 
      {
       cin >> t; v+=t; 
      } 
     if (v!=a[i][n-1]) ok=false;
    }
   if (!ok) cout << "NO" << endl;
   else cout << "YES" << endl;
  }
 return 0;
}

Но этот метод неверный, или в коде ошибка, точно не знаю.

@grizlik78 · 09.08.2011, 15:41

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

Но этот метод неверный, или в коде ошибка, точно не знаю.

И реализовал неправильно (как-минимум невооружённым глазом видно выход за границу массива) и, похоже, понял тоже не полностью. Если вектора после перемножений не равны, то это однозначно указывает на неравенство матриц. Если же вектора равны, то матрицы могут быть не равны, поэтому придётся перемножать для гарантии (тут, в общем-то, тоже можно поколдовать).

@AvengerAlive · 09.08.2011, 16:12 **[ТС]**

C++

#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
 
int main()
{
 int n,i,j,t,v;
 int a[500][500];
 bool ok;
 while (cin >> n)
  {
   if (!n) break;
   ok=true;
   for (i=0; i<n; i++)
   for (j=0; j<n; j++)
   cin >> a[i][j];
   v=0;
   for (j=0; j<n; j++) 
    {
     cin >> t; v+=t; 
    }
   for (j=0; j<n; j++) a[j][0]*=v;  
   for (i=1; i<n; i++) 
    {
     v=0;
     for (j=0; j<n; j++) 
      {
       cin >> t; v+=t; 
      } 
     for (j=0; j<n; j++) { a[j][i]*=v; a[j][i]+=a[j][i-1]; }
    }
   for (i=0; i<n; i++) 
    {
     v=0;
     for (j=0; j<n; j++) 
      {
       cin >> t; v+=t; 
      } 
     if (v!=a[i][n-1]) ok=false;
    }
   if (!ok) cout << "NO" << endl;
   else cout << "YES" << endl;
  }
 return 0;
}

Даже так сделал, суть не в этом, лимит времени исчерпывает.

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
		1
	Произведение матриц O(n^2) 09.08.2011, 12:50. Показов 1544. Ответов 10 Метки нет (Все метки) Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit ( 0

@grizlik78 2380 / 1664 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	09.08.2011, 12:59	2
	Сообщение от AvengerAlive Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Для (квадратных) матриц общего вида вряд ли такое возможно. Может у матриц есть какие-то особенности? 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	09.08.2011, 13:05	3
	Сообщение от AvengerAlive Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit ( А под n подразумевается количество умножений? Добавлено через 2 минуты Grizlik78, еще раз простите за xor, глупо вышло 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	09.08.2011, 13:09 [ТС]	4
	grizlik78, Матрица квадратная. Ну вообще то прочитав разбор задачи там посоветовали взять вектор из 0 и 1 и перемножить B и С на него, потом A на полученный из B. Потом сравнить. Если равны то с вероятностью 50% AB=C. Но это тупо. Если поменять число там где 0 в векторе то он покажет что они равны. А вектор 010101... брать тоже глупо по той же причине. Генератор чисел rand()%2 тоже, может сгенерировать 0000... Что делать не пойму. Olga_, n это размер матрицы, но в таких случаях это количество операций. 0

@grizlik78 2380 / 1664 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	09.08.2011, 13:14	5
	AvengerAlive, проблема в том, что нам предлагается решить не ту задачу, которую нужно решить на самом деле. Вдруг оказалось, что надо не перемножить матрицы, а проверить на равенство AB и С. Может задачу покажешь? 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	09.08.2011, 13:18	6
	Иногда можно столбцы первой матрицы превратить в обычные числа, а умножение будет линейной комбинацией этих чисел 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	09.08.2011, 13:31 [ТС]	7
	Вот условие: В лесу графини Мордвиновой. Петергоф. 1891. С годами у художника развилось обостренное цветовое видение. Теперь он видит и может передать кистью изменчивость цветов в зависимости от освещения и от рефлексов соседних предметов. Живописец выписывает мягкие переходы зеленых, желтоватых и сероватых оттенков стволов елей, хвои и мха. Но тонкие колористические изменения не самоцель для художника: ими он стремится донести до зрителя реальную жизнь природы. Картина вызывает у зрителя впечатление, что он находится внутри лесного пространства, дает прочувствовать окружающую атмосферу сосновой чащобы. Даны три квадратные матрицы A, B, C, каждая из которых имеет размер n х n. Необходимо проверить равенство: A х B = C. Технические условия Входные данные Каждый тест начинается значением n (n ≤ 500). Далее следуют три матрицы A, B, C, каждая из которых представляется n строками, содержащих в точности n чисел. Элементы матриц А и В по модулю не превышают 1000. Последний тест содержит n = 0 и не обрабатывается. Например, в первом тесте следует проверить равенство Выходные данные Для каждого теста в отдельной строке вывести "YES" или "NO" в зависимости от того, имеет ли место равенство A х B = C или нет. Информация о задаче Лимит времени: 3 секунды Лимит памяти: 64 MB Пример Пример входных данных 2 1 2 3 4 1 3 2 3 5 9 11 21 2 1 2 3 4 1 3 2 3 5 9 10 21 0 Пример выходных данных YES NO 0

@grizlik78 2380 / 1664 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	09.08.2011, 14:16	8
	После умножения на вектор равенство результатов, конечно, не гарантирует равенства исходных матриц. Но если я правильно понял, проблема не в том, что перемножение матриц медленное, а в том, что проверить надо много матриц. В этом случае умножение на вектор позволит отсечь заведомо неравные матрицы, а если полученные вектора равны, то тогда уж можно провести полную проверку перемножением двух матриц. Только для предварительной проверки я бы, наверное, брал вектор, состоящий из всех единиц. То есть, по сути, надо найти суммы для каждой строки. Хотя на специально подобранных данных мой метод будет даже медленнее прямого Ну и переполнение 32-битного int с заданными ограничениями получить не так уж сложно. 0

@grizlik78 2380 / 1664 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	09.08.2011, 15:41	10
	Сообщение от AvengerAlive Но этот метод неверный, или в коде ошибка, точно не знаю. И реализовал неправильно (как-минимум невооружённым глазом видно выход за границу массива) и, похоже, понял тоже не полностью. Если вектора после перемножений не равны, то это однозначно указывает на неравенство матриц. Если же вектора равны, то матрицы могут быть не равны, поэтому придётся перемножать для гарантии (тут, в общем-то, тоже можно поколдовать). 0

	09.08.2011, 16:12

Опции темы