洛谷B3940 [GESP样题 四级] 填幻方
Tomorrowland 2024-07-27 08:09:00 阅读 70
题目链接:https://www.luogu.com.cn/record/168775339
题目叙述:
[GESP样题 四级] 填幻方
题目描述
在一个 N×N 的正方形网格中,每个格子分别填上从 1 到 N×N 的正整数,使得正方形中任一行、任一列及对角线的几个数之和都相等,则这种正方形图案就称为“幻方”(输出样例中展示了一个 3×3 的幻方)。我国古代称为“河图”、“洛书”,又叫“纵横图”。
幻方看似神奇,但当 N 为奇数时有很方便的填法:
- <li>一开始正方形中没有填任何数字。首先,在第一行的正中央填上 1。
- 从上次填数字的位置向上移动一格,如果已经在第一行,则移到同一列的最后一行;再向右移动一格,如果已经在最右一列,则移动至同一行的第一列。如果移动后的位置没有填数字,则把上次填写的数字的下一个数字填到这个位置。
- 如果第 2 步填写失败,则从上次填数字的位置向下移动一格,如果已经在最下一行,则移到同一列的第一行。这个位置一定是空的(这可太神奇了!)。把上次填写的数字的下一个数字填到这个位置。
- 重复 2、3 步骤,直到所有格子都被填满,幻方就完成了!
快来编写一个程序,按上述规则,制作一个 N×N 的幻方吧。
输入格式
输入为一个正奇数 N,保证 3<=N<=21。
输出格式
输出 N 行,每行 N 个空格分隔的正整数,内容为 N×N 的幻方。
样例 #1
样例输入 #1
<code>3
样例输出 #1
8 1 6
3 5 7
4 9 2
思路:
这题我们直接根据题意模拟就可以了:
唯一要注意的点就是: 如果已经在第一行,则移到同一列的最后一行
和再向右移动一格,如果已经在最右一列,则移动至同一行的第一列
,这两句话怎么实现呢?我们要设置四个逻辑判断语句吗?
其实不用,我们使用取模运算,一句话便可以达到这条语句的效果!
取模运算
取模运算广泛应用于有边界的图形当中,尤其是环形或者矩形这种的含边界的处理问题,比如:如果触碰到了已经到了最上面,我们就移动到最下面
碰到这种需求时,就体现出了取模运算的重要性!
我们先了解一下取模运算的性质:
取模运算的性质:
在C++(以及许多其他编程语言)中,取模运算(也称为模除、求余运算)是一个重要的算术操作,它用来求得两个数相除后的余数。在C++中,取模运算通常使用 % 符号表示。了解取模运算的性质对于
编写准确和高效的代码至关重要。以下是C++中取模运算的一些基本性质:
- <li>
结果范围:对于整数 a 和正整数 n,a % n 的结果是一个在 0 到 n-1 之间的整数(包括 0 和 n-1)。
与负数的关系:当除数是正数时,被除数为负数时,结果的符号与被除数相同。然而,不同编程语言和编译器在实现取模运算时,对负除数的处理可能有所不同。在C++中,如果除数是负数,结果将依赖于具体的编译器实现,但通常不保证跨所有平台的一致性。
周期性:取模运算具有周期性。对于任何整数 a 和正整数 n,序列 a % n, (a+1) % n, (a+2) % n, ... 会以 n 为周期重复。这个性质在解决诸如循环数组索引、哈希表冲突解决等问题时非常有用。
分配律不成立:与乘法运算不同,取模运算不满足分配律,即 (a+b) % n 不一定等于 a % n + b % n。但是,有一个类似的性质,即 (a+b) % n = ((a % n) + (b % n)) % n,这在进行取模运算时非常有用,尤其是在处理大数时,可以减少中间结果的规模。
结合律成立:虽然分配律不成立,但取模运算满足结合律,即 (a % n) % m 等于 a % (n * m)(当 n 和 m 互质时)。这个性质在优化计算或处理复杂表达式时很有用。
定义:如果 a 是被除数,n 是除数(n 不为0),那么 a % n 的结果是 a 除以 n 的余数。注意,这里的结果的符号与被除数 a 的符号相同。
因此,在C++中,如果对一个负数做取模运算,结果是不确定的,我们得额外处理这个逻辑,就拿这道题举例子,我们假设当前处于的行为curRow
,经过变换后的行数为newRow
,(向上移动一行)我们如果不是第一行的
话,直接写出以下式子: newRow=(curRow-1)%n;
,但是curRow=0时,curRow-1就为负数了!取模的结果就变成未知了!因此我们需要对这个式子额外处理,变成newRow=(curRow-1+n)%n
就可以保证我们的
运算的答案在0-n-1之间。
思路:
经过上面的讲解,相信大家对取模运算就有了基本的认识了,那么我们直接上代码:
#include<iostream>
using namespace std;
//全局变量会自动初始化为0
int a[22][22];
int main()
{
int n; cin >> n;
int i = 1;
int curRow = 0, curCol = n / 2;
while (i <= n * n) {
if (a[curRow][curCol] == 0) {
a[curRow][curCol] = i;
//进行步骤二
int newRow = (curRow - 1 + n) % n;
int newCol = (curCol + 1) % n;
//步骤二不成立
if (a[newRow][newCol] != 0) {
newRow = (curRow + 1) % n;
newCol = curCol;
}
//更新当前所在行数和当前所在列数
curRow = newRow;
curCol = newCol;
i++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。