main.cpp

魔方算法 即横竖斜的数字和都相等的方阵

#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;

#define MSIZE 100

int temp1[MSIZE+1][MSIZE+1];
int temp2[MSIZE+1][MSIZE+1];
int temp3[MSIZE+1][MSIZE+1];
int temp4[MSIZE+1][MSIZE+1];
int Magic[MSIZE+1][MSIZE+1];

int mmod(int a,int b)
{
	if(a>=0) return a%b;
	else return b-(-a%b);
}

void Swap(int& a,int& b)
{
	int t=a;
	a=b;
	b=t;
}

void SetMagic(int size)
{
	int i,j;
	//	Odd order.
	if(size%2==1)
	{
		//   [J,I] = meshgrid(1:n);
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
			{
				temp1[i][j]=i;
				temp2[i][j]=j;
			}

		//   A = mod(I+J-(n+3)/2,n);
		//   B = mod(I+2*J-2,n);
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
			{
				temp3[i][j]=mmod(temp1[i][j]+temp2[i][j]-(size+3)/2,size);
				temp4[i][j]=mmod(temp1[i][j]+2*temp2[i][j]-2,size);
			}

		//   M = n*A + B + 1;
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
				Magic[i][j]=size*temp3[i][j]+temp4[i][j]+1;
	}
	//% Doubly even order.
	else if(size%4==0)
	{
		//   [J,I] = meshgrid(1:n);
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
			{
				temp1[i][j]=i;
				temp2[i][j]=j;
			}
		//   K = fix(mod(I,4)/2) == fix(mod(J,4)/2);
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
				temp3[i][j]=(temp1[i][j]%4)/2==(temp2[i][j]%4)/2?1:0;
		
		//   M = reshape(1:n*n,n,n)';
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
				temp4[i][j]=size*(i-1)+j;
		
		//   M(K) = n*n+1 - M(K);
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
				if(temp3[i][j]==1)
					Magic[i][j]=size*size+1-temp4[i][j];
				else
					Magic[i][j]=temp4[i][j];
	}
	//	% Singly even order.
	else
	{
		//   p = n/2;
		int p=size/2;
		//   M = magic(p);
		SetMagic(p);
		//   M = [M M+2*p^2; M+3*p^2 M+p^2];
		for(i=1;i<=size;i++)
			for(j=1;j<=size;j++)
				if(i<=p&&j<=p)
					temp1[i][j]=Magic[i][j];
				else if(i<=p&&j>p)
					temp1[i][j]=Magic[i][j-p]+2*p*p;
				else if(i>p&&j<=p)
					temp1[i][j]=Magic[i-p][j]+3*p*p;
				else
					temp1[i][j]=Magic[i-p][j-p]+p*p;
		//   i = (1:p)';
		//   k = (n-2)/4;
		int k=(size-2)/4;
		//   j = [1:k (n-k+2):n];
		list<int> lj;
		for(i=1;i<=k;i++) 
			lj.push_back(i);
		
		if(k==2) 
		{
			lj.push_back(size);
		}
		else if(k>2)
		{
			lj.push_back(size-k+2);
			lj.push_back(size);
		}
		else
		{
			//do nothing
		}
		
		//   M([i; i+p],j) = M([i+p; i],j);
		for(list<int>::iterator itrj=lj.begin();itrj!=lj.end();itrj++)
			for(i=1;i<=p;i++)
				Swap(temp1[i][*itrj],temp1[p+i][*itrj]);
		//   i = k+1;
		//   j = [1 i];
		lj.clear();
		lj.push_back(1);
		lj.push_back(k+1);

		//   M([i; i+p],j) = M([i+p; i],j);
		for(itrj=lj.begin();itrj!=lj.end();itrj++)
			Swap(temp1[k+1][*itrj],temp1[k+1+p][*itrj]);

		memcpy(Magic,temp1,(MSIZE+1)*(MSIZE+1)*sizeof(int));
	}
}

void main()
{
	int n;
	cin>>n;
	if(n==2||n<1) 
	{
		cout<<"The magic square of size "<<n<<" does not exist."<<endl;
		return;
	}

	SetMagic(n);

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<Magic[i][j]<<"\t";
		cout<<endl;
	}
	return;
}