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

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

题目叙述:

[GESP样题 四级] 填幻方

题目描述

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3

样例输出 #1

8 1 6
3 5 7
4 9 2

思路:

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

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

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

取模运算

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

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

取模运算的性质:

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

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

  1. 定义:如果 a 是被除数,n 是除数(n 不为0),那么 a % n 的结果是 a 除以 n 的余数。注意,这里的结果的符号与被除数 a 的符号相同。

  2. 结果范围:对于整数 a 和正整数 n,a % n 的结果是一个在 0 到 n-1 之间的整数(包括 0 和 n-1)。

  3. 与负数的关系:当除数是正数时,被除数为负数时,结果的符号与被除数相同。然而,不同编程语言和编译器在实现取模运算时,对负除数的处理可能有所不同。在C++中,如果除数是负数,结果将依赖于具体的编译器实现,但通常不保证跨所有平台的一致性。

  4. 周期性:取模运算具有周期性。对于任何整数 a 和正整数 n,序列 a % n, (a+1) % n, (a+2) % n, ... 会以 n 为周期重复。这个性质在解决诸如循环数组索引、哈希表冲突解决等问题时非常有用。

  5. 分配律不成立:与乘法运算不同,取模运算不满足分配律,即 (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;
}

热门相关:许你盛世安宁   爆萌宠妃:邪帝,要抱抱   天命为妃   弃妇当家:带着萌宝去种田   寒门状元