Задача 5.
Задана прямоугольная таблица А[1:N,1:N], элементы которой равны 0 или 1 причем А[i,i]=0 для любого i.
Необходимо найти, если они есть, такие строку i0 и столбец j0, чтобы в столбце j0 были все 0, а в строке i0 - все 1 (кроме элемента A[i0,i0], равного 0).
|
Решение задачи 5.
Простейшим решением является просмотр элементов i-й строки и i-го столбца, i=1,2,...,N (номера строки и столбца должны быть равны, иначе они пересекаются не по диагональному элементу) массива до нахождения индекса k, такого что элементы k-ой строки и k-го столбца удовлетворяют требуемому свойству или установления факта, что такого индекса нет. Очевидно, что в последнем случае необходим просмотр почти всех элементов массива.
Однако возможно существенно сократить количество операций, используя следующий факт.
Рассмотрим элемент A[k,j], k<>j. Возможны следующие ситуации:
1. A[k,j] = 0.
В этом случае легко заметить, что индекс k не подходит, так как в строке с индексом k стоит 0. Поэтому можно ограничится по иском заданного элемента в подмассиве без k-ого столбца и k-й строки.
2. A[k,j] = 1.
В этом случае легко заметить, что индекс j не подходит, так как в столбце с индексом j стоит 1. Поэтому можно ограничится по иском заданного элемента в подмассиве без j-ого столбца и j-й строки.
Таким образом, рассматривая на каждом шаге значения элементов A[k,j], таких что A[k,j] является элементом интересующего нас под массива, потребуется просмотр ровно N-1 элемента для установления единственного индекса k, удовлетворяющего требуемому свойству. Осталось проверить только элементы этого столбца и строки.
k:=1
для j от 2 до N
если A[k,j] = 0
то k:=j
Осталось проверить только элементы k-ого столбца и строки. Поэтому трудоемкость такого поиска не превосходит 3*N.
|
