Задача следующая: дана матрица $%A$% размера $%n \times n$% с элементами $%a_{ij}$% из множества $%\{ 0, 1 \}$%. Известно, что существует единственное число $%k$%, такое, что $%a_{kj} = 0$% для всех $%j = 1, 2, \dots, n$%, а также $%a_{ik} = 1$% для всех $%i = 1, 2, \dots, k - 1, k + 1, \dots, n$%. Требуется найти это число $%k$%, сделав порядка $%\mathcal{O}(n)$% операций.

Заметил следующее: для $%i \neq j$% имеем $$a_{ij} = 0 \Rightarrow j \neq r \quad \text{и} \quad a_{ij} = 1 \Rightarrow i \neq r .$$

Как из этого наблюдения построить алгоритм с подходящим временем работы $%\mathcal{O}(n)$%?

Вроде бы можно, проверяя в некоторой последовательности значения $%a_{ij}$%, отсеивать, чему точно не может быть равно $%k$%, но как устроить обход $%a_{ij}$%, чтобы удовлетворить ограничению по времени?

задан 29 Мар 21:21

изменен 29 Мар 23:59

а просто, как говорят военные, "слева направо от себя в глубину" нельзя?...

если $%a_{11}\not=0$%, то вычёркиваете $%k=1$% и переходите к $%a_{22}$%...

если $%a_{11}=0$%, то проверяете написанное Вами условие $$ a_{12}=0 \quad\text{and}\quad a_{21}=1 $$ Если условие выполнено, то $%k=2$% вычёркиваете из рассмотрения и переходите к следующему элементу первой строки и первого столбца...

Если нарушается, то $%k=1$% вычёркиваете из рассмотрения... В зависимости от того как нарушается, то $%k=2$% может быть вычеркнуто или остаться

Ну, и так далее...

(30 Мар 0:17) all_exist

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

(30 Мар 1:24) all_exist

@all_exist, вряд ли этот алгоритм является линейным. Например, если взять матрицу с нулями на главной диагонали, выше - единицы, ниже - нули.

(30 Мар 10:49) spades

То есть, как минимум, надо внести уточнение, что сначала проверяем столбец(!) вниз, а потом только строку. Будет ли этого достаточно? Вряд ли... Вообще, хотелось бы уточнений - линейный в среднем или в экстремальном случае. По последнему у меня большие сомнения насчёт возможности, но возможно это очень хитрая задача

(30 Мар 11:19) spades

@spades, понятно, что в общем случае алгоритм нелинеен... но в условии есть фраза, что "Известно, что существует единственное число..."... в этом случае проверка линейна, поскольку при каждой проверке у наc отбрасывается один номер $%k$%... то есть в результате останется только один не вычеркнутый номер, который и будет искомым...

(30 Мар 13:31) all_exist

@all_exist, так у нас на одну проверку уходит в среднем n/2 действий. Или я не так понял?

(30 Мар 14:43) spades
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
0

@spades, вот пример матрицы $%4\times 4$%, приведённый Вами...

alt text

1) Проверяем номер $%k=1$% ... элемент $%a_{11}=0$% - удовлетворяет условию...

2) проверяем условие для пары элементов $%a_{12}$% и $%a_{21}$% ...
$%(a_{12}=1\;\; and \;\; a_{21}=0)$% - следовательно, $%k=1$% неудовлетворяют условию его вычёркиваем... переходим на диагональный элемент с минимальным невычеркнутым номером, здесь это $%k=2$%...

3) Проверяем элемент $%a_{22}=0$% - удовлетворяет условию...

4) проверяем условие для пары элементов $%a_{23}$% и $%a_{32}$% ...
$%(a_{23}=1\;\; and \;\; a_{32}=0)$% - следовательно, $%k=2$% неудовлетворяют условию его вычёркиваем... переходим на диагональный элемент с минимальным невычеркнутым номером, здесь это $%k=3$%...

5) Проверяем элемент $%a_{33}=0$% - удовлетворяет условию...

6) проверяем условие для пары элементов $%a_{34}$% и $%a_{43}$% ...
$%(a_{34}=1\;\; and \;\; a_{43}=0)$% - следовательно, $%k=3$% неудовлетворяют условию его вычёркиваем...

