LINUX.ORG.RU
ФорумTalks

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


0

0

Народ! I need help!

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

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

★★★★★

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

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

bugmaker ★★★★☆ ()

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

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

bugmaker ★★★★☆ ()
Ответ на: Re: Алгоритм нахождения.. от bugmaker

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

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

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

Igron ★★★★★ ()
Ответ на: Re: Алгоритм нахождения.. от bugmaker

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

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

Igron ★★★★★ ()

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

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

Igron ★★★★★ ()
Ответ на: Re: Алгоритм нахождения.. от Igron

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

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

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

linux_newbe ()
Ответ на: Re: Алгоритм нахождения.. от Igron

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

И что, думаешь, это понтово - позориться публично на ЛОРе?

anonymous ()
Ответ на: Re: Алгоритм нахождения.. от anonymous

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

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

Ekonomist ()
Ответ на: Re: Алгоритм нахождения.. от linux_newbe

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

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

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