注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

AP计算机众里寻他千百度,名师成就满分路

AP计算机

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

魔方阵  

2016-11-29 07:58:36|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

49.Algorithm Gossip: 奇数魔方阵

说明

将1到n(为奇数)的数字排列在nxn的方阵上,且各行、各列与各对角线的和必须相同,如下所示:

clip_image001

解法

填魔术方阵的方法以奇数最为简单,第一个数字放在第一行第一列的正中央,然后向右(左)上填,如果右(左)上已有数字,则向下填,如下图所示:

clip_image002

一般程序语言的阵列索引多由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方阵的解法:

clip_image003

简单的说,就是一个从左上由1依序开始填,但遇对角线不填,另一个由左上由16开始填,但只填在对角线,再将两个合起来就是解答了;如果N大于2,则以 4X4为单位画对角线:

clip_image004

至于对角线的位置该如何判断,有两个公式,有兴趣的可以画图印证看看,如下所示:

左上至右下: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),并将整个方阵看作是数个奇数方阵的组合,如下所示:

clip_image005

首先依序将A、B、C、D四个位置,依奇数方阵的规则填入数字,填完之后,方阵中各行的和就相同了,但列与对角线则否,此时必须在A-D与C- B之间,作一些对应的调换,规则如下:

将A中每一列(中间列除外)的头m个元素,与D中对应位置的元素调换。

将A的中央列、中央那一格向左取m格,并与D中对应位置对调

将C中每一列的倒数m-1个元素,与B中对应的元素对调

举个实例来说,如何填6X6方阵,我们首先将之分解为奇数方阵,并填入数字,如下所示:

clip_image006

接下来进行互换的动作,互换的元素以不同颜色标示,如下:

clip_image007

由于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]); 
        } 
    } 
}
复制代码
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018