双偶数阶魔方阵_动态数组实现

双偶数阶魔方阵_动态数组实现

刚打完代码调试运行无错，兴奋了下，上网找其他高手的实现方式

结果一看，心都凉了。。。

不多说，上代码比较：

我的算法：

 

#include <stdio.h>
#include <stdlib.h>

void Init(int **a,int n);
void Change(int **a,int n);
void Print(int **a,int n);
void main()
{
    int **a;
    int i,n;
  
    do{    
        printf("输入一个双偶数: ");//输入一个双偶数,满足n%4=0

        scanf("%d",&n);
        fflush(stdin);
    }while(n<3||(n%4!=0));

    a=(int **)malloc(n*sizeof(int *)); //建立动态数组

    if(!a) exit(-1);
    for(i=0;i<n;i++)
    {
        a[i]=(int *)malloc(n*sizeof(int));
        if(!a[i]) exit(-1);
    }

    Init(a,n);//初始化
    Change(a,n);//魔方阵转换
    Print(a,n);//输出
    getchar();
}
//初始化函数
void Init(int **a,int n)
{
    int i,j,k=1;
    for(i=0;i<n;i++)    
        for(j=0;j<n;j++)
            a[i][j]=k++;
    return;
}
//转换函数，核心算法   
void Change(int **a,int n)
{
    int m,t,x,y,i,j,_i,_j;//_i,_j标记

    m=n/4;
    for(x=0;x<m;x++)
        for(y=0;y<m;y++)
            if(x<y||((x<(m+1)/2)&&x==y))
            {
                for(i=4*x,_i=0;_i<4;i++,_i++)
                    for(j=4*y,_j=0;_j<4;j++,_j++)
                        if(_i==_j||(_i+_j)%3==0)
                        {
                            t=a[i][j];
                            a[i][j]=a[n-1-i][n-1-j];
                            a[n-1-i][n-1-j]=t;
                        }
            }

    if(m%2!=0) //特例，对于中心矩阵的转换，这里最多执行一步

        for(i=(m+1)%2,_i=0;_i<2;i++,_i++)
            for(j=(m+1)%2,_j=0;_j<4;j++,_j++)
                if(_i==_j||(_i+_j)%3==0)
                    {
                        t=a[i][j];
                        a[i][j]=a[n-1-i][n-1-j];
                        a[n-1-i][n-1-j]=t;
                    }
    return;
}
//输出函数
void Print(int **a,int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)    
            printf("%8d",a[i][j]);
        printf("\n");
    }
    return;
}

 

网上流行的实现方式的核心:

void DEvenMagicSquare(int n)
{
    int m=1;
    int i,j,k;

    //从上至下，从左到右顺序填入矩阵

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[j][i]=m++;
        
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(i%4==0 && abs(i-j)%4==0)//abs求绝对值
                for(k=0;k<4;k++)
                    a[i+k][j+k]=n*n-a[i+k][j+k]+1;
                else if(i%4==3&&(i+j)%4==3)
                    for(k=0;k<4;k++)
                        a[i-k][j+k]=n*n-a[i-k][j+k]+1;
        }
}

网上的算法很灵活，这个是第一点要承认的。而相比之，我的实现有点麻烦而不够精简（当然，如果我除去最后一个特例的实现，在代码方面与之精简应相当）。

网上的版本在查找时只须搜索每个小矩阵左上与左下两个数据，然后利用对角线的特点对需要进行转换的数据进行操作。而在我的实现中，对角线的操作根本没有体现出来，这点关键没有利用，很可惜也让我有点惭愧。

不过，在核心算法的时间复杂度方面，网上算法为O(n*n/2),我的算法为O（n*n/4）,在计算一个非常大的双偶数纵横图时，这点将体现出来，也算是一种安慰吧。。。

 

单偶阶的实现因为已经看了其他人的实现，这里就不写代码了。。。