首页 > 代码库 > 魔方阵
魔方阵
①问题描述
魔方阵是一个古老的智力问题,它要求在一个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
④思考
-
可以考虑使用其他方法生成魔方阵。任何算法都有不同的实现方法,通过采用不同实现方法来重新实现算法,这要比单纯学习算法的效果好得多。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #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; } } |