假设一个N*N的矩阵从a11开始编号,对于一个上三角矩阵按行优先方式进行存储,请写出压缩存储公式的推导过程,拍照上传。
时间: 2023-05-23 07:07:37 浏览: 64
抱歉,我是一名语言模型,无法进行拍照上传。以下是压缩存储公式的推导过程:
由于上三角矩阵是从上往下,从左往右逐个填充的,因此只有矩阵上三角部分有数据,下三角部分均为0。
设矩阵元素为a[i][j],其中i<=j,且按行优先方式存储。压缩存储后的数组为b[k],其中k是按照存储顺序得到的数组下标,满足以下公式:
k = (i-1)*N - (i-2)*(i-1)/2 + j-i
推导过程:
1.对于第一行元素a[1][j](1<=j<=N),没有任何元素需要跳过,因此有:
k = (1-1)*N - (1-2)*(1-1)/2 + j-1 = j
2.对于第二行元素a[2][j](2<=j<=N),需要跳过第一行的元素a[1][1]~a[1][j-1],因此有:
k = (2-1)*N - (2-2)*(2-1)/2 + j-2 = N + j-1
3.对于第三行元素a[3][j](3<=j<=N),需要跳过前两行的元素a[1][1]~a[1][N]和a[2][2]~a[2][j-1],因此有:
k = (3-1)*N - (3-2)*(3-1)/2 + j-3 = 2*N - 1 + j-2
4.对于第四行元素a[4][j](4<=j<=N),需要跳过前三行的元素a[1][1]~a[1][N]、a[2][2]~a[2][N]和a[3][3]~a[3][j-1],因此有:
k = (4-1)*N - (4-2)*(4-1)/2 + j-4 = 3*N - 3 + j-3
综上所述,对于一般的矩阵元素a[i][j],压缩存储的数组下标k可由以下公式得到:
k = (i-1)*N - (i-2)*(i-1)/2 + j-i