前言
在上一篇博客(click here)中,我们完成了实验要求的部分,即实现奇数阶幻方的构造。接下来我们将要着手实现剩下的4M阶幻方和4M+2阶幻方的构造。
构造方法
4M阶幻方
4M阶幻方的构造方法较奇数阶幻方的构造更为复杂,在此我们采用对角线法,其策略如下:
- 将幻方划分为M2 个4X4的小幻方。
- 在每个小幻方中,找到并标记两条对角线所经过的方格。
- 第一次填充时跳过标记的方格,其余方格均填入其按顺序摆放时对应的数字。
- 第二次填充时在标记的方格中填入其关于幻方中心对称的方格处按顺序摆放时对应的数字。
我们可以通过一个例子来更深的理解这个构造方法。对八阶幻方,先将其划分成为4个4阶小幻方,接着分别画出4个小幻方的两条对角线,被对角线切开的方格记为被标记。第一次填充时,依次将1到82填入方格,其中理解为被标记的方格不显示数字。第二次填充时,将所有被标记的方格中的数字与其关于整个幻方的对称方格中的数字对调,接着显示数字。按照上面的步骤便可将所有数填入,八阶幻方构造完毕。其全过程示意图如下:
同样,需要注意的是幻方并不是唯一的,这只是用该方法构造的幻方,如果采用其他构造法得到不同的幻方是很正常的。
知道了构造思路,便很容易用java语言实现这一构造方法,代码如下:
public static void magic_square_4m_generate(int[][] squares)
{for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {//坐标(i,j)是否处在对角线上int p = i % 4;int q = j % 4;if (p == q || p + q == 3) {//对角线上的按顺序摆放的数与其关于幻方中心的数对调squares[i][j] = (n - 1 - i) * n + (n - 1 - j) + 1;} else {//对角线外的数即为按顺序摆放的数squares[i][j] = i * n + j + 1;}}}
}
4M+2阶幻方
4M+2阶幻方的构造方法是三种幻方中最为复杂的,基于我们已经实现的奇数阶幻方构造方法,我们可以采用Strachey法,其策略如下:
-
将幻方等分成四个2M+1阶幻方A、B、C、D,并且其排列为:
A C
D B
-
分别将A用1至(2M+1)2填写成2M+1阶幻方;B用(2M+1)2+1至2(2M+1)2填写成2M+1阶幻方;C用2(2M+1)2+1至3(2M+1)2填写成2M+1阶幻方;D用3(2M+1)2+1至4(2M+1)2填写成2M+1阶幻方。
-
第一次置换,在A区域取最中间的方格与D区域对应方格对调,再将A区域中间那一行从左向右前M-1个方格与D区域对应方格对调,最后将A区域其他2M行从左向由前M个方格与D区域对应方格对调。
-
第二次置换,在C区域中任取 m-1 列与B区域对应小格对调。
我们可以通过一个例子来更深的理解这个构造方法。对六阶幻方,先将其划分为4个三阶幻方,分别用A、C、D、B标注(在图上用不同颜色表示)。在A幻方中,用1到32将其填充为三阶幻方;在C幻方中,用2X32+1到3X32将其填充为三阶幻方;在D幻方中,用3X32+1到4X32将其填充为三阶幻方;在A幻方中,用32+1到2X32将其填充为三阶幻方。第一次置换,将A区域最中间的方格中的数字5与D区域对应方格中的数字32对调,再将A区域中间那一行从左向右前1-1(即0)个方格与D区域对应方格对调(由于计算得0,故无交换方格),最后将A区域其他两行从左向由前1个方格与D区域对应方格对调(即将A区域中的8、4分别与D区域中与之对应的35、31对调)。第二次置换,在C区域中任取 1-1 (即0)列与B区域对应小格对调(由于计算得0,故无交换方格)。按照上面的步骤便可将所有数填入,六阶幻方构造完毕。其全过程示意图如下:
同样,需要注意的是幻方并不是唯一的,这只是用该方法构造的幻方,如果采用其他构造法得到不同的幻方是很正常的。
知道了构造思路,便很容易用java语言实现这一构造方法,代码如下:
public static void magic_square_4m+2_generate(int[][] squares)
{int row, column, m = ( n - 2 ) / 4, temp;//将幻方等分成四个部分int[][] A = new int[2 * m + 1][2 * m + 1];int[][] B = new int[2 * m + 1][2 * m + 1];int[][] C = new int[2 * m + 1][2 * m + 1];int[][] D = new int[2 * m + 1][2 * m + 1];//构造A, B, C, D幻方magic_square_odd_generate(A);for(row = 0; row < 2 * m + 1; row++){for(column = 0; column < 2 * m + 1; column++){B[row][column] = A[row][column] + (2 * m + 1) * (2 * m + 1);C[row][column] = B[row][column] + (2 * m + 1) * (2 * m + 1);D[row][column] = C[row][column] + (2 * m + 1) * (2 * m + 1);}}//完成A, D的置换for(row = 0; row < 2 * m + 1; row++){for(column = 0; column < m; column++){temp = A[row][column];A[row][column] = D[row][column];D[row][column] = temp;}}temp = A[m][m]; A[m][m] = D[m][m]; D[m][m] = temp;temp = A[m][m - 1]; A[m][m - 1] = D[m][m - 1]; D[m][m - 1] = temp;//完成C, B的对调for(row = 0; row < 2 * m + 1; row++){for(column = 0; column < m - 1; column++){temp = B[row][column];B[row][column] = C[row][column];C[row][column] = temp;}}//将A, B, C, D对应区域赋值到squares中for(row = 0; row < n; row++){for(column = 0; column < n; column++){if(row < ( 2 * m + 1 ) && column < ( 2 * m + 1 ))squares[row][column] = A[row][column];else if(row < ( 2 * m + 1 ) && column >= ( 2 * m + 1 ))squares[row][column] = C[row][column - n];else if(row >= ( 2 * m + 1 ) && column < ( 2 * m + 1 ))squares[row][column] = D[row - ( 2 * m + 1 )][column];else if(row >= ( 2 * m + 1 ) && column >= ( 2 * m + 1 ))squares[row][column] = B[row - ( 2 * m + 1 )][column - ( 2 * m + 1 )];}}
}
结语
综上,我们已经全部实现了三种幻方的构造,现在我们可以说你给我任意一个数字(2阶幻方不存在),我都可以给出它的一种幻方的构造,而我的博客也到此为止。但是,事实上幻方的构建方法远远不止一种,我给出的仅有一种方法,还可以尝试新的其他的构造方法。同时,我的博客的构造方法基于网络中给出的已有的算法,可以肯定它是正确的,但我对这些方法的证明并没有做过多深挖。由此,我给出的想法只是幻方浅陋的部分,感兴趣的可以就其他构造方法及其理论证明这两点进行更深层次的探讨与研究。