幻方

• 下载演示项目 - 26.2 Kb

引言

魔方阵是一个古老的数学问题，许多人尝试解决它。你可能在一些杂志上见过它，或者你的老师可能在课堂上介绍过它。

详细说明

魔方阵是将从 1 到 n² 的数字排列在一个 [n x n] 矩阵中，每个数字恰好出现一次，并且使得任何行、任何列或任何主对角线的条目之和都相同。

不难证明这个和必须是 n [ ( n² + 1) / 2 ]。如果我们对下面的示例输出使用这个公式，对于 [5x5] 矩阵；5 [ ( 52 + 1 ) / 2 ] = 65.

现在，我想向你展示一种使用你熟练的计算机来计算任意阶魔方阵的方法。

暹罗法

这种方法适用于计算奇数阶的魔方阵。它从将 1 放置在任何位置开始（在上面的例子中，位于顶部行中央的方格中），然后以递增的方式将后续数字放置在方格上方和右侧的一个单位处。计数是循环的，因此超出顶部会返回到底部，超出右侧会返回到左侧。当遇到已经填写的方格时，下一个数字将放置在前一个数字下方，然后方法继续进行。这种方法也称为德拉卢贝尔法。

例如，如果方阵的阶数为 5，我们有

void CalculateOddMagicSquare()
{
  n=5;
  int matrix[5][5];

  int nsqr = n * n;
  int i=0, j=n/2;     // start position

  for (int k=1; k<=nsqr; ++k) 
  {
    matrix[i][j] = k;

    i--;
    j++;

    if (k%n == 0) 
    { 
      i += 2; 
      --j; 
    }
    else 
    {
      if (j==n) 
        j -= n;
      else if (i<0) 
        i += n;
    }
  }
}

这里有一个非常好的 Flash 动画，向你展示如何填充方阵的单元格。感谢 KIVANÇ HiKMET ANAR 制作了这个 Flash。

完整代码

下面是计算任意阶魔方阵的完整源代码。

#include "stdafx.h"
#include <vector>

using namespace std;

void OddMagicSquare(vector<vector<int> > &matrix, int n);
void DoublyEvenMagicSquare(vector<vector<int> > &matrix, int n);
void SinglyEvenMagicSquare(vector<vector<int> > &matrix, int n);
void MagicSquare(vector<vector<int> > &matrix, int n);
void PrintMagicSquare(vector<vector<int> > &matrix, int n);

int main(int argc, char* argv[])
{
  int n;
  printf("Enter order of square: ");
  scanf("%d", &n);

  vector<vector<int> > matrix(n, vector<int> (n, 0));

  if (n<3)
  {
    printf("\nError: n must be greater than 2\n\n");
    return -1;
  }

  MagicSquare(matrix, n);  

  //Print results
  PrintMagicSquare(matrix, n);
    
  return 0;
}

void MagicSquare(vector<vector<int> > &matrix,int n)
{
  if (n%2==1)        //n is Odd
    OddMagicSquare(matrix, n);
  else          //n is even
    if (n%4==0)    //doubly even order
      DoublyEvenMagicSquare(matrix, n);
    else      //singly even order
      SinglyEvenMagicSquare(matrix, n);
}

void OddMagicSquare(vector<vector<int> > &matrix, int n)
{
  int nsqr = n * n;
  int i=0, j=n/2;     // start position

  for (int k=1; k<=nsqr; ++k) 
  {
    matrix[i][j] = k;

    i--;
    j++;

    if (k%n == 0) 
    { 
      i += 2; 
      --j; 
    }
    else 
    {
      if (j==n) 
        j -= n;
      else if (i<0) 
        i += n;
    }
  }
}

void DoublyEvenMagicSquare(vector<vector<int> > &matrix, int n)
{
  vector<vector<int> > I(n, vector<int> (n, 0));
  vector<vector<int> > J(n, vector<int> (n, 0));

  int i, j;

  //prepare I, J
  int index=1;
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
    {
      I[i][j]=((i+1)%4)/2;
      J[j][i]=((i+1)%4)/2;
      matrix[i][j]=index;
      index++;
    }

  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
    {
      if (I[i][j]==J[i][j])
        matrix[i][j]=n*n+1-matrix[i][j];
    }
}

void SinglyEvenMagicSquare(vector<vector<int> > &matrix, int n)
{
  int p=n/2;

  vector<vector<int> > M(p, vector<int> (p, 0));
  MagicSquare(M, p);
  
  int i, j, k;

  for (i=0; i<p; i++)
    for (j=0; j<p; j++)
    {
      matrix[i][j]=M[i][j];
      matrix[i+p][j]=M[i][j]+3*p*p;
      matrix[i][j+p]=M[i][j]+2*p*p;
      matrix[i+p][j+p]=M[i][j]+p*p;
    }

  if (n==2)
    return;  

  vector<int> I(p, 0);
  vector<int> J;

  for (i=0; i<p; i++)
    I[i]=i+1;

  k=(n-2)/4;
  
  for (i=1; i<=k; i++)
    J.push_back(i);

  for (i=n-k+2; i<=n; i++)
    J.push_back(i);

  int temp;
  for (i=1; i<=p; i++)
    for (j=1; j<=J.size(); j++)
    {
      temp=matrix[i-1][J[j-1]-1];
      matrix[i-1][J[j-1]-1]=matrix[i+p-1][J[j-1]-1];
      matrix[i+p-1][J[j-1]-1]=temp;
    }

  //j=1, i
  //i=k+1, k+1+p
  i=k; 
  j=0;
  temp=matrix[i][j]; matrix[i][j]=matrix[i+p][j]; matrix[i+p][j]=temp;

  j=i;
  temp=matrix[i+p][j]; matrix[i+p][j]=matrix[i][j]; matrix[i][j]=temp;
}


void PrintMagicSquare(vector<vector<int> > &matrix, int n)
{
  for (int i=0; i<n; i++) 
  {
    for (int j=0; j<n; j++)
      printf(" %3d", matrix[i][j]);

    printf("\n");
  }

  printf("\n\n");
}

结论

尽情享用！