设矩阵A是一个对称矩阵,为了节省存储空间,将其下三角部分按照行优先存放在一维数组B[0..n(n+1)/2-1]中,对于下三角部分的任一元素a_{i,j}(i>=j,i和j从0开始取值),在一维数组B中的下标k的值是____。
时间: 2024-03-28 15:39:34 浏览: 50
假设矩阵A的维数为n,则下标k的计算公式为:
k = i * (i+1) / 2 + j
其中i和j分别为矩阵A中元素a_{i,j}的行和列下标,i>=j,且0<=i,j<n。这个公式的推导可以参考下三角矩阵压缩存储的定义。
例如,当n=4时,矩阵A的下三角部分为:
1 0 0 0
2 3 0 0
4 5 6 0
7 8 9 10
按行优先存放在一维数组B中,则B的元素如下所示:
B[0]=1, B[1]=2, B[2]=3, B[3]=4, B[4]=5, B[5]=6, B[6]=7, B[7]=8, B[8]=9, B[9]=10
例如,要访问矩阵A中第3行第1列的元素a_{3,1},可以通过下标计算公式计算出在数组B中的下标k:
k = 3 * (3+1) / 2 + 1 = 6
则B[6]的值为5,即a_{3,1}的值为5。
相关问题
设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i>=j),在一维数组B的下标位置k的值是?
设下标i,j在矩阵A中对应的一维数组B的下标为k,则有:
k = (i-1)*n - (i-2)(i-1)/2 + j-i
推导如下:
在矩阵A中,第i行前有i-1行,每行有n个元素,因此前i-1行共有(i-1)*n个元素。
对于第i行,其下标从i开始,到n结束,即有n-i+1个元素。但是由于A是对称矩阵,下三角部分与上三角部分相同,因此只需要存储下三角部分,即j<=i,因此第i行只需要存储i个元素。
因此,前i-1行和第i行共有(i-1)*n+i个元素,在一维数组B中的下标为:
k = (i-1)*n + i-1 + j-i
= (i-1)*n - (i-1)(i-2)/2 + j-i
= (i^2-i)/2 + j-i (化简)
因此,对于任一元素ai,j,其在一维数组B中的下标位置k为:
k = (i^2-i)/2 + j-i (i>=j)
若对称矩阵 AnXn按行顺序压缩存储,只存下三角到 一维数组 b 中,则 b 的元素个数是 ,元素 aij 在 b 中的下标是 。
对称矩阵 AnXn 的下三角(包括对角线)中的元素个数是 (n+1)*n/2,因为对称矩阵中,第 i 行第 j 列和第 j 行第 i 列的元素是相等的,只需要存储其中一个即可,因此只有下三角(包括对角线)中的元素需要存储,共有 (n+1)*n/2 个元素。
将下三角按行顺序压缩存储到一维数组 b 中,需要按照以下方式计算元素在 b 中的下标:
- 先计算该元素在矩阵中的行列坐标:对于下标 k,其所对应的元素在矩阵中的行号为 i = floor((sqrt(8*k+1)-1)/2) ,列号为 j = k - i*(i+1)/2。
- 然后再根据行列坐标计算元素在 b 中的下标:对于对称矩阵中的第 i 行第 j 列的元素,其在压缩存储的一维数组 b 中的下标为 b_index = i*(i+1)/2+j。
因此,元素 aij 在 b 中的下标是 b_index = i*(i+1)/2+j = floor((sqrt(8*k+1)-1)/2)*(floor((sqrt(8*k+1)-1)/2)+1)/2+k-floor((sqrt(8*k+1)-1)/2)*floor((sqrt(8*k+1)-1)/2+1)/2。