逻辑矩阵....解决方案

发布于 2024-08-29 13:51:02 字数 322 浏览 4 评论 0原文

假设你有一个 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|

我需要用任何语言生成一个通用程序来检查方阵是否为上三角矩阵。

原文

Suppose you have an NxN matrix and you have to check whether it's a upper diagonal matrix or not. Is there any generic method to solve this problem?

I am elaborating my question:
Some thing is like this:
Suppose you have NXN matrix having the value of N=4
then matrix will look like this:

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

Its a 4X4 square matrix and again if it's upper triangle matrix it will look something like this:

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

I need to generate a generic program in any language to check wether a square matrix is upper trailgle or not.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风和你 2024-09-05 13:51:02

只是为了检查一下，这些图中的左下角是 (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 的极端情况检查是一个好主意。

Just to check, are (1,1) the lower left and (n,n) the upper right in these diagrams? (This is not the way matrices are usually written!).

In any event, the algorithm is O(N^2) no matter what, I think -- you have to do something with all of the n*(n-1)/2 possibly-zero entries with row>column. You just have to step through them and see if they are zero -- of course, you should work your way through the matrix in the most efficient way, which depends on whether it is stored column- or row-major.

Also, is your matrix really filled with integers, or do you need to check for being approximately zero?

Basically you need to check

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

although the corner-case checks from @paxdiablo are a good idea.

回复收藏 0 原文

青衫负雪 2024-09-05 13:51:02

如果您想要一个简单的解决方案（使用基于 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 的列（含）。

在每一个单元格中，它只是检查数字是否为零。如果不是，则它不是左上三角形。如果检查的所有单元格均为零，则为零。

If you want a simplistic solution (using 1-based indexes):

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

This is assuming zeros are allowed in the upper left. If not, you'd have to check that as well.

Reasonably simple. On your 4x4 matrix, it iterates row from 2 to 4 inclusive. For row 2, it iterates column from 4 to 4 inclusive. For row 3, it iterates column from 3 to 4 inclusive. For row 4, it iterates column from 2 to 4 inclusive.

At every one of those cells, it just checks that the number is zero. If not, it's not upper left triangular. If all cells checked are zero, then it is.

回复收藏 0 原文

嗫嚅 2024-09-05 13:51:02

假设这在您的情况下是可行的，您可以采用以时间换空间的经典策略。

（我假设您使用的是面向对象语言 - 这个想法也适用于非面向对象语言，但需要付出更多努力来确保同一矩阵的不同表示保持同步）。

与其将矩阵表示为数组（或与该表示一起），不如将其保留为一组非零值呢？

因此，如果可行的话，您所表示的内容

|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-map 一起存储为数组，并且如果矩阵不是不可变的，您将必须提供方法来更改“单元格”值。

另一个权衡（除了空间）是创建新矩阵需要更多的 CPU 时间。但如果您不经常创建和修改这些并且必须经常测试下对角线，则可能是值得的。

更极端的方法：

为每个矩阵构建一个位图表示（非零单元为 1，零单元为 0）并使用逻辑运算来检查部分的“空性”。

Assuming this is feasible in your case, you could go for a classical strategy of trading time for space.

(I am assuming you are using an OO language - the idea holds for non-OO ones too, but will require more effort to ensure that the different representation of the same matrix are kept in synch).

Instead of representing the matrix as an array (or along with that representation) what about keeping it as a set of non-zero values?

So what you are representing as:

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

would become (or stored also as)

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

if this is doable, you could also split this set in two (upper and lower diagonal)

so in the case of your first matrix:

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

would be:

UpperMap -

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

Lower Map-

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

In this case, your test would be "asking if the lower hashmap is empty".

As mentioned above, if you need to do more "traditional" operations on the matrix you could store it as an array along with the 2-maps, and in case the matrixes are not immutable, you will have to provide methods to change the "cell" values.

The other trade off (apart from space) is that creating a new matrix requires more cpu time. But could be worth it if you create and modify these infrequently and have to test for the lower diagonal often.

A more extreme approach:

For each matrix build a bitmap representation (non-zero cells are 1, zero cells get a 0) and use logical operations to check for "emptiness" of a section.

回复收藏 0 原文

~没有更多了~