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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

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

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

Кто нибудь может скинуть код произведения матриц со сложностью O(n^2)? Никак не получается решить задачу со стандартной функцией, Time Limit (
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.08.2011, 12:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Произведение матриц O(n^2) (C++):

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

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

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

Произведение матриц - C++
Вобщем вот задача:"Напишите перегружаемую функцию product, которая возвращает произведение вещественных квадратных матриц либо комплексных...

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

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

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

Добавлено через 2 минуты
Grizlik78, еще раз простите за xor, глупо вышло
0
AvengerAlive
5 / 5 / 0
Регистрация: 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
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
09.08.2011, 13:14 #5
AvengerAlive, проблема в том, что нам предлагается решить не ту задачу, которую нужно решить на самом деле. Вдруг оказалось, что надо не перемножить матрицы, а проверить на равенство AB и С.
Может задачу покажешь?
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
09.08.2011, 13:18 #6
Иногда можно столбцы первой матрицы превратить в обычные числа, а умножение будет линейной комбинацией этих чисел
0
AvengerAlive
5 / 5 / 0
Регистрация: 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
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
09.08.2011, 14:16 #8
После умножения на вектор равенство результатов, конечно, не гарантирует равенства исходных матриц. Но если я правильно понял, проблема не в том, что перемножение матриц медленное, а в том, что проверить надо много матриц.
В этом случае умножение на вектор позволит отсечь заведомо неравные матрицы, а если полученные вектора равны, то тогда уж можно провести полную проверку перемножением двух матриц.
Только для предварительной проверки я бы, наверное, брал вектор, состоящий из всех единиц. То есть, по сути, надо найти суммы для каждой строки.
Хотя на специально подобранных данных мой метод будет даже медленнее прямого
Ну и переполнение 32-битного int с заданными ограничениями получить не так уж сложно.
0
AvengerAlive
5 / 5 / 0
Регистрация: 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
grizlik78
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
09.08.2011, 15:41 #10
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Но этот метод неверный, или в коде ошибка, точно не знаю.
И реализовал неправильно (как-минимум невооружённым глазом видно выход за границу массива) и, похоже, понял тоже не полностью. Если вектора после перемножений не равны, то это однозначно указывает на неравенство матриц. Если же вектора равны, то матрицы могут быть не равны, поэтому придётся перемножать для гарантии (тут, в общем-то, тоже можно поколдовать).
0
AvengerAlive
5 / 5 / 0
Регистрация: 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
09.08.2011, 16:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.08.2011, 16:12
Привет! Вот еще темы с ответами:

Найти произведение матриц - C++
Даны две матрицы. Найти произведение матриц. Размерности массивов, где хранятся матрицы, должны соответствовать правилам умножения матриц ...

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

Найти произведение матриц - C++
1)Даны матрицы А и В размера k×m и m×l соответственно. Найти произведение АВ. Перемножение матриц реализовать в виде функции.

Произведение двух матриц - C++
Произведение двух матриц, помогите пожалуйста написать код программы, нужно срочно


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru