5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
1

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

09.08.2011, 12:50. Показов 1472. Ответов 10
Метки нет (Все метки)

Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.08.2011, 12:50
Ответы с готовыми решениями:

Транспонирование матриц. Произведение транспонированных матриц
Найти матрицу С: C=ATBTB; A=\begin{bmatrix}1\\ 1\\ 1\end{bmatrix} B=\begin{bmatrix}1 &...

Произведение матриц
Даны две матрицы. Получите их произведение.

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

Произведение матриц
Всем привет. Пожалуйста подскажите, в чем ошибка? #include <iostream> using namespace std; int...

10
Эксперт С++
2375 / 1659 / 279
Регистрация: 29.05.2011
Сообщений: 3,387
09.08.2011, 12:59 2
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)?
Для (квадратных) матриц общего вида вряд ли такое возможно. Может у матриц есть какие-то особенности?
0
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
09.08.2011, 13:05 3
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (
А под n подразумевается количество умножений?

Добавлено через 2 минуты
Grizlik78, еще раз простите за xor, глупо вышло
0
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
Эксперт С++
2375 / 1659 / 279
Регистрация: 29.05.2011
Сообщений: 3,387
09.08.2011, 13:14 5
AvengerAlive, проблема в том, что нам предлагается решить не ту задачу, которую нужно решить на самом деле. Вдруг оказалось, что надо не перемножить матрицы, а проверить на равенство AB и С.
Может задачу покажешь?
0
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
09.08.2011, 13:18 6
Иногда можно столбцы первой матрицы превратить в обычные числа, а умножение будет линейной комбинацией этих чисел
0
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
Эксперт С++
2375 / 1659 / 279
Регистрация: 29.05.2011
Сообщений: 3,387
09.08.2011, 14:16 8
После умножения на вектор равенство результатов, конечно, не гарантирует равенства исходных матриц. Но если я правильно понял, проблема не в том, что перемножение матриц медленное, а в том, что проверить надо много матриц.
В этом случае умножение на вектор позволит отсечь заведомо неравные матрицы, а если полученные вектора равны, то тогда уж можно провести полную проверку перемножением двух матриц.
Только для предварительной проверки я бы, наверное, брал вектор, состоящий из всех единиц. То есть, по сути, надо найти суммы для каждой строки.
Хотя на специально подобранных данных мой метод будет даже медленнее прямого
Ну и переполнение 32-битного int с заданными ограничениями получить не так уж сложно.
0
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
09.08.2011, 15:29  [ТС] 9
grizlik78, написал с единичным вектором

C++
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
#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;
}
Но этот метод неверный, или в коде ошибка, точно не знаю.
0
Эксперт С++
2375 / 1659 / 279
Регистрация: 29.05.2011
Сообщений: 3,387
09.08.2011, 15:41 10
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Но этот метод неверный, или в коде ошибка, точно не знаю.
И реализовал неправильно (как-минимум невооружённым глазом видно выход за границу массива) и, похоже, понял тоже не полностью. Если вектора после перемножений не равны, то это однозначно указывает на неравенство матриц. Если же вектора равны, то матрицы могут быть не равны, поэтому придётся перемножать для гарантии (тут, в общем-то, тоже можно поколдовать).
0
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
09.08.2011, 16:12  [ТС] 11
C++
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
#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;
}
Даже так сделал, суть не в этом, лимит времени исчерпывает.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.08.2011, 16:12
Помогаю со студенческими работами здесь

Произведение матриц
Вобщем вот задача:&quot;Напишите перегружаемую функцию product, которая возвращает произведение...

Найти произведение матриц
Дано: прямоугольные матрицы A и B. Найти произведение AB. Вычисление элемента матрицы AB оформить...

Найти произведение матриц
1)Даны матрицы А и В размера k×m и m×l соответственно. Найти произведение АВ. Перемножение матриц...

Найти произведение матриц
17. Найти произведение матриц A(5,7) и D(5.7)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru