|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dennis 2:5020/400 02 Apr 2002 16:53:59
To : Andrey Dashkovsky
Subject : Re: несложная задачка, а поди ж ты ...
--------------------------------------------------------------------------------
Добрый день!
AD> SP> Есть матрица N*N, заполненная 0 и 1. Известно, что есть такое
AD> i, что SP> i-тый столбец состоит из "0", а i-я строка - из "1"
AD> (что стоит на SP> пересечении - неизвестно). Hужно найти это i за
AD> кол-во операций O(N).
AD> Вот подумал, и что-то придумал:
AD> Суть следующая: берём угол, проверяем граничный крест, если по краям не
AD> нули, значит это не та строка, если по вертикали не 1 значит не тот столбец,
AD> и сдвигаемся вниз и вправо если надо. Знаком '-' и '+' отмечен путь, где + -
AD> там граничные условия удовлетворяют. Как только дошли до того места где
AD> попали граничные условия - переходим на следующую строку и повторяем с
AD> первого столбца. потом также для столбцов.
А это не O(N^2)?
Hапример здесь:
1 0 0 0 0
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0
1 1 1 1 1
...Может, и ошибаюсь --- лень проверять. :)
--
Best regards,
Dennis
mailto: denis@tversu.ru
ICQ: 21938733
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Tver State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: несложная задачка, а поди ж ты ...