Логическая матрица .... Решение

Question

Предположим, у вас есть матрица NxN, и вы должны проверить, является ли она верхней диагональной матрицей или нет. Есть ли общий метод для решения этой проблемы?

Я уточняю свой вопрос: Что-то вроде этого: Предположим, у вас есть матрица NXN, имеющая значение N = 4 тогда матрица будет выглядеть так:

|5 6 9 2|
|1 8 4 9|
|5 8 1 6|
|7 6 3 2|

Это квадратная матрица 4X4 и снова, если это матрица верхнего треугольника, она будет выглядеть примерно так:

|5 6 9 2|
|1 8 4 0|
|5 8 0 0|
|7 0 0 0|

Мне нужно создать универсальную программу на любом языке, чтобы проверить, является ли квадратная матрица верхним трейлингом или нет.

Answer 1

Просто чтобы проверить, являются ли (1,1) нижний левый угол и (n, n) верхний правый на этих диаграммах? (Это не способ, которым матрицы обычно пишутся!).

В любом случае, алгоритм O(N^2), несмотря ни на что, я думаю - вы должны сделать что-то со всеми n*(n-1)/2 возможно нулевыми записями с row>column. Вам просто нужно пройтись по ним и посмотреть, равны ли они нулю - конечно, вы должны пройти через матрицу наиболее эффективным способом, который зависит от того, хранится ли она в столбце или мажоре строки.

Кроме того, ваша матрица действительно заполнена целыми числами, или вам нужно проверить, что она приблизительно равна нулю?

В основном вам нужно проверить

for col = 2, n 
   for row = col+1, n
      if matrix(row, col) != 0
         return false
      endif
   endfor
endfor

хотя проверки в угловом регистре от @paxdiablo - хорошая идея.

Answer 2

Если вы хотите упрощенное решение (с использованием индексов на основе 1):

def isUpperDiag(matrix[][]):
    if matrix.height != matrix.width:
        return false                      # must be square
    if matrix.height == 1:
        return true                       # not sure how to treat 1x1
    for row = 2 to matrix.height:
        for col = matrix.width - row + 2 to matrix.width:
            if matrix[row][col] != 0:
                return false
    return true

Предполагается, что в левом верхнем углу допустимы нули. Если нет, то вам тоже нужно это проверить.

Достаточно просто. На вашей матрице 4x4 она перебирает строки от 2 до 4 включительно. Для строки 2 это итерирует столбец от 4 до 4 включительно. Для строки 3 это итерирует столбец от 3 до 4 включительно. Для строки 4 это итерирует столбец от 2 до 4 включительно.

В каждой из этих ячеек он просто проверяет, что число равно нулю. Если нет, то это не верхний левый треугольник. Если все проверенные ячейки равны нулю, то это так.

Answer 3

Предполагая, что это возможно в вашем случае, вы можете пойти на классическую стратегию торговли временем для пространства.

(Я предполагаю, что вы используете OO-язык - идея подходит и для не-OO-языков, но потребует больше усилий для обеспечения синхронизации различных представлений одной и той же матрицы).

Вместо представления матрицы в виде массива (или вместе с этим представлением), как насчет сохранения ее в виде набора ненулевых значений?

Итак, что вы представляете как:

|5 6 9 2|
|1 8 4 0|
|5 8 0 0|
|7 0 0 0|

станет (или сохранится также)

1,1=5
1,2=6
1,3=9
...
4,1=7

если это выполнимо, вы также можете разделить этот набор на две части (верхняя и нижняя диагонали)

так в случае вашей первой матрицы:

|5 6 9 2|
|1 8 4 9|
|5 8 1 6|
|7 6 3 2|

будет:

UpperMap -

1,1=5
1,2=6
1,3=9
...
4,1=7

Lower Map-

2,4=9
3,3=1
...
4,4=2

В этом случае ваш тест будет «спрашивать, пуста ли нижняя хэш-карта».

Как уже упоминалось выше, если вам нужно выполнить больше «традиционных» операций над матрицей, вы можете сохранить ее как массив вместе с 2-картами, и в случае, если матрицы не являются неизменяемыми, вам придется предоставить методы для изменить значения "ячейки".

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

Более экстремальный подход:

Для каждой матрицы построить растровое представление (ненулевые ячейки равны 1, нулевые ячейки получают 0) и использовать логические операции для проверки «пустоты» секции.