洛谷B3940 [GESP样题四级] 填幻方

2024-07-26 21:09 由 Tomorrowland_D 发表于 #后端开发

题目链接：https://www.luogu.com.cn/record/168775339

题目叙述：

[GESP样题四级] 填幻方

题目描述

在一个 N×N 的正方形网格中，每个格子分别填上从 1 到 N×N 的正整数，使得正方形中任一行、任一列及对角线的几个数之和都相等，则这种正方形图案就称为“幻方”（输出样例中展示了一个 3×3 的幻方）。我国古代称为“河图”、“洛书”，又叫“纵横图”。

幻方看似神奇，但当 N 为奇数时有很方便的填法：

一开始正方形中没有填任何数字。首先，在第一行的正中央填上 1。
从上次填数字的位置向上移动一格，如果已经在第一行，则移到同一列的最后一行；再向右移动一格，如果已经在最右一列，则移动至同一行的第一列。如果移动后的位置没有填数字，则把上次填写的数字的下一个数字填到这个位置。
如果第 2 步填写失败，则从上次填数字的位置向下移动一格，如果已经在最下一行，则移到同一列的第一行。这个位置一定是空的（这可太神奇了！）。把上次填写的数字的下一个数字填到这个位置。
重复 2、3 步骤，直到所有格子都被填满，幻方就完成了！

快来编写一个程序，按上述规则，制作一个 N×N 的幻方吧。

输入格式

输入为一个正奇数 N，保证 3<=N<=21。

输出格式

输出 N 行，每行 N 个空格分隔的正整数，内容为 N×N 的幻方。

样例 #1

样例输入 #1

样例输出 #1

8 1 6
3 5 7
4 9 2

思路：

这题我们直接根据题意模拟就可以了：

唯一要注意的点就是： 如果已经在第一行，则移到同一列的最后一行和再向右移动一格，如果已经在最右一列，则移动至同一行的第一列,这两句话怎么实现呢？我们要设置四个逻辑判断语句吗？

其实不用，我们使用取模运算，一句话便可以达到这条语句的效果！

取模运算

取模运算广泛应用于有边界的图形当中，尤其是环形或者矩形这种的含边界的处理问题，比如：如果触碰到了已经到了最上面，我们就移动到最下面碰到这种需求时，就体现出了取模运算的重要性！

我们先了解一下取模运算的性质：

取模运算的性质：

在C++（以及许多其他编程语言）中，取模运算（也称为模除、求余运算）是一个重要的算术操作，它用来求得两个数相除后的余数。在C++中，取模运算通常使用 % 符号表示。了解取模运算的性质对于

编写准确和高效的代码至关重要。以下是C++中取模运算的一些基本性质：

定义：如果 a 是被除数，n 是除数（n 不为0），那么 a % n 的结果是 a 除以 n 的余数。注意，这里的结果的符号与被除数 a 的符号相同。
结果范围：对于整数 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 互质时）。这个性质在优化计算或处理复杂表达式时很有用。

因此，在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;
}