魔方阵算法及C语言实现

C/C++ 2013年07月31日 , ,

1 魔方阵概念

魔方阵是指由1,2,3……n2填充的,每一行每一列对角线之和均相等的方阵,阶数n = 3,4,5…。魔方阵也称为幻方阵

例如三阶魔方阵为:magic-1

魔方阵有什么的规律呢?

魔方阵分为奇幻方和偶幻方。而偶幻方又分为是4的倍数(如4,8,12……)和不是4的倍数(如6,10,14……)两种。下面分别进行介绍。

2 奇魔方的算法

2.1 奇魔方的规律与算法

奇魔方(阶数n = 2 * m + 1,m =1,2,3……)规律如下:

  1. 数字1位于方阵中的第一行中间一列;
  2. 数字a(1 < a  ≤ n2)所在行数比a-1行数少1,若a-1的行数为1,则a的行数为n;
  3. 数字a(1 < a  ≤ n2)所在列数比a-1列数大1,若a-1的列数为n,则a的列数为1;
  4. 如果a-1是n的倍数,则a(1 < a  ≤ n2)的行数比a-1行数大1,列数与a-1相同。

2.2 奇魔方算法的C语言实现

#include
// Author: http://furzoom.com/
// N为魔方阶数
#define N 11

int main()
{
    int a[N][N];
    int i;
    int col,row;

    col = (N-1)/2;
    row = 0;

    a[row][col] = 1;

    for(i = 2; i < = N*N; i++)
    {
        if((i-1)%N == 0 )
        {
            row++;
        }
        else
        {
            // if row = 0, then row = N-1, or row = row - 1
            row--;
            row = (row+N)%N;

            // if col = N, then col = 0, or col = col + 1
            col ++;
            col %= N;
        }
        a[row][col] = i;
    }
    for(row = 0;row<N;row++)
    {
        for(col = 0;col < N; col ++)
        {
            printf("%6d",a[row][col]);
        }
        printf("\n");
    }
    return 0;
}

3 偶魔方的算法

偶魔方的情况比较特殊,分为阶数n = 4 * m(m =1,2,3……)的情况和阶数n = 4 * m + 2(m = 1,2,3……)情况两种。

3.1 阶数n = 4 * m(m =1,2,3……)的魔方(双偶魔方)

算法1:阶数n = 4 * m(m =1,2,3……)的偶魔方的规律如下:

  1. 按数字从小到大,即1,2,3……n2顺序对魔方阵从左到右,从上到下进行填充;
  2. 将魔方中间n/2列的元素上、下进行翻转;
  3. 将魔方中间n/2行的元素左、右进行翻转。

C语言实现

#include
// Author: http://furzoom.com/
// N为魔方阶数,
#define N 12

int main()
{
    int a[N][N];//存储魔方
    int i, temp;//临时变量
    int col, row;//col 列,row 行

    //初始化
    i = 1;
    for(row = 0;row < N; row++)
    {
        for(col = 0;col < N; col ++)
        {
            a[row][col] = i;
            i++;
        }
    }

    //翻转中间列
    for(row = 0; row < N/2; row ++)
    {
        for(col = N/4;col < N/4*3;col ++)
        {
            temp = a[row][col];
            a[row][col] = a[N-row-1][col];
            a[N-row-1][col] = temp;
        }
    }

    //翻转中间行
    for(col = 0; col < N/2; col ++)
    {
        for(row = N/4;row < N/4 * 3;row ++)
        {
            temp = a[row][col];
            a[row][col] = a[row][N-col-1];
            a[row][N-col-1] = temp;
        }
    }

    for(row = 0;row < N; row++)
    {
        for(col = 0;col < N; col ++)
        {
            printf("%5d",a[row][col]);
        }
        printf("\n");
    }
    return 0;
}

算法2:阶数n = 4 * m(m =1,2,3……)的偶魔方的规律如下:

  1. 按数字从小到大,即1,2,3……n2顺序对魔方阵从左到右,从上到下进行填充;
  2. 将魔方阵分成若干个4×4子方阵,将子方阵对角线上的元素取出;
  3. 将取出的元素按从大到小的顺序依次填充到n×n方阵的空缺处。

C语言实现

#include
// Author: http://furzoom.com/
// N为魔方阶数
#define N 12

