一个关于矩阵映射的数据结构题

发表于 | 分类于 ，

偶然从网上看到一个到数据结构题目，对 n 阶矩阵，输出如下正方矩阵：

1
2
3
4
5
6
 1   2   6   7  15  16
 3   5   8  14  17  26
 4   9  13  18  25  27
10  12  19  24  28  33
11  20  23  29  32  34
21  22  30  31  35  36

这是个“斜向”递增的自然数列，而打印时只能从上到下，从左到右。如果能用算法将点坐标 （i,j） 映射到自然数列即可。

此矩阵从对角线可分成“左上”和“右下”两个三角形，算法对两个三角形内的点分别处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>

void main(int argc, char *argv[]) {
  int i,j,n,tri,x,l,ri,rj;

  if (argc < 2) n = 6;
  else n = atoi(argv[1]);

  tri = (n * n - n) / 2 + n;

  for (i = 0; i < n; ++i) {
    for (j = 0; j < n; ++j) {
      if (i + j + 1 <= n) {
        // 左上三角形中的点
        l = i + j + 1;  // 当前点所在对角线上的点数
        x = (l * l - l) / 2 + l;
        x = l % 2 == 0 ? x - j : x - i;

        printf("%3d ", x);

      }
      else {
        // 右下三角形中的点
        ri = n - j - 1;
        rj = n - i - 1;
        l = ri + rj + 1;  // 当前点所在对角线上的点数
        x = (l * l - l) / 2 + l;
        x = l % 2 == 0 ? x - ri : x - rj;

        x = n * n - x + 1;
        printf("%3d ", x);
      }
    }
    printf("\n");
  }

}