GESP 题解库 / 4 级题解 / [GESP样题 四级] 填幻方 · 第 22 / 25 题
GESP样题 四级 · B3940 · 简单

填幻方

按"向右上移动、越界环绕、撞格则下移"的规则构造奇数阶幻方。

📊
3 ≤ N ≤ 21
阶数(奇数)
🔢
int
数值类型
⚡
O(N²)
时间复杂度
🎯
规则模拟 + 取模环绕
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

幻方是 N × N 的方阵,填入 1 ~ N² 使每行、每列、两条对角线上数字之和都相等。当 N 为奇数时有如下填法:

  1. 在第一行的正中央填 1
  2. 从上次填数的位置向上移动一格(已在第一行则移到同一列的最后一行);再向右移动一格(已在最右列则移到同一行的第一列)。若该位置为空,就填下一个数
  3. 若第 2 步的位置已被占,则改为从上次位置向下移动一格(已在最后一行则移到第一行),这个位置一定是空的,填下一个数
  4. 重复第 2、3 步直到填满
💡
人话翻译:这是著名的"罗伯法"(Siamese method)。记忆口诀:「右上斜填,出上填下,出右填左,遇阻下移」。用取模运算就能优雅地实现"越界环绕"。

🔍 关键词提取

罗伯法取模环绕二维数组模拟奇数阶幻方

已知条件

项目说明
输入一个正奇数 N
输出N 行,每行 N 个空格分隔的正整数
数据范围3 ≤ N ≤ 21
阶数保证为奇数
填法从第 1 行中间开始,向右上斜填

需要解决的问题

02
思维导图
整理解题思路的全貌
🔮 罗伯法:右上斜填
📥 初始化
N × N 数组置 0
从第 1 行中间开始
即 (0, N/2) 填 1
N 为奇数保证有正中央
➡️ 右上移动
nr = (r − 1 + N) % N
nc = (c + 1) % N
取模实现环绕
出上填下、出右填左
🚧 撞格处理
若 a[nr][nc] 非 0
改为 nr = (r + 1) % N
列不变
该位置必定为空
⚠️ 易错点
忘记取模导致越界
撞格时列也跟着变(应不变)
取模写成 (r-1)%N(负数)
循环次数写成 N 而非 N²
03
样例手算推导
3 阶幻方的逐步填写

🧮 N = 3 的完整填写过程

先初始化全 0,然后从 (0, 1) 开始填 1。

步骤填的数位置 (行, 列)说明
11(0, 1)第 1 行正中央
22(2, 2)右上越上界 → 环绕到最后一行
33(1, 0)右上越右界 → 环绕到第一列
44(2, 0)右上到 (0,1) 已被 1 占 → 下移到 (2,0)
55(1, 1)继续右上
66(0, 2)右上越上界 → 环绕
77(2, 1)右上到 (0,2) 已被 6 占 → 下移
88(1, 2)继续右上
99(0, 0)右上越上界 → 环绕
1
每次"右上"用取模实现

上移:(r − 1 + N) % N,加 N 是为了避免负数取模

右移:(c + 1) % N

例如 (0,1) 右上 → ((0−1+3)%3, (1+1)%3) = (2, 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) % N2✅ 正确
(r + N - 1) % N2✅ 等价写法
⚠️
这是本题最容易出错的地方。C++ 的取模运算对负数保留负号,所以 (r - 1) % N 在 r = 0 时会得到 −1,用它当下标会数组越界,程序可能崩溃或输出乱码。记牢:环形下标一定要先加 N 再取模。
04
解法对比
取模环绕 vs if 判断边界

⚔️ 解法对比

🟢 取模环绕(推荐) 推荐

用 (r-1+N)%N 和 (c+1)%N 一次算出目标位置

  • 时间 O(N²)
  • 每步 O(1)
  • 代码 15 行
  • 不需要写边界 if
💡
核心代码:int nr = (r - 1 + n) % n, nc = (c + 1) % n; if (a[nr][nc]) { nr = (r + 1) % n; nc = c; }——三行完成"右上 + 撞格下移"。

🟠 if 判断四个边界

分别判断"是否在第一行""是否在最右列"再决定移动

  • 功能等价
  • 代码多 10 行以上
  • 四个分支容易漏或写错
  • 不如取模简洁
⚠️
注意:用 if 写法时,"上移 + 右移"两个方向都要单独判断边界,而且"撞格下移"时也要判断是否在最后一行——一共 3 处边界判断,出错的几率明显更高。

📈 性能对比

方案代码量边界出错风险
取模环绕约 15 行低
if 判断约 30 行中高
05
算法流程图
按罗伯法逐格填写
开始读入 N;数组 a[N][N] 全部置 0r = 0,c = N / 2;a[r][c] = 1k 从 2 到 N × Nnr = (r − 1 + N) % N,nc = (c + 1) % Na[nr][nc] 已经被填了吗?是 ✓nr = (r + 1) % N,nc = c(改为下移)否 ✗保持右上移动的结果a[nr][nc] = k;r = nr,c = nc输出整个方阵结束还有数字没填 → k 加 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔮 幻方生成器

输入一个正奇数 N(3 ~ 11),程序会按罗伯法生成幻方。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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 行正中央)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
38 1 6 / 3 5 7 / 4 9 2题面样例
517 24 1 8 15 / 23 5 7 14 16 / 4 6 13 20 22 / 10 12 19 21 3 / 11 18 25 2 95 阶幻方(每行和 65)
1(题目保证 N ≥ 3)题目范围外
21每行和 = 21 × 442 / 2 = 4641最大规模
✅
自查清单:① 取模前加 N 了吗?② 撞格时只改行吗?③ 起始位置对吗?

🚨 易错点清单

⚠️
负数取模:(r - 1) % n 在 r = 0 时得 −1,必须写成 (r - 1 + n) % n。
⚠️
撞格时列也变了:下移只改变行,列必须保持不变。
⚠️
起始位置错:必须是第 1 行正中央,即 0 基的 (0, n/2)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N²)
空间复杂度
O(N²)
N 最大
21
格子数
441

时间怎么算的?

空间都用在哪?

一个 N × N 的数组,最多 21 × 21 = 441 个位置。

✅ 441 次填写,瞬间完成。这题考的是"用取模优雅处理环形边界"这个技巧。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 环形下标的正确写法(关键技巧)
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++ 保留负号所有环形下标计算
🌟
思考题:你能验证"每行之和都等于 N(N²+1)/2"吗?(提示:1 + 2 + … + N² = N²(N²+1)/2,平均分到 N 行,每行就是 N(N²+1)/2。这说明了幻和必然是这个值,可以用来检查自己的输出是否正确——写程序时加一句断言就能快速定位错误。)