大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献！
49.Algorithm Gossip: 奇数魔方阵
说明
将1到n(为奇数)的数字排列在nxn的方阵上，且各行、各列与各对角线的和必须相同，如下所示：
解法
填魔术方阵的方法以奇数最为简单，第一个数字放在第一行第一列的正中央，然后向右(左)上填，如果右(左)上已有数字，则向下填，如下图所示：
一般程序语言的阵列索引多由0开始，为了计算方便，我们利用索引1到n的部份，而在计算是向右(左)上或向下时，我们可以将索引值除以n值，如果得到余数为1就向下，否则就往右(左)上，原理很简单，看看是不是已经在同一列上绕一圈就对了。
#include <stdio.h> #include <stdlib.h> #define N 5 int main(void) { int i, j, key; int square[N+1][N+1] = {0}; i = 0; j = (N+1) / 2; for(key = 1; key <= N*N; key++) { if((key % N) == 1) i++; else { i--; j++; } if(i == 0) i = N; if(j > N) j = 1; square[i][j] = key; } for(i = 1; i <= N; i++) { for(j = 1; j <= N; j++) printf("%2d ", square[i][j]); } return 0; }
50.Algorithm Gossip: 4N 魔方阵
说明
与 奇数魔术方阵 相同，在于求各行、各列与各对角线的和相等，而这次方阵的维度是4的倍数。
解法
先来看看4X4方阵的解法：
简单的说，就是一个从左上由1依序开始填，但遇对角线不填，另一个由左上由16开始填，但只填在对角线，再将两个合起来就是解答了；如果N大于2，则以 4X4为单位画对角线：
至于对角线的位置该如何判断，有两个公式，有兴趣的可以画图印证看看，如下所示：
左上至右下：j % 4 == i % 4
右上至左下：(j % 4 + i % 4) == 1
#include <stdio.h> #include <stdlib.h> #define N 8 int main(void) { int i, j; int square[N+1][N+1] = {0}; for(j = 1; j <= N; j++) { for(i = 1; i <= N; i++){ if(j % 4 == i % 4 || (j % 4 + i % 4) == 1) square[i][j] = (N+1-i) * N -j + 1; else square[i][j] = (i - 1) * N + j; } } for(i = 1; i <= N; i++) { for(j = 1; j <= N; j++) printf("%2d ", square[i][j]); printf("\n"); } return 0; }
51.Algorithm Gossip: 2(2N+1) 魔方阵
说明
方阵的维度整体来看是偶数，但是其实是一个奇数乘以一个偶数，例如6X6，其中6=2X3，我们也称这种方阵与单偶数方阵。
解法
如果您会解奇数魔术方阵，要解这种方阵也就不难理解，首先我们令n=2(2m+1)，并将整个方阵看作是数个奇数方阵的组合，如下所示：
首先依序将A、B、C、D四个位置，依奇数方阵的规则填入数字，填完之后，方阵中各行的和就相同了，但列与对角线则否，此时必须在A-D与C- B之间，作一些对应的调换，规则如下：
将A中每一列(中间列除外)的头m个元素，与D中对应位置的元素调换。
将A的中央列、中央那一格向左取m格，并与D中对应位置对调
将C中每一列的倒数m-1个元素，与B中对应的元素对调
举个实例来说，如何填6X6方阵，我们首先将之分解为奇数方阵，并填入数字，如下所示：
接下来进行互换的动作，互换的元素以不同颜色标示，如下：
由于m-1的数为0，所以在这个例子中，C-B部份并不用进行对调。
#include <stdio.h> #include <stdlib.h> #define N 6 #define SWAP(x,y) {int t; t = x; x = y; y = t;} void magic_o(int [][N], int); void exchange(int [][N], int); int main(void) { int square[N][N] = {0}; int i, j; magic_o(square, N/2); exchange(square, N); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) printf("%2d ", square[i][j]); printf("\n"); } return 0; } void magic_o(int square[][N], int n) { int count, row, column; row = 0; column = n / 2; for(count = 1; count <= n*n; count++) { square[row][column] = count; // 填A square[row+n][column+n] = count + n*n; // 填B square[row][column+n] = count + 2*n*n; // 填C square[row+n][column] = count + 3*n*n; // 填D if(count % n == 0) row++; else { row = (row == 0) ? n - 1 : row - 1 ; column = (column == n-1) ? 0 : column + 1; } } } void exchange(int x[][N], int n) { int i, j; int m = n / 4; int m1 = m - 1; for(i = 0; i < n/2; i++) { if(i != m) { for(j = 0; j < m; j++) // 处理规则 1 SWAP(x[i][j], x[n/2+i][j]); for(j = 0; j < m1; j++) // 处理规则 2 SWAP(x[i][n-1-j], x[n/2+i][n-1-j]); } else { // 处理规则 3 for(j = 1; j <= m; j++) SWAP(x[m][j], x[n/2+m][j]); for(j = 0; j < m1; j++) SWAP(x[m][n-1-j], x[n/2+m][n-1-j]); } } }
评论