谭浩强的c语言第七章数组中有一道题:

如题所述

对平面魔方的构造,分为三种情况:N 为奇数、N 为4的倍数、N 为其他偶数(4n+2的形式)。
1. N 为奇数时,构造最为简单。首先,将数字1放在第一行中间一列。然后,从数字2开始,直到n×n止,按照以下规则存放:按45°方向行走,如向右上;每一个数存放的行比前一个数的行数减1,列数加1。如果行列范围超出矩阵范围,则回绕。例如,1在第1行,则2应放在最下一行,列数同样加1。如果按上述规则确定的位置上已有数,或上一个数是第1行第n列时,则将下一个数放在上一个数的下面。
2. N 为4的倍数时,采用对称元素交换法。首先,将数字1到n×n按从上至下,从左至右的顺序填入矩阵。然后,将方阵的所有4×4子方阵中的两对角线上位置的数关于方阵中心作对称交换,即a(i,j)与a(n+1-i,n+1-j)交换。所有其他位置上的数不进行交换。
3. N 为其他偶数时,即N 为非4倍数的偶数(4n+2的形式)时:首先,将大方阵分解为4个奇数(2m+1阶)子方阵。然后,按上述奇数阶魔方给分解的4个子方阵对应赋值。上左子阵最小(i),下右子阵次小(i+v),下左子阵最大(i+3v),上右子阵次大(i+2v),其中v=n×n/4。四个子矩阵由小到大排列方式为 ① ③ ④ ②。接着,作相应的元素交换:a(i,j)与a(i+u,j)在同一列做对应交换(jn-t+2),a(t-1,0)与a(t+u-1,0);a(t-1,t-1)与a(t+u-1,t-1)两对元素交换,其中u=n/2,t=(n+2)/4。上述交换使每行每列与两对角线上元素之和相等。
以上是关于平面魔方构造的详细步骤。我的程序算法可以对除2以外的任意阶数的方阵进行输出,结果保存在运行程序的目录下的Magic.txt文件中。当然,具体的程序中存在内存空间以及变量范围的约束,我试过了,100以内的是可以的。偶数阶的算法都是建立在奇数阶的基础之上,设方阵的阶数为n,则魔方阵常数(即每列每行以及对角线元素之和)为n×(n×n+1)/2。请对照程序代码看,否则可能看不懂,可以一边看一边用笔对小阶的进行演算。
奇数阶的算法最为简单,n=2×m+1,m为自然数。1)将数字1填在(0,(n+1)/2);要注意C中是从下标0开始。2)从左上往右下依次填。3)由2),列的下标出界(超过n-1)时,行加1,以n为模的余数为应填的列数;4)由2),行的下标出界(超过n-1)时,列加1,以n为模的余数为应填的行数;5)由2),行列都未出界,但已填上其他数,应在当前位置左横移一个位置进行填数。
偶数阶的算法分两种情况,一种是n%4==2,一种是n%4==0。前一种:n=2×(2×m+1),m为自然数。1)将n阶方阵分为四个小魔方阵ABCD如下排列:B C D A。因为n×n=4×(2×m+1)×(2×m+1),记u=n/2=2×m+1,分为1~u×u,u×u+1~2×u×u,2×u×u+1~3×u×u,3×u×u+1~4×u×u,即在调用子函数的时候分别如下面传递参数:A(0),B(u×u),C(2×u×u),D(3×u×u)。分别在ABCD中按照前面的填法把奇数阶填好(注意加上所传参数作为基数,每一个元素都要加上这个值),最后做如下交换:(1)B中第0~(m-1)-1行中元素与C中相对应元素交换;(2)D中第(n-1)-m+1~(n-1)共m行的每行中的元素与A中相对应元素交换;(3)交换D:(u+m,m)与A中对应元素(矩阵中心值);(4)交换D:(n-1,m)与A中对应元素(实际为矩阵最大值n×n)。所谓对应位置,指相对于小魔方阵的左顶角的相对的行列位置。上面的这些你可以用数学进行证明,利用魔则轮方阵常数(注意n阶的和u阶的关系)。后一种:n=4×m,m为自然数。因为行列都是4的倍数,因而可以将整个矩阵分为每4×4的小矩阵。先判断一个数是否在划为4×4小矩阵的对角线上,如果在,则填该位置的数为n×n-i+1(i为该元素的相对位置,从1开始,比如n阶的第s行第t个元素则其i=s×n+t)。如果不在,则填上i。
温馨提示:答案为网友推荐,仅供参考
相似回答
大家正在搜