Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.08.2011, 12:50     Произведение матриц O(n^2) #1
Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.08.2011, 12:50     Произведение матриц O(n^2)
Посмотрите здесь:

Найти произведение матриц C++
Произведение матриц C++
Произведение матриц C++
Получить матричное произведение матриц C++
Произведение двух матриц C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.08.2011, 12:59     Произведение матриц O(n^2) #2
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)?
Для (квадратных) матриц общего вида вряд ли такое возможно. Может у матриц есть какие-то особенности?
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.08.2011, 13:05     Произведение матриц O(n^2) #3
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (
А под n подразумевается количество умножений?

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

Olga_, n это размер матрицы, но в таких случаях это количество операций.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.08.2011, 13:14     Произведение матриц O(n^2) #5
AvengerAlive, проблема в том, что нам предлагается решить не ту задачу, которую нужно решить на самом деле. Вдруг оказалось, что надо не перемножить матрицы, а проверить на равенство AB и С.
Может задачу покажешь?
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.08.2011, 13:18     Произведение матриц O(n^2) #6
Иногда можно столбцы первой матрицы превратить в обычные числа, а умножение будет линейной комбинацией этих чисел
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.08.2011, 13:31  [ТС]     Произведение матриц O(n^2) #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
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.08.2011, 14:16     Произведение матриц O(n^2) #8
После умножения на вектор равенство результатов, конечно, не гарантирует равенства исходных матриц. Но если я правильно понял, проблема не в том, что перемножение матриц медленное, а в том, что проверить надо много матриц.
В этом случае умножение на вектор позволит отсечь заведомо неравные матрицы, а если полученные вектора равны, то тогда уж можно провести полную проверку перемножением двух матриц.
Только для предварительной проверки я бы, наверное, брал вектор, состоящий из всех единиц. То есть, по сути, надо найти суммы для каждой строки.
Хотя на специально подобранных данных мой метод будет даже медленнее прямого
Ну и переполнение 32-битного int с заданными ограничениями получить не так уж сложно.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.08.2011, 15:29  [ТС]     Произведение матриц O(n^2) #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;
}
Но этот метод неверный, или в коде ошибка, точно не знаю.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.08.2011, 15:41     Произведение матриц O(n^2) #10
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Но этот метод неверный, или в коде ошибка, точно не знаю.
И реализовал неправильно (как-минимум невооружённым глазом видно выход за границу массива) и, похоже, понял тоже не полностью. Если вектора после перемножений не равны, то это однозначно указывает на неравенство матриц. Если же вектора равны, то матрицы могут быть не равны, поэтому придётся перемножать для гарантии (тут, в общем-то, тоже можно поколдовать).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.08.2011, 16:12     Произведение матриц O(n^2)
Еще ссылки по теме:

C++ Транспонирование матриц. Произведение транспонированных матриц
Найти произведение матриц C++
C++ Найти произведение матриц

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

Или воспользуйтесь поиском по форуму:
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.08.2011, 16:12  [ТС]     Произведение матриц O(n^2) #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;
}
Даже так сделал, суть не в этом, лимит времени исчерпывает.
Yandex
Объявления
09.08.2011, 16:12     Произведение матриц O(n^2)
Ответ Создать тему
Опции темы

Текущее время: 05:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru