按"向右上移动、越界环绕、撞格则下移"的规则构造奇数阶幻方。
幻方是 N × N 的方阵,填入 1 ~ N² 使每行、每列、两条对角线上数字之和都相等。当 N 为奇数时有如下填法:
罗伯法取模环绕二维数组模拟奇数阶幻方
| 项目 | 说明 |
|---|---|
| 输入 | 一个正奇数 N |
| 输出 | N 行,每行 N 个空格分隔的正整数 |
| 数据范围 | 3 ≤ N ≤ 21 |
| 阶数 | 保证为奇数 |
| 填法 | 从第 1 行中间开始,向右上斜填 |
nr = (r − 1 + N) % N、nc = (c + 1) % Na[nr][nc] != 0 表示已填nr = (r + 1) % N,列不变先初始化全 0,然后从 (0, 1) 开始填 1。
| 步骤 | 填的数 | 位置 (行, 列) | 说明 |
|---|---|---|---|
| 1 | 1 | (0, 1) | 第 1 行正中央 |
| 2 | 2 | (2, 2) | 右上越上界 → 环绕到最后一行 |
| 3 | 3 | (1, 0) | 右上越右界 → 环绕到第一列 |
| 4 | 4 | (2, 0) | 右上到 (0,1) 已被 1 占 → 下移到 (2,0) |
| 5 | 5 | (1, 1) | 继续右上 |
| 6 | 6 | (0, 2) | 右上越上界 → 环绕 |
| 7 | 7 | (2, 1) | 右上到 (0,2) 已被 6 占 → 下移 |
| 8 | 8 | (1, 2) | 继续右上 |
| 9 | 9 | (0, 0) | 右上越上界 → 环绕 |
上移:(r − 1 + N) % N,加 N 是为了避免负数取模
右移:(c + 1) % N
例如 (0,1) 右上 → ((0−1+3)%3, (1+1)%3) = (2, 2) ✅
环绕逻辑用取模一次搞定
例如准备填 4 时,从 (1,0) 右上到 (0,1)
(0,1) 已有数字 1 → 撞格
改为下移:(1+1)%3 = 2,列不变 → (2, 0) ✅
(2,0) 填 4
8 1 6 3 5 7 4 9 2
验证:每行每列每条对角线之和都是 15 = N(N²+1)/2 ✓
计算 r − 1 时如果 r = 0,结果是 −1,而 C++ 中 −1 % 3 = −1(不是 2!)。这就是必须写成 (r − 1 + N) % N 的原因。
| 表达式 | r = 0 时的结果 | 是否正确 |
|---|---|---|
(r - 1) % N | -1 | ❌ 负数,导致数组越界 |
(r - 1 + N) % N | 2 | ✅ 正确 |
(r + N - 1) % N | 2 | ✅ 等价写法 |
(r - 1) % N 在 r = 0 时会得到 −1,用它当下标会数组越界,程序可能崩溃或输出乱码。记牢:环形下标一定要先加 N 再取模。用 (r-1+N)%N 和 (c+1)%N 一次算出目标位置
int nr = (r - 1 + n) % n, nc = (c + 1) % n; if (a[nr][nc]) { nr = (r + 1) % n; nc = c; }——三行完成"右上 + 撞格下移"。分别判断"是否在第一行""是否在最右列"再决定移动
| 方案 | 代码量 | 边界出错风险 |
|---|---|---|
| 取模环绕 | 约 15 行 | 低 |
| if 判断 | 约 30 行 | 中高 |
输入一个正奇数 N(3 ~ 11),程序会按罗伯法生成幻方。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[25][25]; int main() { int n; scanf("%d", &n); int r = 0, c = n / 2; // 第 1 行正中央 a[r][c] = 1; for (int k = 2; k <= n * n; k++) { // 先尝试向右上移动(加 n 再取模,避免负数) int nr = (r - 1 + n) % n; int nc = (c + 1) % n; if (a[nr][nc] != 0) { // 目标位置已被占用 → 改为向下移动一格 nr = (r + 1) % n; nc = c; // 列不变 } a[nr][nc] = k; r = nr; c = nc; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j) printf(" "); printf("%d", a[i][j]); } printf("\n"); } return 0; }
(r - 1 + n) % n 里的 + n 能省吗?不能省。当 r = 0 时 r - 1 = -1,而 C++ 中 -1 % n = -1(保留负号),用它做下标会越界。先加 n 把被除数变成正数,取模结果自然就落在 [0, n) 里了。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
c = n / 2 | 正中央 | N 为奇数,n/2 正好是中间列(0 基) |
(r - 1 + n) % n | 向上环绕 | +n 是为了避免负数取模 |
(c + 1) % n | 向右环绕 | c+1 最大是 n,取模变回 0 |
nc = c;(撞格时) | 列不变 | 下移只改变行,列保持 |
(r - 1) % n,负数下标导致越界;② 撞格时把列也改了(应该只改行);③ 起始位置写成 (0, n/2) 之外的地方(必须是第 1 行正中央)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 8 1 6 / 3 5 7 / 4 9 2 | 题面样例 |
5 | 17 24 1 8 15 / 23 5 7 14 16 / 4 6 13 20 22 / 10 12 19 21 3 / 11 18 25 2 9 | 5 阶幻方(每行和 65) |
1 | (题目保证 N ≥ 3) | 题目范围外 |
21 | 每行和 = 21 × 442 / 2 = 4641 | 最大规模 |
(r - 1) % n 在 r = 0 时得 −1,必须写成 (r - 1 + n) % n。(0, n/2)。一个 N × N 的数组,最多 21 × 21 = 441 个位置。
✅ 441 次填写,瞬间完成。这题考的是"用取模优雅处理环形边界"这个技巧。
// 环形下标的正确写法(关键技巧) int prevRow = (r - 1 + n) % n; // 上移,环绕 int nextRow = (r + 1) % n; // 下移,环绕 int nextCol = (c + 1) % n; // 右移,环绕 int prevCol = (c - 1 + n) % n; // 左移,环绕 // 通用公式:把 (i + delta) 折到 [0, n) int wrap(int i, int delta, int n) { return ((i + delta) % n + n) % n; } // 幻方的性质 // 每行/每列/对角线的和都等于 n*(n*n+1)/2 // 称为"幻和" // 偶数阶幻方需要别的构造法(如"双偶""单偶"方法) // 本题只要求奇数阶,所以罗伯法足够
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 取模环绕 | (i - 1 + n) % n | 矩阵环绕、循环数组、约瑟夫环 |
| 撞格下移 | 罗伯法的关键分支 | 所有"斜向填数"类构造题 |
| 负数取模陷阱 | C++ 保留负号 | 所有环形下标计算 |