LINUX.ORG.RU
ФорумTalks

Алгоритм нахождения..


0

0

Народ! I need help!

Сижу тут, решаю информатику.. Не могу домыслить, как найти седловые точки матрицы (точка является седловой, если она является минимальным элементом в своей строке и максимальным элементом в своем столбце)..

Есть ли у кого какие-нибудь идеи?

★★★★★

Это элементарно, Igron! Строиш множество из минимальных элементов строки, другое - из максимальных элементов столбца, ищеш пересечение этих, voila - всё работает...

bugmaker ★★★★☆
()

Исчо можно для например для каждой строки искать минимальный элемент, и по нахождении проверять, является ли оный максимальным в своём столбце, но это ИМХО неоптимальное решение.

bugmaker ★★★★☆
()
Ответ на: комментарий от bugmaker

> Исчо можно для например для каждой строки искать минимальный элемент, и по нахождении проверять, является ли оный максимальным в своём столбце, но это ИМХО неоптимальное решение

я над этим алгоритмом уже доолго парюсь - не получается:(

Igron ★★★★★
() автор топика
Ответ на: комментарий от bugmaker

Да фиг знает. Всю ночь на Си программирую, скоро красноглазым стану, а толку мало.

Igron ★★★★★
() автор топика

Блин, вроде сделал.. Только всё равно как-то не всегда работает. Сегодня я побил свой рекорд по времени пользования дебаггером.

Igron ★★★★★
() автор топика
Ответ на: комментарий от Igron

На C алгоритмы не пишут, ты не знал?
На С их реализуют.

sdio ★★★★★
()
Ответ на: комментарий от Igron

Чё ты там такого пишешь, что дебагить надо?

Ну ёпт не делай тогда оптимально, а просто перебором по каждому элементу.

linux_newbe
()
Ответ на: комментарий от anonymous

Эта... В первой матрице (исходная - нулевая) по строкам ставишь ноль, для минимального значения - единицу. Во второй по столбцам... ну ты понял. В третьей делаешь "дебильное умножение матриц" а3(i,j) = a1(i,j)*a2(i,j). Кто единица - тот и седловая точка.

Ekonomist
()
Ответ на: комментарий от linux_newbe

Согласен. Это я вчера погнал чёто спросонок. Вариант 1 всё-таки кажется логичней и незамысловатей однако...

bugmaker ★★★★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.