ABC436B 幻方
大约 5 分钟数学
ABC436B 幻方
【算法标签】 数学推导
【语法标签】 :二维数组、for循环、取模运算
给定一个奇数 (),在 的网格中按以下规则填入 的整数:
- 在第一行正中间的格子 填入 。
- 重复以下操作 次(设上次填入的格子为 ,填入的数为 ):
- 尝试往右上角走到
- 如果目标格为空,就在那里填入
- 如果目标格已经有数,就改为正下方 填入
最终每个格子恰有一个数,输出整个网格。
二、解题思路
2.1 这就是传说中的「罗伯法」
这道题的填数规则就是构造奇数阶幻方的经典方法——罗伯法(Siamese method / de la Loubère method)。
所谓「幻方」,就是每行、每列、两条对角线的和都相等(虽然本题不要求验证这个性质,只需按规则填数)。
2.2 规则拆解
规则用一句话说就是:每次先尝试往右上角走,如果右上角已经被占了,就往正下方走。
走的时候要注意边界循环:从第 0 行往上走就是第 N-1 行(即 ),从第 N-1 列往右走就是第 0 列(即 )。相当于网格是一个上下左右都连通的环面。
2.3 手动模拟 N=3
用 · 表示空格,一步步看:
初始:所有格子为空
· · ·
· · ·
· · ·
第1步:在 (0, 1) 填入 1
· 1 ·
· · ·
· · ·
第2步:k=1, (r,c)=(0,1)
尝试右上: ((0-1)%3, (1+1)%3) = (2,2), 为空 → 填入 2
· 1 ·
· · ·
· · 2
第3步:k=2, (r,c)=(2,2)
尝试右上: (1,0), 为空 → 填入 3
· 1 ·
3 · ·
· · 2
第4步:k=3, (r,c)=(1,0)
尝试右上: (0,1), 已经有 1!→ 改为正下方 (2,0), 填入 4
· 1 ·
3 · ·
4 · 2
第5步:k=4, (r,c)=(2,0)
尝试右上: (1,1), 为空 → 填入 5
· 1 ·
3 5 ·
4 · 2
第6步:k=5, (r,c)=(1,1)
尝试右上: (0,2), 为空 → 填入 6
· 1 6
3 5 ·
4 · 2
第7步:k=6, (r,c)=(0,2)
尝试右上: (2,0), 已经有 4!→ 改为正下方 (1,2), 填入 7
· 1 6
3 5 7
4 · 2
第8步:k=7, (r,c)=(1,2)
尝试右上: (0,0), 为空 → 填入 8
8 1 6
3 5 7
4 · 2
第9步:k=8, (r,c)=(0,0)
尝试右上: (2,1), 为空 → 填入 9
8 1 6
3 5 7
4 9 2
完成!可以验证:每行、每列、对角线的和都是 15,这就是著名的三阶幻方。
2.4 实现要点
- 用二维数组记录状态, 表示空,非 表示已填数
- 取模技巧:C++ 中
%对负数取模结果也是负数(如-1 % 3 = -1),所以需要写成(r - 1 + N) % N来确保结果在 范围内 - 循环 次,每次根据规则确定下一个位置并填数
2.5 数据规模
,。纯模拟, 轻松通过。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N]; // a[i][j] = 0 表示该格为空
int main() {
int n;
cin >> n;
// 起点:(0, (n-1)/2),填入 1
int r = 0;
int c = (n - 1) / 2;
a[r][c] = 1;
// 依次填入 2 ~ n*n
for (int k = 2; k <= n * n; k++) {
// 尝试往右上角走
int nr = (r - 1 + n) % n; // 注意 C++ 负数取模要 +n
int nc = (c + 1) % n;
if (a[nr][nc] == 0) {
// 右上角为空,填进去
r = nr;
c = nc;
} else {
// 右上角已被占,改为正下方
r = (r + 1) % n;
// c 不变
}
a[r][c] = k;
}
// 输出
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j];
if (j < n - 1) cout << ' ';
}
cout << endl;
}
return 0;
}取模的坑
C++ 中 % 不是数学意义上的模运算:
cout << (-1) % 3 << endl; // 输出 -1,不是 2!
cout << (-З) % 3 << endl; // 还是 -3所以 (r - 1) % n 当 时会得到 ,数组下标越界。
正确写法:(r - 1 + n) % n,先加 确保非负再取模。
而 (c + 1) % n 不会有负数问题,直接用即可。
四、复杂度分析
| 项目 | 说明 |
|---|---|
| 时间复杂度 | ,一共填入 个数,每次常数操作 |
| 空间复杂度 | ,存储 的网格 |
时,,完全无压力。
五、知识扩展
5.1 奇数阶幻方的性质
用罗伯法构造出的 阶幻方( 为奇数),具有以下性质:
- 幻和(每行/每列/对角线之和)=
- 例如 :幻和 =
- 例如 :幻和 =
学生可以自己验证输出结果是否满足这个性质。
5.2 偶数阶幻方
偶数阶幻方构造方法更复杂,分为:
- 双偶数阶():如 、,用对称交换法
- 单偶数阶():如 、,用 LUX 法或 Strachey 法
这些都是奥数中常见的组合数学内容。
六、易错点
负数取模:
(r-1) % n在 r=0 时为 -1,必须写成(r-1+n) % n正下方规则:被占时是往正下方走,列坐标 不变,不要弄成右下或左下
下标从 0 开始:题目给出的规则用的是 0-based 下标 ,代码保持一致即可,不需要强行转 1-based
