右上三角矩阵的压缩（Python实现）

阅读量：4189 次

发布时间：2019-05-26

本文共 6556 字，大约阅读时间需要 21 分钟。

右上三角矩阵

上三角矩阵就是一种对角线以下元素都为0的 n x n矩阵。其中右上三角矩阵是指对角线以下的元素都为0。由于上三角矩阵仍然有大量元素为0，为了避免浪费太多的内存空间，可以把三角矩阵的二维模式存储在一维列表中。

$a_{11}$	$a_{12}$	$a_{13}$	...	$a_{1n}$
0	$a_{22}$	$a_{23}$	...	$a_{2n}$
0	0	$a_{33}$	...	$a_{3n}$
...	...	...	...	...
0	0	0	...	$a_{nn}$

对于如上所示的 n x n右上三角矩阵A(ij)，如果i > j，那么对应位置的元素值为0。

解决方案

由于采用Python解决这个问题，一维列表不需要实现声明大小。将该矩阵的有效元素映射为一维列表存储有两种解决方案，映射方式分为以行为主和以列为主两种方式。

1. 以行为主的存储映射

以行为主的存储方案是先将右上三角矩阵的第一行对角线及对角线以上的元素存储在一维列表中，然后在将右上三角矩阵的第二行对角线及对角线以上的元素存储在一维列表中。。。以此类推存储每一行元素。这样存储的一维列表中包含了右上三角矩阵中全部的有效元素。

$a_{11}$

$a_{12}$

$a_{13}$

$a_{14}$

...

$a_{1n}$

$a_{22}$

$a_{23}$

...

$a_{ij}$

...

$a_{nn}$

观察一维列表存储的数据和坐标之间的关系，第0个位置存储 $a_{11}$ ，第1个位置存储 $a_{12}$ ，... 第n-1个位置存储 $a_{1n}$ 。第n个位置存储 $a_{22}$ ...

因此 $a_{ij}$ 存储在一维列表中的映射位置是 $n \cdot (i - 1) - \frac{i(i-1))}{2} + j - 1$

2. 以列为主的存储映射

以列为主的存储方案是先将右上三角矩阵的第一列对角线及对角线以上的元素存储在一维列表中，然后在将右上三角矩阵的第二列对角线及对角线以上的元素存储在一维列表中。。。以此类推存储每一列元素。这样存储的一维列表中包含了右上三角矩阵中全部的有效元素。

存储原理与上文类似，这里直接给出映射关系： $\frac{j(j-1))}{2} + i - 1$

无论选择哪一种存储映射，都可以将右上三角矩阵压缩为一个一维列表。本文选用以列为主的存储映射举例说明。

示例题目

1. 题目描述

设计一个Python程序，输入一个右上三角矩阵，输出压缩后的一维数组。

2. 输入/输出描述

输入描述：

输入右上三角矩阵的总行数、默认数字，然后自动计算大小，提示输入对应的数字。

Input matrix rows: 1Input default value: 0upper_triangular_matrix[0][0]: 8

输出描述：

输出原右上三角矩阵和压缩成一维列表后的矩阵。

------upper triangular matrix------|	8	|------compress upper triangular matrix --> list ------[8]

3. 代码

class MatrixException(Exception):    def __init__(self, message, code):        self.message = message        self.code = code# 1. 输入一个右上三角矩阵try:    rows = int(input("Input matrix rows: "))    if rows <= 0:        raise MatrixException("Matrix rows can not less than zero.", 1002)    columns = rows    default_value = int(input("Input default value: "))    utm = [[default_value] * columns for row in range(rows)]    for row in range(rows):        for column in range(columns):            if column >= row:                utm[row][column] = int(input("upper_triangular_matrix[%d][%d]: "                                             % (row, column)))except ValueError as e:    print("errcode: %s" % str(1001))    print("errmsg: %s" % str(e))    exit(1001)except MatrixException as e:    print("errcode: %s" % e.code)    print("errmsg: %s" % e.message)    exit(e.code)# 2. 压缩右上三角矩阵try:    array_size = ((1 + rows) * rows) // 2    compress = [None] * array_size    pos = 0    for row in range(rows):        for column in range(columns):            if column >= row:                compress[pos] = utm[row][column]                pos += 1    if None in compress:        print("compress: %s" % compress)        raise MatrixException("Compress upper triangular matrix failed.", 1002)except MatrixException as e:    print("errcode: %s" % e.code)    print("errmsg: %s" % e.message)    exit(e.code)# 3. 打印结果print("------upper triangular matrix------")for row in range(rows):    message = "|\t"    for column in range(columns):        message += str(utm[row][column]) + "\t"    message += "|"    print(message)print("------compress upper triangular matrix --> list ------")print(compress)

4. 代码走读

