Рубрики

Седловая точка в матрице

При заданной матрице размера nxn задача состоит в том, чтобы найти седловую точку матрицы. Седловая точка — это такой элемент матрицы, который является минимальным элементом в ее строке и максимальным в ее столбце.

Примеры :

Input: Mat[3][3] = { {1, 2, 3},
                  {4, 5, 6},
                  {7, 8, 9}}
Output: 7
7 is minimum in its row and maximum in its column.

Input: Mat[3][3] = {{1, 2, 3},
                    {4, 5, 6},
                    {10, 18, 4}}
Output: No saddle point

Простое решение состоит в том, чтобы обойти все матричные элементы один за другим и проверить, является ли элемент седловой точкой или нет.

Эффективное решение основано на следующих шагах.
Пройдите по всем строкам одну за другой и сделайте следующее для каждой строки i.

  1. Найдите минимальный элемент текущей строки и сохраните индекс столбца минимального элемента.
  2. Проверьте, является ли минимальный элемент строки максимальным в своем столбце. Мы используем хранимый индекс столбца здесь.
  3. Если да, то седловая точка еще продолжается до конца матрицы.

Ниже приведена реализация вышеуказанных шагов.

C ++

// C ++ программа для иллюстрации седловой точки
#include <bits/stdc++.h>

using namespace std;

  

const int MAX = 100;

  
// Функция для поиска седловой точки

bool findSaddlePoint(int mat[MAX][MAX], int n)

{

    // Обрабатываем все строки одну за другой

    for (int i = 0; i < n; i++)

    {

        // Находим минимальный элемент строки i.

        // Также найти индекс столбца минимального элемента

        int min_row = mat[i][0], col_ind = 0;

        for (int j = 1; j < n; j++)

        {

            if (min_row > mat[i][j])

            {

                min_row = mat[i][j];

                col_ind = j;

            }

        }

  

        // Проверка, является ли минимальный элемент строки также

        // максимальный элемент столбца или нет

        int k;

        for (k = 0; k < n; k++)

  

            // Обратите внимание, что col_ind исправлен

            if (min_row < mat[k][col_ind])

                break;

  

        // Если в этой строке присутствует седловая точка

        // распечатать

        if (k == n)

        {

           cout << "Value of Saddle Point " << min_row;

           return true;

        }

    }

  

    // Если седловая точка не найдена

    return false;

}

  
// Код драйвера

int main()

{

    int mat[MAX][MAX] = {{1, 2, 3},

                        {4, 5, 6},

                        {7, 8, 9}};

    int n = 3;

    if (findSaddlePoint(mat, n) == false)

       cout << "No Saddle Point ";

    return 0;

}

Джава

// Java-программа для иллюстрации седловой точки

  

class Test

{

    // Метод нахождения седловой точки

    static boolean findSaddlePoint(int mat[][    ], int n)

    {

        // Обрабатываем все строки одну за другой

        for (int i = 0; i < n; i++)

        {

            // Находим минимальный элемент строки i.

            // Также найти индекс столбца минимального элемента

            int min_row = mat[i][0], col_ind = 0;

            for (int j = 1; j < n; j++)

            {

                if (min_row > mat[i][j])

                {

                    min_row = mat[i][j];

                    col_ind = j;

                }

            }

       

            // Проверка, является ли минимальный элемент строки также

            // максимальный элемент столбца или нет

            int k;

            for (k = 0; k < n; k++)

       

                // Обратите внимание, что col_ind исправлен

                if (min_row < mat[k][col_ind])

                    break;

       

            // Если в этой строке присутствует седловая точка

            // распечатать

            if (k == n)

            {

               System.out.println("Value of Saddle Point " + min_row);

               return true;

            }

        }

       

        // Если седловая точка не найдена

        return false;

    }

      

    // Метод драйвера

    public static void main(String[] args) 

    {

        int mat[][] = {{1, 2, 3},

                      {4, 5, 6},

                     {7, 8, 9}};

          

        int n = 3;

        if (findSaddlePoint(mat, n) == false)

            System.out.println("No Saddle Point ");

    }

}

C #

// C # программа для иллюстрации седловой точки

using System;

  

class GFG {

      

    // Метод нахождения седловой точки

    static bool findSaddlePoint(int [,] mat, 

                                int n)

    {

          

        // Обрабатываем все строки одну за другой

        for (int i = 0; i < n; i++)

        {

              

            // Находим минимальный элемент

            // строка i. Также найдите индекс столбца

            // минимального элемента

            int min_row = mat[i, 0], col_ind = 0;

            for (int j = 1; j < n; j++)

            {

                if (min_row > mat[i, j])

                {

                    min_row = mat[i, j];

                    col_ind = j;

                }

            }

      

            // Проверка минимального элемента

            // строки тоже максимум

            // элемент столбца или нет

            int k;

            for (k = 0; k < n; k++)

      

                // Обратите внимание, что col_ind исправлен

                if (min_row < mat[k, col_ind])

                    break;

      

            // Если в этой строке присутствует седловая точка

            // распечатать

            if (k == n)

            {

                Console.WriteLine("Value of Saddle Point " 

                                                + min_row);

                return true;

            }

        }

      

        // Если седловая точка не найдена

        return false;

    }

      

    // Код драйвера

    public static void Main() 

    {

        int [,] mat = {{1, 2, 3},

                       {4, 5, 6},

                       {7, 8, 9}};

          

        int n = 3;

        if (findSaddlePoint(mat, n) == false)

            Console.WriteLine("No Saddle Point ");

    }

}

  
// Этот код предоставлен KRV.

PHP

<?php
// PHP программа для иллюстрации
// Точка перевала

  

$MAX = 100;

  
// Функция для поиска седловой точки

function findSaddlePoint( $mat, $n)

{

    // Обрабатываем все строки одну за другой

    for ( $i = 0; $i < $n; $i++)

    {

        // Находим минимальный элемент

        // строки i. Также найти столбец

        // индекс минимального элемента

        $min_row = $mat[$i][0]; 

        $col_ind = 0;

        for ( $j = 1; $j < $n; $j++)

        {

            if ($min_row > $mat[$i][$j])

            {

                $min_row = $mat[$i][$j];

                $col_ind = $j;

            }

        }

  

        // Проверяем, является ли минимальный элемент

        // строка также является максимальным элементом

        // столбца или нет

        $k;

        for ($k = 0; $k < $n; $k++)

  

            // Обратите внимание, что col_ind исправлен

            if ($min_row < $mat[$k][$col_ind])

                break;

  

        // Если седловая точка присутствует в

        // эту строку затем распечатать

        if ($k == $n)

        {

        echo "Value of Saddle Point " ,

                              $min_row;

        return true;

        }

    }

  

    // Если седловая точка не найдена

    return false;

}

  
// Код драйвера

$mat = array(array(1, 2, 3),

             array(4, 5, 6),

             array (7, 8, 9));

$n = 3;

if (findSaddlePoint($mat, $n) == false)

echo "No Saddle Point ";

  
// Этот код предоставлен anuj_67.
?>


Выход :

Value of Saddle Point 7

Упражнение:
Может ли быть более одной седловой точки в матрице?

Эта статья предоставлена Сахилом Чхаброй (KILLER) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Седловая точка в матрице

0.00 (0%) 0 votes