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

@Setb · Регистрация: 04.07.2015

Студворк — интернет-сервис помощи студентам

Для матрицы m на n вывести на экран все седловые точки. Элемент матрицы называется седловой точкой, если он является наименьшим в своей строке и одновременно наибольшим в своем столбце или наоборот.

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
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
#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;
    double 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. И как тогда координаты седловых точек определять? Через указатель?

Добавлено через 46 секунд
Как обращаться к отдельным элементам массива имея создание массива через указатели?

@zss · 19.09.2015, 21:17

Возьмите Вот этот образец
Он для C++. Но идея правильная.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
}

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
47
48
49
50
51
52
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 · 19.09.2015, 21:28 **[ТС]**

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

@zss · 19.09.2015, 21:35

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

@Setb · 19.09.2015, 21:43 **[ТС]**

C
1
2
3
4
5
6
7
8
9
10
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;
}

Этот код?

Добавлено через 1 минуту
Так это создание матрицы. Я имею ввиду как обращаться к отдельным элементам, осуществлять поиск максимума и минимума.

Добавлено через 1 минуту
У меня вообще путаница с указателями полная. Как обращаться к отдельному элементу матрицы?

C
1
2
3
4
5
if (mas[i][j] < min)
            { 
                min = mas[i][j]; 
                k = j; 
            }

Тут все понятно. А как это делать имея указатели?

@zss · 19.09.2015, 21:50

Сообщение от Setb

А как это делать имея указатели?

mas - это и есть указатель на массив указателей на адреса строк.
Конечно можно написать

C
1
if (  *( *(mas+i)+j) < min)

Но зачем?

@Setb · 21.09.2015, 11:51 **[ТС]**

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
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
#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;
    }

Переделано полностью. Один вопрос. Почему то в качестве седловой точки нули показывает.

@Fixer_84 · 22.01.2017, 14:37

Setb, здравствуйте! Вот решение. Я его тестировал на различных ресурсах, таких как E-olymp и Дистанционная подготовка. В двух случаях из трех все тесты пройдены. Если кто-то найдет недочет в данной программе, прошу сообщить с примером матрицы для которой может быть найдена ошибка. Спасибо всем!

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
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
#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;
}

@CoderHuligan · 22.01.2017, 14:42

Сообщение от Fixer_84

Вот решение.

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

@Fixer_84 · 22.01.2017, 14:45

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

Новые блоги и статьи Все статьи Все блоги /
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .

@Setb 136 / 2 / 6 Регистрация: 04.07.2015 Сообщений: 122
	19.09.2015, 21:28 [ТС]
	Так динамический массив одним циклом создается? И как тогда поиск по строкам и столбцам делать? 0

@zss Модератор 13770 / 10963 / 6491 Регистрация: 18.12.2011 Сообщений: 29,240
	19.09.2015, 21:35
	Так же, как и раньше. Я же написал Ваш код поиска в виде функции Calc. 0

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	22.01.2017, 14:45
	Setb, Прошу прощения. Задачу не в тот раздел закинул... 0

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

Решение