"""Copyright TCatTime"""# 自定义压缩异常class MatrixException(Exception):    def __init__(self, message, code):        self.message = message        self.code = code# 1. 输入一个右上三角矩阵try:    # 输入右上三角矩阵的行数，行数不大于0时报错    rows = int(input("Input matrix rows: "))    if rows <= 0:        raise MatrixException("Matrix rows can not less than zero.", 1002)    # 列数与行数保持相等    columns = rows    # 输入默认值（通常为0）    default_value = int(input("Input default value: "))    # 使用默认值初始化右上三角矩阵，并提示用户填充    utm = [[default_value] * columns for row in range(rows)]    for row in range(rows):        for column in range(columns):            if column >= row:                utm[row][column] = int(input("upper_triangular_matrix[%d][%d]: "                                             % (row, column)))# 当用户输入的数据不是一个整数时，会报错并退出except ValueError as e:    print("errcode: %s" % str(1001))    print("errmsg: %s" % str(e))    exit(1001)except MatrixException as e:    print("errcode: %s" % e.code)    print("errmsg: %s" % e.message)    exit(e.code)# 2. 压缩右上三角矩阵try:    # 初始化压缩列表，并使用None填充    array_size = ((1 + rows) * rows) // 2    compress = [None] * array_size    # 将右上三角矩阵的数据写入压缩l    pos = 0    for row in range(rows):        for column in range(columns):            if column >= row:                compress[pos] = utm[row][column]                pos += 1    if None in compress:        print("compress: %s" % compress)        raise MatrixException("Compress upper triangular matrix failed.", 1002)except MatrixException as e:    print("errcode: %s" % e.code)    print("errmsg: %s" % e.message)    exit(e.code)# 3. 打印结果print("------upper triangular matrix------")for row in range(rows):    message = "|\t"    for column in range(columns):        message += str(utm[row][column]) + "\t"    message += "|"    print(message)print("------compress upper triangular matrix --> list ------")print(compress)

传送门

测试用例

1、将如下的右上三角矩阵压缩

5	6	7
0	3	9
0	0	1

Input matrix rows: 3Input default value: 0upper_triangular_matrix[0][0]: 5upper_triangular_matrix[0][1]: 6upper_triangular_matrix[0][2]: 7upper_triangular_matrix[1][1]: 3upper_triangular_matrix[1][2]: 9upper_triangular_matrix[2][2]: 1------upper triangular matrix------|	5	6	7	||	0	3	9	||	0	0	1	|------compress upper triangular matrix --> list ------[5, 6, 7, 3, 9, 1]

2、输入的行数数据测试

1、输入0

Input matrix rows: 0errcode: 1002errmsg: Matrix rows can not less than zero.

2、输入负数

Input matrix rows: -4errcode: 1002errmsg: Matrix rows can not less than zero.

3、输入1

Input matrix rows: 1Input default value: 0upper_triangular_matrix[0][0]: 6------upper triangular matrix------|	6	|------compress upper triangular matrix --> list ------[6]

4、输入浮点数

Input matrix rows: 4.8errcode: 1001errmsg: invalid literal for int() with base 10: '4.8'

5、输入字符

Input matrix rows: serrcode: 1001errmsg: invalid literal for int() with base 10: 's'

3、输入的默认值测试

1、压缩如下矩阵。

5	6	7
13	3	9
13	13	1

将默认值default设置为13.

Input matrix rows: 3Input default value: 13upper_triangular_matrix[0][0]: 5upper_triangular_matrix[0][1]: 6upper_triangular_matrix[0][2]: 7upper_triangular_matrix[1][1]: 3upper_triangular_matrix[1][2]: 9upper_triangular_matrix[2][2]: 1------upper triangular matrix------|	5	6	7	||	13	3	9	||	13	13	1	|------compress upper triangular matrix --> list ------[5, 6, 7, 3, 9, 1]

2、输入的默认值为浮点数

Input matrix rows: 3Input default value: 3.6errcode: 1001errmsg: invalid literal for int() with base 10: '3.6'

3、输入的默认值为字符：

Input matrix rows: 3Input default value: derrcode: 1001errmsg: invalid literal for int() with base 10: 'd'

4、输入的矩阵值测试

1、正确的测试值在上例已有演示。

2、矩阵值输入的是字符：

Input matrix rows: 3Input default value: 0upper_triangular_matrix[0][0]: aerrcode: 1001errmsg: invalid literal for int() with base 10: 'a'

3、矩阵值输入的是浮点数：

Input matrix rows: 3Input default value: 0upper_triangular_matrix[0][0]: 1.3errcode: 1001errmsg: invalid literal for int() with base 10: '1.3'

转载地址：http://afsoi.baihongyu.com/

你可能感兴趣的文章

另一道看上去很吓人的面试题：如何交换a和b两个整数的值，不用额外空间 (Rev. 2)

查看>>

一道看上去很吓人的算法面试题：如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)

查看>>

今天David Solomon的为期三天的Windows Internal培训刚结束

查看>>

转贴：Mark Russinovich的Inside Vista Kernel系列文章，讲到了Vista内核的调度，IO，内存管理，缓存，事务处理，安全等众多新特性

查看>>

转载：如何指定程序在Vista上面需要提升权限运行(Elevated)

查看>>

如何知道可执行文件是32-bit还是64-bit

查看>>

.NET Interop: 从IErrorInfo错误对象获得托管代码的异常信息

查看>>

Microsoft Silverlight正式发布

查看>>

国际化编程中Locale相关概念的一些解释

查看>>

PIA (Primary Interop Assembly) & AIA (Alternate Interop Assembly)简介

查看>>

“妖精”团队———阿里巴巴

查看>>

迟到的感谢——2006最有价值博客的候选人（& 个人回顾）

怎样让.Net2.0的Membership使用已存在的Sql Server2000/2005数据库

查看>>

ASP.NET2.0 文本编辑器FCKeditor使用方法详解

查看>>

常见的 Web 项目转换问题及解决方案

查看>>

VS2005中使用ClickOnce 部署应用程序的升级

查看>>

Visual Studio2005下配置及运行NUnit

查看>>

.Net Remoting配置文件的用法

查看>>