【GESP】C++四级练习 luogu-B3940 [GESP样题四级] 填幻方

发表于 2025/08/11 更新于 2025/08/11

作者 OneCoder

次浏览 10 分钟阅读

GESP C++四级样例。其实和P2615[NOIP 2015 提高组] 神奇的幻方是一模一样的题，只是题目中的文字描述有不同，原题解代码拿来可直接AC。不过，这次带着孩子重新做了一遍，根据本题的描述方式，对代码也进行了一些调整和优化，就当巩固练习吧。

本题为多维数组的应用练习，难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B3940 [GESP样题四级] 填幻方

题目要求

题目描述

在一个 $N\times N$ 的正方形网格中，每个格子分别填上从 1 到 $N×N$ 的正整数，使得正方形中任一行、任一列及对角线的几个数之和都相等，则这种正方形图案就称为“幻方”（输出样例中展示了一个 $3×3$ 的幻方）。我国古代称为“河图”、“洛书”，又叫“纵横图”。
幻方看似神奇，但当 $N$ 为奇数时有很方便的填法：
一开始正方形中没有填任何数字。首先，在第一行的正中央填上 $1$。
从上次填数字的位置向上移动一格，如果已经在第一行，则移到同一列的最后一行；再向右移动一格，如果已经在最右一列，则移动至同一行的第一列。如果移动后的位置没有填数字，则把上次填写的数字的下一个数字填到这个位置。
如果第 2 步填写失败，则从上次填数字的位置向下移动一格，如果已经在最下一行，则移到同一列的第一行。这个位置一定是空的（这可太神奇了！）。把上次填写的数字的下一个数字填到这个位置。
重复 2、3 步骤，直到所有格子都被填满，幻方就完成了！
快来编写一个程序，按上述规则，制作一个 $N\times N$ 的幻方吧。

输入格式

输入为一个正奇数 $N$，保证 $3 \leq N \leq 21$。

输出格式

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

输入 #1

3

输出 #1

1 6
5 7
9 2

题目分析

本题是一道经典的幻方填数问题。主要考察了多维数组的应用和规律推导能力。下面分析解题思路：

解题思路

首先理解幻方的填数规则：
- 从1开始，在第一行中间位置填入1
- 按照”上右”规则尝试填入下一个数
- 如果位置已被占用，则在当前位置下方填入数字
- 重复此过程直到填满整个方阵
关键点分析：
- 需要处理边界情况：
  - 向上超出第一行时，转到最后一行
  - 向右超出最后一列时，转到第一列
  - 向下超出最后一行时，转到第一行
- 使用二维数组存储数据，初始值为0表示未填数
- 记录上一个数字的位置，用于计算下一个位置
具体实现步骤：
- 创建N×N的二维数组
- 计算中间列位置 mid = n/2
- 在array[0][mid]位置填入1
- 循环填入2到n*n的数字：
  - 计算”上右”位置
  - 判断位置是否已填数
  - 根据判断结果选择填数位置
- 最后按格式输出结果

算法复杂度分析

时间复杂度: $O(n^2)$
- 需要填入 $n \times n$ 个数字
- 每个数字填入时的位置计算是 $O(1)$
- 最后输出结果需要遍历整个数组，也是 $O(n^2)$
空间复杂度: $O(n^2)$
- 需要一个 $n \times n$ 的二维数组存储结果
- 其他变量占用空间为 $O(1)$

示例代码

  
#include <iostream>

// 定义一个足够大的二维数组用于存放幻方阵
// 数组大小为25是为了确保能容纳最大的输入规模(21x21)
int array[25][25];

int main() {
    int n;
    std::cin >> n; // 输入幻方阵的阶数n（n为奇数）

    // 初始化：将1放在第一行的中间位置
    int mid = n / 2; // 计算中间列的位置
    array[0][mid] = 1; // 将1放在第一行的中间位置

    // 初始化填数相关变量
    int num = 2; // 下一个要填入的数字
    int l_n = 0, l_m = mid; // l_n, l_m分别表示上一个数字所在的行和列
    int c_n, c_m; // c_n, c_m用于计算下一个数字应该放置的位置（current_n和current_m的缩写）

    // 主循环：按照规则填充整个幻方阵
    while (num <= n * n) {
        // 第一步：尝试"上右"移动
        // 向上移动时的边界处理：第一行则转到最后一行
        c_n = l_n == 0 ? n - 1 : l_n - 1;
        // 向右移动时的边界处理：最后一列则转到第一列
        c_m = l_m == n - 1 ? 0 : l_m + 1;

        // 判断"上右"位置是否可用
        if (array[c_n][c_m] == 0) {
            // 如果"上右"位置为空，则填入当前数字
            array[c_n][c_m] = num; // 填入数字
            num++; // 准备填写下一个数字
            // 更新上一次填数的位置
            l_n = c_n;
            l_m = c_m;
        } else {
            // 如果"上右"位置已被占用，则尝试向下移动
            // 向下移动时的边界处理：最后一行则转到第一行
            c_n = l_n == n - 1 ? 0 : l_n + 1;
            c_m = l_m; // 列位置保持不变
            array[c_n][c_m] = num; // 填入数字，题目描述中说了该位置一定未占用，”神奇“。
            num++; // 准备填写下一个数字
            // 更新上一次填数的位置
            l_n = c_n;
            l_m = c_m;
        }
    }

    // 按格式要求输出幻方阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << array[i][j] << " "; // 输出每个元素，空格分隔
        }
        std::cout << "\n"; // 每行结束换行
    }
    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

GESP, 四级

本文由作者按照 CC BY 4.0 进行授权

luogu-B3940 [GESP样题 四级] 填幻方