C як знайти все сідлові точки в матриці

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:

Перевірте, для матриці розмірністю 8 * 2 повинен вийти порядок а для 4 * 4 - як у нас,

Код ж з лістингу повинен працювати незалежно від налаштувань приведення типів.

Для пошуку всіх сідлових точок в матрицях великої розмірності не потрібно розглядати кожен елемент окремо.

Розглянемо більш "культурний" алгоритм пошуку всіх сідлових точок матриці. Покажемо його роботу на прикладі.

Потрібно знайти всі її сідлові точки.

Зберемо найменші значення по всіх рядках, отримаємо вектор A = (- 4, 2, 2, -3).

Зберемо найбільші значення по всіх стовпцях, отримаємо вектор B = (7, 2, 7, 2).

Перевірка: максимум першого набору ніколи не може бути більше мінімуму другого.

Якщо максимум першого набору менше, ніж мінімум другого, то сідлових точок немає.

Якщо максимум першого набору дорівнює мінімуму другого (в нашому випадку число 2), ми знайшли значення S сідлової точки.

Тепер подивимося, на яких позиціях у векторах A і B знаходяться значення S.

При нумерації з одиниці. в першому наборі це позиції 2 і 3, а в другому - позиції 2 і 4.

На творі цих множин розташовуються всі сідлові точки. У нашому випадку * = <, , ,> - координати в матриці всіх сідлових точок, знову ж таки, при нумерації з одиниці.

Одна з можливих реалізацій цього алгоритму (гість)