- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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
#include <iostream>
using namespace std;
int main()
{
int n, m, c, b, f = 0;
cin >> n >> m;
int A[n][m];
for(int i = 0; i < n; i++ )
{
for(int j = 0; j < m; j++)
{
cin >> A[i][j];
}
}
for(int i = 0; i < n; i++ )
{
b = A[i][0];
for(int j = 0; j < m; j++)
{
c = A[0][j];
for(int a = 0; a < n; a++)
{
if(c < A[0][a])
{
c = A[0][a];
}
}
for(int k = 0; k < m; k++)
{
if(b > A[k][0])
{
b = A[k][0];
}
}
if(b == c)
{
f++;
}
}
}
cout << f;
return 0;
}
Задана матрица K, содержащая n строк и m столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.
Вроде всё правильно, а выдаёт, что есть необработаное исключение.Что не так?
Follow us!
для матрицы судя по педивикии будет 9 седловых точек
Если бы 'n' являлось мерой стороны матрицы (т.е. величиной той же размерности, что и 'm' и 'n' в исходной постановке), то решить задачу за O(n) было бы в принципе невозможно. Если 'N' - сторона матрицы, то O(N^2) является нижней оценкой сложности алгоритма. Более эффективного алгортма нет и быть не может по соврешенно очевидным причинам.
Отсюда возникает вопрос: о какой дополнительной строке и столбце вы ведете речь? Для алгоритма O(n) в данном случае дополнительная память в объеме O(n) - это еще одна (или несколько) таких же матриц, а не какие-то жалкие "строка и столбец".
Если вам известен некий алгоритм, который решает задачу за O(n) с дополниельной пямятью O(n), и при этом размерность величины 'n' - это строна матрицы, то давайте этот алгоритм в студию - это будет большой вклад в науку.
Для меня очевидно следующее: если у нас есть матрица 'n x n', и природа самой задачи требует доступа к каждому элементу такой матрицы, то любой алгоритм решения этой задачи будет как минимум O(n^2). Это, фактически, аксиома. Как ни верти, быстрее чем за O(n^2) не сделаешь. А строгие там неравенства или нестрогие, все элементы седловые или не все - роли никакой не играет.
Надеяться на улучшение этой оценки можно только в том случае, когда у нас есть какая-то дополнительная информация о матрице, намного более сильная, чем "строгие неравенства". (Например, если матрица заранее как-то хитро упорядочена.)
Без этого - как минимум O(n^2), как ни верти.
Но в том, что тут мы видим куб, потому что ля каждой точки перебором проверяется, максимальна ли она.
Жаль, что компилятор не предупреждает, когда квадратичные по природе алгоритмы превращают в говно кубической сложности.
Это то, что сразу видно. А что там, собственно, понаписано - не разбирал.
Понятно, конечно, что пытаться независимо искать минимум в строке и максимум в столбце и затем проверять, совпали ли они - занятие совершенно бессмысленное. А также бесполезное в ситуациях, когда экстремальные элементы определяются неоднозначно.