Найти все седловые точки матрицы

Setb

Для матрицы m на n вывести на экран все седловые точки. Элемент матрицы называется седловой точкой, если он является наименьшим в своей строке и одновременно наибольшим в своем столбце или наоборот.
#include "stdafx.h"
#include "locale.h"
#include "math.h"
#include "stdio.h"
#include "conio.h"
#include "time.h"
#include "stdlib.h"
 
 
int main(void)
{
    setlocale(LC_ALL, "rus");
    int i, p, j, L, L2, pch, t = 0, min, min2, max, max2, k, k2;
    ****** srar = 0, sum = 0;
    int mas[3][3] = { { 5, 6, 4 }, { 3, 1, 2 }, { 3, 3, 3 } };
 
    printf("Исходный массив:\n");
    for (int i = 0; i < 3; ++i)// Вывод массива 
    {
        for (int j = 0; j < 3; ++j)
        {
            printf(" %d", mas[i][j]);
        }
        printf("\n\n");
    }
 
    printf("\n");
 
    for (i = 0; i<3; i++)//Вычисление седловых точек
    {
        min = mas[i][0];//минимум в строке
        max2 = mas[i][0];//максимум в строке
        k = 0;//записываем значения для сравнения с минимумом
        k2 = 0;//записываем значения для сравнения с максимумом
 
 
        for (j = 1; j<3; j++)
        {
            if (mas[i][j] < min)
            { 
                min = mas[i][j]; 
                k = j; 
            }
            if (mas[i][j] > max2)
            { 
                max2 = mas[i][j]; 
                k2 = j; 
            }
 
        }
 
        max = mas[i][k];
        L = 0;//записываем значения для сравнения с максимумом
        min2 = mas[i][k2];
        L2 = 0;//записываем значения для сравнения с минимумом
 
        for (j = 1; j<3; j++){
            if (mas[j][k] > max)
            { 
                max = mas[j][k]; L = j; 
            }
            if (mas[j][k] < min2)
            {
                min2 = mas[j][k2]; L2 = j; 
            }
        }
 
        if ((mas[L][k] == min && mas[L][k] == max))
        { 
            printf("Седловая точка в строке %d = %d\n", i, max); 
        }
        if (mas[L2][k2] == min2 && mas[L2][k2] == max2)
        { 
            printf("Седловая точка в строке %d = %d\n", i, max2);
        }
 
    }
Как это переделать, чтобы массив создавался через malloc. И как тогда координаты седловых точек определять? Через указатель?Как обращаться к отдельным элементам массива имея создание массива через указатели?
9 ответов

Setb

Возьмите Вот этот образец Он для C++. Но идея правильная.
int** Create(int n,int m)
{
    int i;
    int** M=(int**)malloc(n*sizeof(int*));
    for(i=0;i<n;i++)
    {
        M[i]=(int*)malloc(m*sizeof(int));
    }
    return M;
}
//----------------------------
void Free(int** M,int n)
{
    int i;
    for(i=0;i<n;i++)
        free(M[i]);
    free(M);
}
void Calc(int** mas,int n,int m)
{
    int i,j,min,max2,k,k2,L,L2,min2;
    for (i = 0; i<n; i++)//Вычисление седловых точек
    {
        min = mas[i][0];//минимум в строке
        max2 = mas[i][0];//максимум в строке
        k = 0;//записываем значения для сравнения с минимумом
        k2 = 0;//записываем значения для сравнения с максимумом
 
 
        for (j = 1; j<m; j++)
        {
            if (mas[i][j] < min)
            { 
                min = mas[i][j]; 
                k = j; 
            }
            if (mas[i][j] > max2)
            { 
                max2 = mas[i][j]; 
                k2 = j; 
            }
 
        }
 
        max = mas[i][k];
        L = 0;//записываем значения для сравнения с максимумом
        min2 = mas[i][k2];
        L2 = 0;//записываем значения для сравнения с минимумом
 
        for (j = 1; j<m; j++){
            if (mas[j][k] > max)
            { 
                max = mas[j][k]; L = j; 
            }
            if (mas[j][k] < min2)
            {
                min2 = mas[j][k2]; L2 = j; 
            }
        }
 
        if ((mas[L][k] == min && mas[L][k] == max))
        { 
            printf("Седловая точка в строке %d = %d\n", i, max); 
        }
        if (mas[L2][k2] == min2 && mas[L2][k2] == max2)
        { 
            printf("Седловая точка в строке %d = %d\n", i, max2);
        }
    }
 }


Setb

Так динамический массив одним циклом создается? И как тогда поиск по строкам и столбцам делать?


Setb

Так же, как и раньше. Я же написал Ваш код поиска в виде функции Calc.


Setb

int** Create(int n,int m)
{
    int i;
    int** M=(int**)malloc(n*sizeof(int*));
    for(i=0;i<n;i++)
    {
        M[i]=(int*)malloc(m*sizeof(int));
    }
    return M;
}
Этот код?Так это создание матрицы. Я имею ввиду как обращаться к отдельным элементам, осуществлять поиск максимума и минимума.У меня вообще путаница с указателями полная. Как обращаться к отдельному элементу матрицы?
if (mas[i][j] < min)
            { 
                min = mas[i][j]; 
                k = j; 
            }
Тут все понятно. А как это делать имея указатели?


Setb

А как это делать имея указатели?
mas - это и есть указатель на массив указателей на адреса строк. Конечно можно написать
if (  *( *(mas+i)+j) < min)
Но зачем?


Setb

#include "stdafx.h"
#include "locale.h"
#include "math.h"
#include "stdio.h"
#include "conio.h"
#include "time.h"
#include "stdlib.h"
 
#define pillar 3
#define line 5
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "rus");
 
    
    int **pMas = (int**)malloc(line*sizeof(int*));
 
    for (int i = 0; i < line; ++i)//Динамический масссив
    {
        pMas[i] = (int*)malloc(pillar*sizeof(int));
 
        for (int j = 0; j < pillar; j++)
        {
            pMas[i][j] = rand() % 11;
            printf("%d ", pMas[i][j]);
        }
        printf("\n\n");
    }
        
        int i, j, m, k;             //Счетчики
 
        int max;                    //Максимальный элемент в столбце
        int max_i = 0;              //Номер строки max
 
        
        
        for (j = 0; j < line; j++)//Поиск седловой точки
        {
            max = pMas[0][j];
 
            
            for (i = 1; i < pillar; i++)//Поиск максимального элемента в столбце
            {
                if (max < pMas[i][j]){
                    max = pMas[i][j];
                    max_i = i;
                }
            }
            
            for (i = 0; i < pillar; i++)//Проверка равных максимальных значений в столбце
            {
                m = 0;
                if (max == pMas[i][j])
                {
        
                    for (k = 0; k < line; k++)//Проверка условия седловой точки
                    {
                        if (max <= pMas[i][k])
                        {
                            m++;
                        }
                        else
                            break;
                    }
                                    
                    if (m == 5)//Вывод седловой точки
                        printf("Седловая точка: %d Строка: %d Столбец: %d\n", max, i + 1, j + 1);
                }
            }
        }
        return 0;
    }
