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

假设你有一个N×N矩阵，你必须检查它是否是一个上对角矩阵。有没有什么通用的方法来解决这个问题？逻辑矩阵....解决方案

我阐述我的问题：有些事情是这样的：假设你有具有N的值NXN矩阵= 4 然后矩阵看起来就像这样：

它是一个4X4的方阵如果再是上三角矩阵会是这个样子：

我需要用任何语言来生成一个通用的程序，请检查是否方阵是上trailgle与否。

来源

2010-04-16 Sanju

您是否在寻找O（n ** 2）以外的天真解决方案来检查所有较低的条目是否都是0？ – outis 2010-04-16 05:13:13

我编辑了我的问题Plz看看这个！ – Sanju 2010-04-16 07:43:21

这是功课吗？ – 2010-04-16 07:48:44

只是为了检查，是（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是一个好主意。

来源

2010-04-16 09:08:03

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

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

来源

2010-04-16 08:49:43 paxdiablo

假设在你的情况下这是可行的，你可以选择一个经典的空间交易时间策略。（我假设你使用的是OO语言 - 这个想法对于非OO语言也适用，但是需要更多的努力来确保同一矩阵的不同表示保持同步）。

而不是将矩阵表示为数组（或与表示一起）将它保持为一组非零值？

那么，你是代表为：

将成为（或存储为）

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

，如果这是可行的，你也可以在两（上下分割该套对角线）

在第一基质的情况下

这样：

是：

UpperMap - 

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

Lower Map- 

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

在这种情况下，你的测试将是“询问是否较低的HashMap是空的”。如上所述，如果您需要在矩阵上执行更多的“传统”操作，您可以将它与2位地图一起存储为数组，并且在矩阵不是不可变的情况下，您将不得不提供方法改变“细胞”值。

另一个折衷（除了空间）是创建一个新的矩阵需要更多的CPU时间。但如果你不经常创建和修改这些东西，而且经常需要测试较低的对角线，这可能是值得的。

一个更极端的方法：

对于每个矩阵建立一个位图表示的（非零细胞是1，零细胞得到一个0），并使用逻辑操作以检查部的“空”。

来源

2010-04-16 09:51:17

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

回答

相关问题