当前位置：首页 > ds >正文

[蓝桥杯]上三角方阵

ds 2025/8/19 21:14:32

上三角方阵

题目描述

方阵的主对角线之上称为"上三角"。

请你设计一个用于填充 nn 阶方阵的上三角区域的程序。填充的规则是：使用 1，2，3.... 的自然数列，从左上角开始，按照顺时针方向螺旋填充。

例如：当 n=3n=3 时，输出：

1 2 3

6 4

当 n=4n=4 时，输出：

1 2 3 4

9 10 5

8 6

当 n=5n=5 时，输出：

1 2 3 4 5

12 13 14 6

11 15 7

10 8

输入描述

要求用户输入整数 n （3≤n≤20）n （3≤n≤20）。

输出描述

输出方阵的上三角部分。

要求每个数据宽度为 4，右对齐。

输入输出样例

示例

输入

输出

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

运行限制

最大运行时间：1s
最大运行内存: 256M

总通过次数: 832 | 总提交次数: 900 | 通过率: 92.4%

难度: 中等标签: 2011, 模拟, 省赛

问题分析

题目要求设计一个程序，用自然数1, 2, 3,... 按顺时针螺旋顺序填充n阶方阵的上三角区域。上三角区域定义为方阵主对角线（含）以上的部分。填充后需按特定格式输出：每行数据宽度为4，右对齐，且输出为锯齿状矩阵（第i行有n-i个元素）。

算法思路

路径模拟：
- 使用方向数组控制螺旋路径：右 (0,1) → 左下 (1,-1) → 上 (-1,0)
- 从(0,0)开始，按优先级选择方向：先尝试当前方向，若无效则按右→左下→上顺序切换
- 位置(r,c)有效条件：
  - 在矩阵范围内：0 ≤ r,c < n
  - 在上三角区域内：c ≤ n - r - 1
  - 目标位置未被填充
填充过程：
- 计算总元素数：T = n(n+1)/2
- 初始化n×n矩阵，所有元素为0
- 从k=1到T，依次填充数字：
  1. 将当前值k赋给矩阵位置(r,c)
  2. 尝试三种方向，找到第一个有效移动位置
  3. 更新坐标(r,c)和当前方向

输出格式：

按锯齿状输出：第i行输出前n-i个元素

每个元素占4字符宽度，右对齐（C++中setw(4)）

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;int main() {int n;cin >> n;int T = n * (n + 1) / 2;  // 上三角区域总元素数vector<vector<int>> a(n, vector<int>(n, 0));  // 初始化n×n矩阵// 方向数组：右(0,1) -> 左下(1,-1) -> 上(-1,0)int dr[3] = {0, 1, -1};int dc[3] = {1, -1, 0};int r = 0, c = 0;          // 起始位置(0,0)int current_dir = 0;        // 初始方向：右for (int k = 1; k <= T; ++k) {a[r][c] = k;           // 填充当前值if (k == T) break;     // 填充完成bool found = false;for (int i = 0; i < 3; ++i) {int nd = (current_dir + i) % 3;  // 尝试方向优先级：当前→下一→下下int nr = r + dr[nd];int nc = c + dc[nd];// 检查新位置是否有效if (nr >= 0 && nr < n && nc >= 0 && nc < n && nc <= n - nr - 1 && a[nr][nc] == 0) {r = nr;c = nc;current_dir = nd;  // 更新方向found = true;break;}}if (!found) break;  // 无有效位置（理论上不会发生）}// 输出锯齿状上三角矩阵for (int i = 0; i < n; ++i) {for (int j = 0; j < n - i; ++j) {cout << setw(4) << a[i][j];}cout << endl;}return 0;
}

关键步骤说明

方向控制：
- 右移：列坐标+1，用于填充当前行
- 左下移：行坐标+1且列坐标-1，用于斜向填充
- 上移：行坐标-1，用于填充左侧列
- 方向切换确保路径始终顺时针螺旋
边界检查：
- 矩阵边界：0 ≤ r,c < n
- 上三角边界：c ≤ n - r - 1（确保不越出上三角区域）
- 已填充检查：目标位置值为0
复杂度分析：
- 时间复杂度：O(n²)，需填充n(n+1)/2个元素
- 空间复杂度：O(n²)，存储n×n矩阵
- 满足运行限制（n≤20时，计算量远低于1s）
示例验证

输入n=3：
```
   1   2   36   45
```
路径轨迹：
(0,0)→(0,1)→(0,2) // 右移填充顶边
(1,1)→(2,0) // 左下移填充斜边
(1,0) // 上移填充左边
输入n=4：
```
   1   2   3   49  10   58   67
```
路径轨迹：
(0,0)→(0,1)→(0,2)→(0,3) // 右移
(1,2)→(2,1)→(3,0) // 左下移
(2,0)→(1,0) // 上移
(1,1) // 右移