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 [35654 просмотра]