数据结构设计——魔方阵【绝对整理清楚】

魔方阵是一个古老的智力问题，它要求在一个m*m的矩阵中填入1~m*m的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等，如下图所示：

程序：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 100
int main()
{   int a[M][M];
    memset(a,0,sizeof(0));
    int x,y,k,m;
    printf("输入阶数:");
    scanf("%d",&m) ;
    while(!((m!=0)&&(m<M)&&(m%2!=0)))
    {
        printf("错误请重新输入:");
        scanf("%d",&m);//m = 3
    }
    x=0;
    y=(m - 1)/2;
    a[x][y]=1;
    for(k=2;k<=m*m;k++){
       x=(x-1+m)%m;
       y=(y-1+m)%m;
       if(a[x][y]==0){
         a[x][y]=k;
       }else{
           x=(x+2)%m;
           y=(y+1)%m;
           a[x][y]=k;
        }
    }
    printf("输出的矩阵为：\n");
    for(x=0;x<m;x++){
        for(y=0;y<m;y++)
        printf("%d\t",a[x][y]);
        printf("\n");
    }
    return 0;
}

【解析】

首先：题目要求是在 m*m 阶阵列中填入1，2，3.....m*m
其次：题目要保证每一行、每一列，对角线方向的所有的数的和相同

 显然，每个元素的选择对全局的平衡有影响。那么，大平衡时，必然局部平衡，只有保证每个局部都平衡，才可以保证大局平衡

所以在分配中要 利用 “一多一少” 来满足“∑各个方向的各个数”相同

以3*3矩阵为例：

         ——寻找3组元素构成中间序列————>    

 【1】

由于 5 是中间序列的中间的元素，为了达到平衡，必须选择较小序列（1，2，3）中的最小值 1 和较大序列（7，8，9）中的最大值 9 ·

【2】

 由于 6 是中间序列的偏大的元素，为了达到平衡，必须选择较小序列(2,3)中的最小值 2 和较大序列(7,8)中的最小值 7，抵消 “偏大”带来的影响 

同理可得”3，4，8“

 【3】

由于在构建过程中，每个局部都是平衡的，大小的影响都会被抵消，那么大平衡必然平衡

此时，所构成的矩阵中，列向 和 对角线方向 所填的数字满足之和相同，即已平衡
横向平衡如何实现？？【所填数字之和相同】

 接着，对超过边界的进行 同向求模移位操作：

【比如，在上方右图中，”7“在对角线序列(4,5,6) 中”4‘的 左1，下2，即从“4”开始，超过边界的移位进行同方向求模移位，即：往左1，到“6”所在列 且 在“6”下方2单位处，再往下2，到“6”所在位置向下1单位处，如下图】

综上分析，完全可以对该序列先升序排序，然后取得中间序列，以中间序列数组为矩阵的对角线序列，再将两边的序列像千层饼一样依次错位层加，构造魔方阵

在上方层次叠加模型中，可以发现1的位置是永远不会变的
【因为以中间序列为对角线元素时,从对角线底部到最上方以“1”开始的层列 所经过的横向长度必然是 （m-1）/ 2 = （序列组数-1）/ 2 ，其中1代表中间序列，即，数字“1”所在的位置必然是 ( 0,(m-1)/2 )】

之后按照层次模型，从1开始往斜上方依次填充矩阵，超越矩阵范围的，通过求模解决；当每一层次填充完毕后，求模操作中对应的x ，y 会返回至最开始的层次起点，那么就直接从起点 往右2，往下1 开始填充新的层次

流程图如下：

制作整理不易，图片均自制。如需转载，请注明出处和作者。

如果有更清晰简单的方法，欢迎评论~~