①问题描述
魔方阵是一个古老的智力问题，它要求在一个m×m的矩阵中填入1～m2的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等，如图1所示。
|
15 |
8 |
1 |
24 |
17 |
|
16 |
14 |
7 |
5 |
23 |
|
22 |
20 |
13 |
6 |
4 |
|
3 |
21 |
19 |
12 |
10 |
|
9 |
2 |
25 |
18 |
11 |
图1 五阶魔方阵示例
②基本要求
-
输入魔方阵的行数m，要求m为奇数，程序对所输入的m作简单的判断，如m有错，能给出适当的提示信息。
-
实现魔方阵。
-
输出魔方阵。
③实现提示
本实验使用的数据结构是数组。
解魔方阵问题的方法很多，这里采用如下规则生成魔方阵。
-
由1开始填数，将1放在第0行的中间位置。
-
将魔方阵想象成上下、左右相接，每次往左上角走一步，会有下列情况：
-
左上角超出上方边界，则在最下边相对应的位置填入下一个数字；
-
左上角超出左边边界，则在最右边相应的位置填入下一个数字；
-
如果按上述方法找到的位置已填入数据，则在同一列下一行填入下一个数字。
-
以3×3魔方阵为例，说明其填数过程，如图2所示。
图2 三阶魔方阵的生成过程
由三阶魔方阵的生成过程可知，某一位置(x,y)的左上角的位置是(x-1,y-1),如果x-1≥0，不用调整，否则将其调整为x-1+m；同理，如果y-1≥0，不用调整，否则将其调整为y-1+m。所以，位置(x,y)的左上角的位置可以用求模的方法获得，即：
x=(x-1+m)%m
y=(y-1+m)%m
如果所求的位置已经有数据了，将该数据填入同一列下一行的位置。这里需要注意的是。此时的x和y已经变成之前的上一行上一列了，如果想变回之前位置的下一行同一列，x需要跨越两行，y需要跨越一列，即：
x=(x+2)%m
y=(y+1)%m
④思考
-
可以考虑使用其他方法生成魔方阵。任何算法都有不同的实现方法，通过采用不同实现方法来重新实现算法，这要比单纯学习算法的效果好得多。
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int m;//阶数
int x , y ;//横坐标，纵坐标
int fz;//辅助数
int number;//当前要进数组的数字
cout<<"please input m"<<endl;
while(cin>>m)
{
if(m<=0)//输入判断
{
cout<<"input error,please input positive odd"<<endl;
continue;
}
if(m%2==0)//输入判断
{
cout<<"input error,please input positive odd"<<endl;
continue;
}
fz = m;
int mofang[m][m];//构建二维数组
memset(mofang,0,sizeof(mofang));//清零
mofang[0][m/2] = 1;//把1放到第一行中间
x = 0 ;
y = m / 2;
number = 2;
while(number <= m * m)//循环条件是进数组的数小于阶数的平方
{
if(x-1<0)//上方出界
{
if(y-1>=0)//左边没出界，把数插入到左边一行最下面
{
for(int i = 0 ; i < m ; i ++)
{
if(mofang[fz-1][y-1]==0)
break;
else fz--;
}
mofang[fz-1][y-1]= number;
number ++;
x = fz-1;
y = y -1;
fz = m;
}
else//左边出界，把数插入到当前位置的下一行
{
mofang[x+1][y] = number;
number ++;
x = x + 1;
fz = m;
}
}
else if(y-1 < 0)//左边出界
{
for(int i = 0 ; i < m ; i++)
{
if(mofang[x-1][fz-1]==0)
break;
else fz--;
}
mofang[x-1][fz-1]= number;
number ++;
x = x - 1;
y = fz - 1;
fz = m ;
}
else if(mofang[x-1][y-1]!=0)//左上角元素不为0
{
mofang[x+1][y] = number ;
number ++;
x = x+1;
}
else//插入左上角
{
mofang[x-1][y-1] = number ;
x = x -1 ;
y = y -1;
number ++;
}
}
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < m ; j++)
{
cout<<mofang[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
}