int main()
{
	int a[N][N];//存储魔方
	int temparray[N*N/2];//存储取出的元素
	int i;//循环变量
	int col, row;// col 列,row 行

	//初始化
        i = 1;
        for(row = 0;row < N; row++)
        {
            for(col = 0;col < N; col ++)
            {
                a[row][col] = i;
                i++;
            }
        }
	//取出子方阵中对角线上的元素,且恰好按从小到大的顺序排放
 	i = 0;
 	for(row = 0;row < N; row++)
 	{
 		for(col = 0;col < N; col ++)
 		{
			 if((col % 4 == row % 4) || ( 3 == ( col % 4 + row % 4)))
			{
 				temparray[i] = a[row][col];
 				i++;
			}
 		}
 	}
	//将取出的元素按照从大到小的顺序填充到n×n方阵中
 	i = N*N/2 -1;
 	for(row = 0;row < N; row++)
 	{
 		for(col = 0;col < N; col ++)
 		{
 			if((col % 4 == row % 4) || ( 3 == ( col % 4 + row % 4)))
 			{
 				a[row][col] = temparray[i];
 				i--;
 			}
 		}
 	}
	//输出方阵
 	for(row = 0;row < N; row++)
 	{
 		for(col = 0;col < N; col ++)
 		{
 			printf("%5d",a[row][col]);
 		}
 		printf("\n");
 	}
	return 0;
}

3.2 阶数n = 4 * m + 2(m =1,2,3……)的魔方(单偶魔方)

算法

设k = 2 * m + 1;单偶魔方是魔方中比较复杂的一个。magic-2

  1. 将魔方分成A、B、C、D四个k阶方阵,如下图这四个方阵都为奇方阵,利用上面讲到的方法依次将A、D、B、C填充为奇魔方。
  2. 交换A、C魔方元素,对魔方的中间行,交换从中间列向右的m列各对应元素;对其他行,交换从左向右m列各对应元素。
  3. 交换B、D魔方元素,交换从中间列向左m - 1列各对应元素。

C语言实现

#include
// Author: http://furzoom.com/
// N为魔方阶数
#define N 10

int main()
{
	int a[N][N] = { {0} };//存储魔方
	int i,k,temp;
	int col,row;// col 列,row 行

	//初始化
	k = N / 2;
	col = (k-1)/2;
	row = 0;
	a[row][col] = 1;
	//生成奇魔方A
	for(i = 2; i < = k*k; i++)
	{
		if((i-1)%k == 0 )//前一个数是3的倍数
		{
			row++;
		}
		else
		{
			// if row = 0, then row = N-1, or row = row - 1
			row--;
			row = (row+k)%k;

			// if col = N, then col = 0, or col = col + 1
			col ++;
			col %= k;
		}
		a[row][col] = i;
	}

	//根据A生成B、C、D魔方
	for(row = 0;row < k; row++)
    {
        for(col = 0;col < k; col ++)
        {
            a[row+k][col+k] = a[row][col] + k*k;
            a[row][col+k] = a[row][col] + 2*k*k;
            a[row+k][col] = a[row][col] + 3*k*k;
        }
    }

    // Swap A and C
    for(row = 0;row < k;row++)
    {
        if(row == k / 2)//中间行,交换从中间列向右的m列,N = 2*(2m+1)
        {
            for(col = k / 2; col < k - 1; col++)
            {
                temp = a[row][col];
                a[row][col] = a[row + k][col];
                a[row + k][col] = temp;
            }
        }
        else//其他行,交换从左向右m列,N = 2*(2m+1)
        {
            for(col = 0;col < k / 2;col++)
            {
                temp = a[row][col];
                a[row][col] = a[row + k][col];
                a[row + k][col] = temp;
            }
        }
    }

    // Swap B and D
    for(row = 0; row < k;row++)//交换中间列向左m-1列,N = 2*(2m+1)
    {
        for(i = 0;i < (k - 1)/2 - 1;i++)
        {
            temp = a[row][k+ k/2 - i];
            a[row][k+ k /2 -i] = a[row + k][k+k/2 -i];
            a[row + k][k+k/2 -i] = temp;
        }
    }

	//输出魔方阵
	for(row = 0;row < N; row++)
	{
		for(col = 0;col < N; col ++)
		{
			printf("%5d",a[row][col]);
		}
		printf("\n");
	}

	return 0;
}

本文地址:http://furzoom.com/magic-square/

你若要放弃,那我就可以安慰自己了,因为这样我不再孤独了,可以参考能够不断往前走,成功难道不是早晚的是事吗?

如无特别说明,本站文章皆为原创,若要转载,务必请注明以下原文信息:
日志标题:《魔方阵算法及C语言实现》
日志链接:http://furzoom.com/magic-square/
博客名称:枫竹梦

发表评论

插入图片

NOTICE1:请申请gravatar头像,没有头像的评论可能不会被回复!

回到顶部