C++: как найти все седловые точки в матрице
Понятие седловой точки матрицы широко применяется в теории игр и кое-где ещё.
Седловой точкой называется
элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы, или, что то же самое, элемент матрицы, который одновременно является максимальным элементом в соответствующем столбце матрицы и минимальным элементом в строке.
Следует учесть, что
если матрица имеет несколько седловых точек, то все их значения равны.
Если все числа в матрице различны, то и седловой точки не более одной.
Если все числа в матрице одинаковы, число седловых точек равно числу элементов.
Сначала листинг с «элементарно-переборным» подходом.
Функция int saddle (int n,int m,int **a,int is,int js) проверяет, является ли элемент
a[is][js] матрицы a размерностью n*m её седловой точкой. Вернёт 1 (да) или 0 (нет).
Функция int *saddle_points (int n, int m, int **a, int &k) находит все седловые точки матрицы. Использует первую функцию. Возвращает количество седловых точек через параметр-ссылку k, а основная возвращаемая величина — вектор размерностью 2*k, содержащий координаты строк и столбцов всех седловых точек матрицы. Например если в матрице 2 седловых точки, находящихся в позициях (0,1) и (3,2), вектор будет состоять из чисел (0,1,3,2) (нумерация с нуля).
В main интересен также способ переписать вектор из (n*m) элементов построчно в матрицу размерности n*m:
//Если число элементов items = n*m, код корректно перепишет вектор в матрицу (по строкам) for (i=0; i<n*m; i++) a[i/m][i%m]=items[i];
Проверьте, для матрицы размерностью 8*2 должен получиться порядок
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15а для 4*4 — как у нас,
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Это нужно для того, что мне захотелось передавать в функции параметр типа int **a, а при подстановке фактического параметра-адреса матрицы
int a[n][m];
во многих компиляторах я рисковал бы получить ошибку вроде
Cannot convert 'int [4] *' to 'int * *'
Код же из листинга должен работать независимо от настроек приведения типов.
#include <stdlib.h>
#include <stdio.h>
int saddle (int n,int m,int **a,int is,int js) {
int i,j,min,max;
min=a[is][0];
for (j=0; j<m; j++) if (a[is][j]<min) min=a[is][j];
max=a[0][js];
for (i=0; i<n; i++) if (a[i][js]>max) max=a[i][js];
return (a[is][js]==min && a[is][js]==max ? 1 : 0);
}
int *saddle_points (int n, int m, int **a, int &k) {
int i,j;
k=0;
for (i=0; i<n; i++)
for (j=0; j<m; j++) {
if (saddle(n,m,a,i,j)) k++;
}
if (k==0) return NULL;
int *s = new int [k*2];
if (s==NULL) return NULL;
int l=0;
for (i=0; i<n; i++)
for (j=0; j<m; j++) {
if (saddle(n,m,a,i,j)) { s[l++]=i; s[l++]=j; }
}
return s;
}
int main () {
const int n=4,m=4;
int **a;
int items[] = {
7,-1,-4,1,
3,2,3,2,
2,2,3,2,
4,-3,7,-2
};
int i,j;
a = new int * [n];
for (i=0; i<n; i++) a[i] = new int [m];
//Если число элементов items = n*m, код корректно перепишет вектор в матрицу (по строкам)
for (i=0; i<n*m; i++) a[i/m][i%m]=items[i];
printf ("nПолучена матрица:");
for (i=0; i<n; i++) {
printf ("n");
for (j=0; j<m; j++) printf ("%d ",a[i][j]);
}
int k=0;
int *s=saddle_points (n,m,a,k);
if (k>0) {
for (i=0; i<2*k; i+=2) {
printf ("na[%d,%d]=%d",s[i],s[i+1],a[s[i]][s[i+1]]);
}
}
else printf ("nНет седловых точек или не выделена память");
printf ("nENTER");
getchar();
return 0;
}
Для поиска всех седловых точек в матрицах большой размерности не нужно рассматривать каждый элемент отдельно.
Рассмотрим более «культурный» алгоритм поиска всех седловых точек матрицы. Покажем его работу на примере.
Дана матрица:
7 -1 -4 1 4 2 3 2 2 2 3 2 4 -3 7 -2
Требуется найти все её седловые точки.
Соберём наименьшие значения по всем строкам, получим вектор A=(-4, 2, 2, -3).
Соберём наибольшие значения по всем столбцам, получим вектор B=(7, 2, 7, 2).
Проверка: максимум первого набора никогда не может быть больше минимума второго.
Если максимум первого набора меньше, чем минимум второго, то седловых точек нет.
Если максимум первого набора равен минимуму второго (в нашем случае число 2), мы нашли значение S седловой точки.
Теперь посмотрим, на каких позициях в векторах A и B находятся значения S.
При нумерации с единицы, в первом наборе это позиции 2 и 3, а во втором — позиции 2 и 4.
На произведении этих множеств располагаются все седловые точки. В нашем случае
{2, 3} * {2, 4} = { {2, 2}, {3, 2}, {2, 4}, {3, 4} } — координаты в матрице всех седловых точек, опять же, при нумерации с единицы.
Одна из возможных реализаций этого алгоритма:
#pragma hdrstop
#pragma argsused
#include <tchar.h>
/* в некоторых компиляторах нужно убрать 3 верхних строчки */
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <ctime>
int main ()
{
const int strok = 4 , stolbcov = 4;
int i,j,k,z, maxofmin,minofmax;
int matr[strok][stolbcov] = {{7,-1,-4,1},{4,2,3,2},{2,2,3,2},{4,-3,7,-2}};
int max[stolbcov], min[strok];
/* srand(time(0));
for (i = 0; i < strok; i++)
for (j = 0; j < stolbcov; j++)
matr[i][j]=rand()%9+1; */
for (i = 0; i < strok; i++)
{
std::cout << "n";
for (j = 0; j < stolbcov; j++)
{
std::cout<< std::setw(3)<<matr[i][j];
}
}
std::cout << std::endl;
j = 0;
for (i = 0; i < strok; i++)
{
for (j = 0; j < stolbcov; j++)
{
min[i] = matr[i][j];
if (min[i] > matr[i][j])
min[i] = matr[i][j];
}
}
j = 0;
for (j = 0; j < stolbcov; j++)
{
i=0;
max[j] = matr[i][j];
for (i = 0; i < strok; i++)
if (max[j] < matr[i][j])
max[j] = matr[i][j];
}
maxofmin = min[0];
for (i = 0; i < strok; i++)
if (maxofmin < min[i])
maxofmin = min[i];
minofmax = max[0];
for (i = 0; i < stolbcov; i++)
if (minofmax > max[i])
minofmax = max[i];
if (minofmax > maxofmin)
std::cout << "Sedlovix tochek net" << std::endl;
else
std::cout << "Sedlovie tochki = " <<std::endl;
for (i = 0; i < strok; i++)
if (min[i] == maxofmin)
for (j = 0; j < stolbcov; j++)
if (max[j] == minofmax)
std::cout << i << " " << j << std::endl;
system("pause");
return 0;
}
15.11.2013, 17:48 [34340 просмотров]
К этой статье пока нет комментариев, Ваш будет первым
I’m trying to write pseudocode to find all the saddle points in a 2D array. The saddle points are the spots where the value is the minimum in its row, but maximum in its column, or the maximum in its row and minimum in its column.
I’m having trouble wrapping my head around how to store where these values occur, especially if there are 2 saddle points in the same row or column. I’m also not sure if I’m even approaching this correctly, maybe it can be done in a more efficient way?
The array is given by A[x][y] where x is the row and y is the column.
So far my (very basic) pseudocode is
for r=0 to y-1 // iterates through every row
for c=0 to x-1 //iterates through every element in row r
min=min(A[c][r]) //finds the minimum value in row r
for p=0 to y-1 //iterates through every element in col c
max=max(A[c][p]) //finds max in col c
if min==max
saddle point=A[c][p]
asked Feb 6, 2017 at 18:36
3
You seem to have two major problems with your pseudocode.
1) You have swapped the raws and colums
2) Passing an array element (aka value) to min/max does not make much sense. You probably should pass a row number instead and have the function to return the column number.
A simple way is to find the index of the column holding the minimum value in row r. Then find the index of the row holding the maximum value in that column.
If the two row index are the same, you have a saddle point.
Something like:
for r=0 to x-1 // iterates through every row
// Check min-max combination
c = min_in_row(r) //find index of the column holding the minimum value in row r
r2 = max_in_column(c) //find index of the row holding the maximum value in column c
if (r == r2)
{
// Saddle point found
printf("r=%d c=%d value %d is a saddle pointn", r, c, A[r][c]);
}
// Repeat the same for the max-min combination
answered Feb 6, 2017 at 19:07
Support UkraineSupport Ukraine
41.5k4 gold badges38 silver badges63 bronze badges
2
Any saddle point can be stored with (row, column). In C:
struct Saddle { int row, col; };
If the maximum number of expected saddle points is known a result array may be used:
/* max. number of saddle points */
#define MAX_FOUND 16
/* row/col. of found saddle points */
struct Saddle found[MAX_FOUND];
/* number of found saddle points */
int nFound = 0;
To store a new result:
found[nFound].row = r;
found[nFound].col = c;
++nFound;
If the number of expected saddle points is unknown two options come in mind:
-
make the array size x * y (Hmm.)
-
allocate storage for array using malloc.
For the 2nd option malloc/realloc can be used.
There is often a trick used: If the storage runs out of memory, the realloc is used to allocate new space for multiple additional elements. Thus, the number of re-allocations is reduced because realloc is counted as «expensive» operation. In this case, two count variables are used: one for the size of allocated array, another for the numbers of actually used elements. Of course, the second must always be less or equal to the first.
answered Feb 6, 2017 at 19:10
Scheff’s CatScheff’s Cat
19.4k6 gold badges28 silver badges56 bronze badges
Вариант решения с учетом возможных повторений минимумов и максимумов.
Не претендует на идеальный, памяти многовато ест. скорее всего можно оптимизировать.
Временная сложность O(MxN), Использование дополнительной памяти O(MxN)
Код на C#, но кроме двумерных массивов в данном фрагменте все идентично C++, адаптация не должна стать проблемой.
int m;//Количество столбцов
int n;//Количество строк
//читаем M и N
int[,] source = new int[m, n];//исходная матрица
int[,] finder = new int[m, n];//матрица поиска
//заполняем исходную матрицу любым способом
//заполняем матрицу поиска нулями
for (int j = 0; j < n; j++){
//ищем минимум в строке
int minInd = 0;
for (int i = 1; i < m; i++)
if (source[minInd,j]>source[i,j])
minInd = i;
//Отмечаем на матрице поиска все минимумы прибавляя 1
for (int i = 0; i < m; i++)
if (source[minInd, j] == source[i, j])
finder[i, j]++;
}
//Повторяем все то же для максимумов столбцов
for (int i = 0; i < m; i++){
int maxInd = 0;
for (int j = 1; j < n; j++)
if (source[i, maxInd] < source[i, j])
maxInd = j;
for (int j = 0; j < n; j++)
if (source[i, maxInd] == source[i, j])
finder[i, j]++;
}
int result = 0;
for (int j = 0; j < n; j++)
for (int i = 1; i < m; i++)
if (finder[i, j] == 2)//если минимум строки и максимум столбца
result++; //совпали, ячейка матрицы поиска будет равна 2
//из result забираем количество найденных седловых элементов
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <time.h> #include <stdio.h> #include <stdlib.h> enum {N=4, M=5}; void printf_arr (int [][M], int, int); void random_arr (int [][M], int, int); int max_in_col (int [][M], int, int, int); int min_in_row (int [][M], int, int, int); void saddle_point (int [][M], int, int); int main (void) { int a[N][M] = { { 2, 12, 6, 45, 77}, { 2, 3, 1, 79, 105}, { 2, 44, 3, 32, 21}, { 0, 83, 0, 19, -6} }; int b[N][M] = { {0} }; random_arr(b, N, M); puts("массив a:"); printf_arr(a, N, M); saddle_point(a, N, M); puts("nмассив b:"); printf_arr(b, N, M); saddle_point(b, N, M); return 0; } // ------------------------------------------------------------- void printf_arr (int a[][M], int rows, int columns) { for (int i=0; i<rows; i++, puts("")) for (int k=0; k<columns; k++) printf("% 4d", a[i][k]); puts(""); } // ------------------------------------------------------------- void random_arr (int a[][M], int rows, int columns) { srand( (unsigned int)time(NULL)/2 ); for (int i=0; i<rows; i++) for (int k=0; k<columns; k++) a[i][k] = rand() %101 - 50; } // ------------------------------------------------------------- int max_in_col (int a[][M], int rows, int columns, int column) { int max = 0; for (int i=1; i<rows; i++) if (a[i][column] > a[max][column]) max = i; return max; // возвращает строку } // ------------------------------------------------------------- int min_in_row (int a[][M], int rows, int columns, int row) { int max = 0; for (int k=1; k<columns; k++) if (a[row][k] < a[row][max]) max = k; return max; // возвращает столбец } // ------------------------------------------------------------- void saddle_point (int a[][M], int rows, int columns) { int i, k, min[N], max[M]; for (i=0; i<rows; i++) min[i] = a[i][min_in_row(a, rows, columns, i)]; for (k=0; k<columns; k++) max[k] = a[max_in_col(a, rows, columns, k)][k]; int found = 0; for (i=0; i<rows; i++) for (k=0; k<columns; k++) if (a[i][k] == min[i] && a[i][k] == max[k]) { printf("%4d", a[i][k]); found++; } if (found < 1) puts("В массиве нет седловых точек!"); else printf("nВыявлено %d седловые точки.n", found); } // ------------------------------------------------------------- |
Задана матрица K, содержащая n строк и m столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.
Входные данные
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 750). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно kij. Все kij по модулю не превосходят 1000.
Выходные данные
Выведите ответ на задачу.
В чем ошибка?
type s = array[1..750,1..750] of integer;
type s2 = array[1..750] of integer;
var mas: s;
var masN,masX: s2;
var n,m,i,j,k: integer;
begin
k:=0;
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(mas[i,j]);
masN[1]:=mas[1,1];
for i:=1 to n do
begin
for j:=1 to m do
if mas[i,j]<masN[i] then
masN[i]:=mas[i,j];
masN[i+1]:=mas[i+1,1];
end;
masX[1]:=mas[1,1];
for j:=1 to m do
begin
for i:=1 to n do
if mas[i,j]>masX[j] then
masX[j]:=mas[i,j];
masX[j+1]:=mas[1,j+1];
end;
for i:=1 to n do
for j:=1 to m do
if (mas[i,j]=masN[i]) and (mas[i,j]=masX[j]) then
k:=k+1;
write(k);
end.