Переделано полностью. Один вопрос. Почему то в качестве седловой точки нули показывает.


Setb

Setb, здравствуйте! Вот решение. Я его тестировал на различных ресурсах, таких как E-olymp и Дистанционная подготовка. В двух случаях из трех все тесты пройдены. Если кто-то найдет недочет в данной программе, прошу сообщить с примером матрицы для которой может быть найдена ошибка. Спасибо всем!
#include <iostream>
#include <climits>
 
using namespace std;
 
int main()
{
    int N, M, k;
    cout << "Введите размеры матрицы:" << endl;
    cout << "N = ";
    cin >> N;
    cout << "M = ";
    cin >> M;
    int* min = new int[N];
    int* max = new int[M];
    int** A = new int*[N];
    for (int i = 0; i < N; i++)
    {
        A[i] = new int[M];
    }
    cout << "Введите матрицу:" << endl;
    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++)
    {
        min[i] = INT_MAX;
        for (int j = 0; j < M; j++)
        {
            if (A[i][j] < min[i])
            {
                min[i] = A[i][j];
            }
        }
    }
    for (int j = 0; j < M; j++)
    {
        max[j] = INT_MIN;
        for (int i = 0; i < N; i++)
        {
            if (A[i][j] > max[j])
            {
                max[j] = A[i][j];
            }
        }
    }
    cout << "Индексы седловых точек:" << endl;
    k = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (min[i] == max[j])
            {
                cout << i << " " << j << endl;
                k++;
            }
        }
    }
    if (!(k))
        cout << "Седловых точек нет!" << endl;
    for (int i = 0; i < N; i++)
    {
        delete[] A[i];
    }
    delete[] min;
    delete[] max;
    system("pause");
    return 0;
}


Setb

Вот решение.
Перепиши его в си, чтобы можно было тестировать


Setb

Setb, Прошу прощения. Задачу не в тот раздел закинул...