神奇的幻方

GitHub跳转原题关系图返回列表

采用暹罗法在 2N-1 阶奇阶方阵中循环右上移动，冲突时向下填入幻方。

OJ: noi_openjudge

题目 ID: ch0108-22

难度:普及-

标签:矩阵模拟构造python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. Python代码
  7. C++代码
    1. 复杂度
    2. 总结

题意

按给定规则构造阶数为 2N−12N-1 的奇阶幻方。

思路

从首行中点填入 11。每次默认尝试向右上循环移动；若目标已填数，则改为从当前格向下移动。取模实现穿越边界后的回绕。

代码

cpp
#include <cstdio>
int n,a[1010][1010],x=1,y;
int main()
{
    scanf("%d",&n);
    y=n;
    int u=(2*n)-1;
    a[x][y]=1;
    for(int i=1;i<=u*u;i++)
    {
        int q=x,w=y;
        if((x==1&&y==u)||(a[x-1][y+1]>0))
            q++;
        else if(x==1){
            q=u;
            w++;
        }
        else if(y>=u){
            q--;
            w=1;
        }
        else if(x==q&&y==w){
            q--;
            w++;
        }
        a[q][w]=i+1;
        x=q;y=w;
    }
    for(int i=1;i<=u;i++)
    {
        for(int j=1;j<=u;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
}

复杂度

总结

Python代码

python
order = int(input())
size = 2 * order - 1
magic_square = [[0] * size for _ in range(size)]
row, column = 0, size // 2

for number in range(1, size * size + 1):
    magic_square[row][column] = number
    next_row = (row - 1) % size
    next_column = (column + 1) % size
    if magic_square[next_row][next_column] != 0:
        row = (row + 1) % size
    else:
        row, column = next_row, next_column

for row in magic_square:
    print(*row)

C++代码

cpp
#include <cstdio>
int n,a[1010][1010],x=1,y;
int main()
{
    scanf("%d",&n);
    y=n;
    int u=(2*n)-1;
    a[x][y]=1;
    for(int i=1;i<=u*u;i++)
    {
        int q=x,w=y;
        if((x==1&&y==u)||(a[x-1][y+1]>0))
            q++;
        else if(x==1){
            q=u;
            w++;
        }
        else if(y>=u){
            q--;
            w=1;
        }
        else if(x==q&&y==w){
            q--;
            w++;
        }
        a[q][w]=i+1;
        x=q;y=w;
    }
    for(int i=1;i<=u;i++)
    {
        for(int j=1;j<=u;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
}

复杂度

方阵边长为 s=2N−1s=2N-1，时间和空间复杂度均为 O(s2)O(s^2)。

总结

奇阶幻方构造的状态只包含当前位置和下一候选位置。