Остался только номер $%k=4$%, который является искомым... Время линейное...

ссылка

отвечен 30 Мар 15:52

изменен 2 Апр 17:43

Я вообще ничего не понял. Сколько проверок у нас уходит на одного кандидата? Как я понял три: $%a_{ii}, a_{i1}, a_{1i}$%. Почему тогда после проверок только одно останется? Я уже приводил пример матрицы. У нее после таких проверок ни одно число не отсеется.

(2 Апр 6:32) spades

@spades, Я уже приводил пример матрицы. У нее после таких проверок ни одно число не отсеется. - Вы привели пример матрицы, которая не рассматривается по условию... для линейности здесь существенно, что ровно одна строка со столбцом удовлетворяет условию расположения нулей и единиц.

Сколько проверок у нас уходит на одного кандидата? - от одного до трёх...

(2 Апр 14:55) all_exist

Что значит не удовлетворяет? Удовлетворяет полностью.
Ещё раз. Мы ищем нулевой диагональный элемент, у которого все значения в строке нулевые, а в столбце единицы. У моей матрицы такой один - последний.

011111
001111
000111
000011
000001
000000

(2 Апр 16:58) spades

@spades, значит я не внимательно прочитал Ваш пример... и видимо не совсем правильно описал алгоритм (перепутал строчки и столбики)... попробую исправиться...

(2 Апр 17:22) all_exist
10|600 символов нужно символов осталось
0

@all_exist, спасибо за исправленный ответ, теперь я разобрался. Ваш алгоритм не до конца рассказан, впрочем я ухватил суть. Привожу итоговое решение.
1. Проверяем диагональные элементы. Во множество возможных значений (МВЗ) вносим те $%k$%, где $%a_{kk}=0$%.
2. Берем пару $%(i,j)$% из МВЗ. Если $%a_{ij}=1$%, то удаляем из МВЗ $%i$%. Если $%a_{ij}=0$%, то $%j$%.
3. Повторяем шаг 2 до тех пор, пока в МВЗ не останется одно число. Количество таких шагов, очевидно, не более n-1.
Итого потребуется не более 2n-1 операций.

Мне задача очень понравилась. Она из тех, что решение, когда уже придумано, проще не бывает. Но до этого момента задаешься вопросом - как такое вообще может быть.
И еще раз благодарность @all_exist. То, что я называю командной работой ©

ссылка

отвечен 2 Апр 20:43

изменен 2 Апр 21:37

@spades, в п. 2 подразумевается, что $%i < j$%?...

у Вас после выполнения просеивания не будет соседних элементов - не понял эту мысль... я не просеиваю диагональные элементы как Вы... Я двигаюсь ступеньками, поэтому отбрасывание идёт по порядку от первого до искомого...

(2 Апр 21:04) all_exist

@all_exist, возможно я опять недопонял ваш метод. По крайней мере, мне показалось, что вы проверяете только диагональные и над- и под-диагональные элементы. Удалил эту часть.
Что касается i<j, то у нас есть 2 элемента в матрице, по которым можно отсеять одно из чисел. Поэтому не важно.

(2 Апр 21:10) spades

@spades, про неравенство ступил... пардон...

мне показалось, что вы проверяете только диагональные и над- и под-диагональные элементы. - нет... например, если бы на втором шаге в описанном решении получилось $%a_{12}=0\;and\;a_{21}=1$%, то я удаляю $%k=2$% и перехожу к рассмотрению элементов $%a_{13}$% и $%a_{31}$%...

(2 Апр 21:20) all_exist

@all_exist, сейчас я уже догадываюсь, что вы имели в виду. Но то, что было в самом начале - настолько туманно описано, а после исправления - только разбор примера. В таком случае, я только кристаллизовал Ваш алгоритм. Меня и эта роль устраивает...

(2 Апр 21:29) spades

@spades, не скажу, что Ваш алгоритм является просто формализацией моего варианта ... плюс Ваш более красиво описан... (сказывается опыт)...

я же просто попытался вступить на чужую территорию... )))

(2 Апр 21:36) all_exist
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×411
×237
×71

задан
29 Мар 21:21

показан
158 раз

обновлен
2 Апр 22:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru