說明
上三角矩陣是矩陣在對角線以下的元素均為0，即Aij = 0，i > j，例如：
1 2 3 4 5
0 6 7 8 9
0 0 10 11 12
0 0 0 13 14
0 0 0 0 15
下三角矩陣是矩陣在對角線以上的元素均為0，即Aij = 0，i < j，例如：
1 0 0 0 0
2 6 0 0 0
3 7 10 0 0
4 8 11 13 0
5 9 12 14 15
對稱矩陣是矩陣元素對稱於對角線，例如：
1 2 3 4 5
2 6 7 8 9
3 7 10 11 12
4 8 11 13 14
5 9 12 14 15
上三角或下三角矩陣也有大部份的元素不儲存值（為0），我們可以將它們使用一維陣列來儲存以節省儲存空間，而對稱矩陣因為對稱於對角線，所以可以視為上三角或下三角矩陣來儲存。
解法
假設矩陣為nxn，為了計算方便，我們讓陣列索引由1開始，上三角矩陣化為一維陣列，若以列為主，其公式為：
loc = n*(i-1) - i*(i-1)/2 + j
化為以行為主，其公式為：
loc = j*(j-1)/2 + i
下三角矩陣化為一維陣列，若以列為主，其公式為：
loc = i*(i-1)/2 + j
若以行為主，其公式為：
loc = n*(j-1) - j*(j-1)/2 + i
公式的導證其實是由等差級數公式得到，您可以自行繪圖並看看就可以導證出來，對於C/C++或Java等索引由0開始的語言來說，只要將i與j各加1，求得loc之後減1即可套用以上的公式。
#include <stdio.h>
#include <stdlib.h>
#define N 5
int main(void) {
int arr1[N][N] = {
{1, 2, 3, 4, 5},
{0, 6, 7, 8, 9},
{0, 0, 10, 11, 12},
{0, 0, 0, 13, 14},
{0, 0, 0, 0, 15}};
int arr2[N*(1+N)/2] = {0};
int i, j, loc = 0;
printf("\n以列為主：");
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++) {
if(arr1[i][j] != 0)
arr2[loc++] = arr1[i][j];
}
}
for(i = 0; i < N*(1+N)/2; i++)
printf("%d ", arr2[i]);
printf("\n輸入索引(i, j)：");
scanf("%d, %d", &i, &j);
loc = N*i - i*(i+1)/2 + j;
printf("(%d, %d) = %d", i, j, arr2[loc]);
printf("\n");
return 0;
}
import java.util.*;
public class TriangleArray {
private List<Integer> list;
private int length;
public TriangleArray(int[][] array) {
length = array.length;
list = new ArrayList<Integer>(length * (1 + length) / 2);
for(int i = 0; i < length; i++) {
for(int j = 0; j < length; j++) {
if(array[i][j] != 0)
list.add(array[i][j]);
}
}
}
public int get(int i, int j) {
return list.get(length * i - i * (i + 1) / 2 + j);
}
public static void main(String[] args) {
int[][] array = {{1, 2, 3, 4, 5},
{0, 6, 7, 8, 9},
{0, 0, 10, 11, 12},
{0, 0, 0, 13, 14},
{0, 0, 0, 0, 15}};
TriangleArray triangleArray = new TriangleArray(array);
System.out.print(triangleArray.get(2, 2));
}
}
class TriangleArray:
def __init__(self, array):
self.__length = len(array)
self.__list = []
for i in range(self.__length):
for j in range(self.__length):
if array[i][j] != 0:
self.__list.append(array[i][j])
def get(self, i, j):
return self.__list[self.__length * i - i * (i + 1) // 2 + j]
array = [
[1, 2, 3, 4, 5],
[0, 6, 7, 8, 9],
[0, 0, 10, 11, 12],
[0, 0, 0, 13, 14],
[0, 0, 0, 0, 15]
]
triangleArray = TriangleArray(array)
print(triangleArray.get(2, 2))
class TriangleArray(array: Array[Array[Int]]) {
val length = array.length;
val arr = (for(i <- 0 until length; j <- 0 until length
if array(i)(j) != 0
) yield array(i)(j)).toArray
def get(i: Int, j: Int) = {
arr(length * i - i * (i + 1) / 2 + j)
}
}
val array = Array(
Array(1, 2, 3, 4, 5),
Array(0, 6, 7, 8, 9),
Array(0, 0, 10, 11, 12),
Array(0, 0, 0, 13, 14),
Array(0, 0, 0, 0, 15)
)
val triangleArray = new TriangleArray(array)
print(triangleArray.get(2, 2))
class TriangleArray
def initialize(array)
@length = array.length
@list = []
@length.times { |i|
@length.times { |j|
if array[i][j] != 0
@list << array[i][j]
end
}
}
end
def get(i, j)
@list[@length * i - i * (i + 1) / 2 + j]
end
end
array = [
[1, 2, 3, 4, 5],
[0, 6, 7, 8, 9],
[0, 0, 10, 11, 12],
[0, 0, 0, 13, 14],
[0, 0, 0, 0, 15]
]
triangleArray = TriangleArray.new(array)
puts triangleArray.get(2, 2)
|
|