一个n阶上三角矩阵A按行优先顺序压缩存放在一维数组B,则B中元素个数是( )。
时间: 2023-06-13 07:05:19 浏览: 260
一个 n 阶上三角矩阵的元素个数为 $1+2+\cdots+n = \frac{n(n+1)}{2}$,但是由于是上三角矩阵,因此只有矩阵的上三角部分有值,即有 $\frac{n(n+1)}{2} - \frac{n(n-1)}{2} = n$ 个元素。而按行优先顺序压缩存放时,我们只需要存储上三角部分的元素,因此数组 B 中的元素个数应该是 n。
相关问题
若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[0..n(n+1)/2-1]中,A中第一个非0元素A[1][1]存于数组B[0]中,则应存放到B[k]中的非0元素A[i]j的下标i,j与k的对应关系是
### 回答1:
下标 i,j 与 k 的对应关系是:
k = (i-1) * i / 2 + j - 1
其中,i 表示矩阵 A 中非零元素的行号,j 表示矩阵 A 中非零元素的列号,k 表示一维数组 B 中存储该非零元素的下标。由于是下三角矩阵,因此只需存储矩阵中主对角线及其下方的元素。而一维数组 B 中的下标从 0 开始,因此需要将 i 和 j 都减 1 才能与 k 对应。
### 回答2:
若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[0..n(n 1)/2-1]中,A中第一个非0元素A[1][1]存于数组B[0]中,则应存放到B[k]中的非0元素A[i]j的下标i,j与k的对应关系如下:
对于下三角矩阵A中的非零元素A[i][j],其中i >= j,可以将A中的第i行和第j列以及对角线上的所有元素按列优先的顺序存放在一维数组B中。
设第i行第j列的元素在A中的位置为pos,则其在B中的位置为:
pos = j*(j-1)/2 + i
其中,j*(j-1)/2 是第j列之前(不含第j列)元素的个数,加上第i列第j行的元素之后得到元素在B中的位置。
所以,对于A中的非0元素A[i]j,它在B中的位置k与i,j之间的对应关系为:
k = j*(j-1)/2 + i
反过来,对于B中的元素B[k],其对应的A矩阵元素A[i][j]的下标为:
j = int(sqrt(2*k + 0.25) - 0.5)
i = k - j*(j-1)/2
需要注意的是,由于存放到B中的是下三角矩阵A,所以i >= j。
### 回答3:
若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[0..n(n 1)/2-1]中,A中第一个非0元素A[1][1]存于数组B[0]中。则应存放到B[k]中的非0元素A[i][j]的下标i,j与k的对应关系是:
对于矩阵A中的第m行第n列的元素A[m][n],如果m <= n,则将该元素存放在数组B中的位置B[k]中,其中k的计算公式为:
k = (n × (n-1)) / 2 + m - 1
其中,n × (n-1) / 2是n阶下三角矩阵中元素的总个数,(n × (n-1)) / 2 + m - 1是表示在第n列中的第m行对应的位置。
对于非0元素A[m][n],其中m > n,则该元素应为0,不需要存放在数组B中。
例如,对于一个3阶下三角矩阵A[3][3],其元素依次为:
A[1][1] A[1][2] A[1][3]
A[2][1] A[2][2] A[2][3]
A[3][1] A[3][2] A[3][3]
将按列优先顺序压缩存放在一维数组B中,应有:
B[0] = A[1][1]
B[1] = A[2][1]
B[2] = A[2][2]
B[3] = A[3][1]
B[4] = A[3][2]
B[5] = A[3][3]
从上述例子可以看出,上三角矩阵中的非0元素按列优先顺序压缩存放在一维数组B中,且对应关系即为上述计算公式。
若对称矩阵 AnXn按行顺序压缩存储,只存下三角到 一维数组 b 中,则 b 的元素个数是 ,元素 aij 在 b 中的下标是 。
对称矩阵 AnXn按行顺序压缩存储,只存下三角时,可以只存储矩阵的下三角或上三角,因为对称矩阵的上三角和下三角相等。假设只存储下三角,则需要存储的元素个数为:
$$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$$
元素 $a_{i,j}$ 在一维数组 b 中的下标为:
$$
\begin{aligned}
&b_{1} = a_{1,1}\\
&b_{2} = a_{2,1}\\
&b_{3} = a_{3,1}\\
&\cdots\\
&b_{n-1} = a_{n-1,1}\\
&b_{n} = a_{n,1}\\
&b_{n+1} = a_{2,2}\\
&b_{n+2} = a_{3,2}\\
&\cdots\\
&b_{\frac{n(n+1)}{2}} = a_{n,n}
\end{aligned}
$$
其中,$b_i$ 表示数组 b 中的第 i 个元素,$a_{i,j}$ 表示矩阵中的第 i 行第 j 列的元素。可以发现,对于矩阵中下三角的任意一个元素 $a_{i,j}$,它在数组 b 中的下标为 $\frac{i(i-1)}{2}+j$。这个公式的推导可以参考下面的过程:
首先,对于矩阵中的第一行(除去第一个元素 $a_{1,1}$),它的元素在数组 b 中的下标分别为:
$$
\begin{aligned}
&b_{2} = a_{2,1}\\
&b_{3} = a_{3,1}\\
&\cdots\\
&b_{n} = a_{n,1}
\end{aligned}
$$
可以发现,除去第一个元素 $a_{1,1}$,剩下的元素在数组 b 中的下标都是连续的,从 2 开始一直到 n。
对于矩阵中的第二行(除去第一个和第二个元素 $a_{2,1}$ 和 $a_{2,2}$),它的元素在数组 b 中的下标分别为:
$$
\begin{aligned}
&b_{4} = a_{3,2}\\
&b_{5} = a_{4,2}\\
&\cdots\\
&b_{n+1} = a_{n,2}
\end{aligned}
$$
可以发现,除去前两个元素 $a_{2,1}$ 和 $a_{2,2}$,剩下的元素在数组 b 中的下标也是连续的,从 4 开始一直到 n+1。
对于矩阵中的第三行(除去前三个元素 $a_{3,1}$,$a_{3,2}$ 和 $a_{3,3}$),它的元素在数组 b 中的下标分别为:
$$
\begin{aligned}
&b_{6} = a_{4,3}\\
&b_{7} = a_{5,3}\\
&\cdots\\
&b_{n+2} = a_{n,3}
\end{aligned}
$$
同样可以发现,除去前三个元素,剩下的元素在数组 b 中的下标也是连续的,从 6 开始一直到 n+2。
以此类推,对于矩阵中的第 i 行,除去前 i-1 个元素,剩下的元素在数组 b 中的下标也是连续的,从 $\frac{i(i-1)}{2}+1$ 开始一直到 $\frac{i(i-1)}{2}+n-i+1$。
因此,对于任意一个元素 $a_{i,j}$,它在数组 b 中的下标为:
$$\frac{i(i-1)}{2}+j$$