任意阶幻方算法c++.doc

/任意阶幻方算法c+/ Magic.cpp : Defines the entry point for the console application. /*- 功能：幻方构造 说明：幻方，亦称纵横图。将自然数1，2，3，n*n排列成一个n*n方阵， 使得每行、每列以及两对角线上的各个数之和都相等，等于n/2*(n*n+1)，这样的方阵称为幻方。 8 1 6 3 5 7 4 9 2 数学上已经证明，对于n2，n阶幻方都存在。 目前填写幻方的方法，是把幻方分成了三类，每类又有各种各样的填写方法 -*/ #include stdafx.h #include #include int get_n(); /读入阶数 int Odd_Construct(int,int*,int =1); /构造奇数阶 int Bi_Even_Construct(int,int*); /构造双偶阶 int Bi_Even_Construct_init(int ,int * ); /双偶阶初始化 int Bi_Even_Construct_Switch(int ,int * ); /双偶阶对调对角线 int init_quadrant_ABCD(int ,int *); /初始化各象限元素 int Swap_A_C(int n,int* ,int* ); /交换A，C象限 int Swap_B_D(int n,int* ,int* ) ; /交换B，D象限 void swap_no(int*,int* ); /交换一个元素 int copy_quadrants_to_magic(int n,int* magic, int* sub_magic_A,int* sub_magic_B,int* sub_magic_C,int* sub_magic_D); /把ABCD各象限合并到magic int Single_Even_Construct(int,int*); /构造单偶阶 int init_magic(int,int*); /初始化幻方 int print_magic(int,int*); /打印幻方 /*- 主程序 -*/ int main(int argc, char* argv) int n; n=get_n(); /读入阶数n int s=n*(n*n+1)/2; /计算幻和 printf(nS= %d,s); int* magic=new intn*n ; /magic存n阶幻方，是整型指针，指向数组头 init_magic(n,magic); /将所有值初始化为0 if( n%2 = 1 ) Odd_Construct(n,magic ); /构造奇数阶幻方 else if( n%4 = 0 ) Bi_Even_Construct(n,magic ); /构造双偶阶4k else Single_Even_Construct(n,magic ); /单偶阶4k+2 print_magic(n,magic ); /打印幻方 if(magic!=NULL) /释放幻方内存 delete magic; magic = NULL; return 0; /*- -读入阶数n,这里限制 n是为了n在一屏 显示下，其实可以增大之 -*/ int get_n() int n; do printf(请输入幻方阶数n n; if(n 100) printf(nN 必须在 3,100 ); continue; else break; while(n100); return n; /*- 初始化幻方，所有元素置0;初始化是必须的，以便用0判断填充否 -*/ int init_magic(int n,int *magic) for(int i=0; i n; i+ ) for(int j=0; j n; j+ ) *(magic+)=0; /幻方每个值置0 return 0; /*- 打印幻方 -*/ int print_magic(int n,int *magic) for(int i=0; i n; i+ ) printf(n); for(int j=0; j n; j+ ) printf(%3d ,*(magic +) ); /打印幻方值 printf(n); return 0; /*- 1、奇数阶幻方 n为奇数 (n=3，5，7，9，11) (n=2*k+1，k=1，2，3，4，5) 奇数阶幻方最经典的填法是罗伯特法(也有人称之为楼梯方)。填写方法是这样： 把1(或最小的数)放在第一行正中； 按以下规律排列剩下的n*n-1个数： (1)、每一个数放在前一个数的右上一格； (2)、如果这个数所要放的格已经超出了顶行那么就把它放在底行，仍然要放在右一列； (3)、如果这个数所要放的格已经超出了最右列那么就把它放在最左列，仍然要放在上一行； (4)、如果这个数所要放的格已经超出了顶行且超出了最右列，那么就把它放在前一个数的下一行同一列的格内； (5)、如果这个数所要放的格已经有数填入，处理方法同(4)。 这种写法总是先向“右上”的方向，象是在爬楼梯。 -*/ int Odd_Construct(int n,int *magic,int start_no ) /把1(或最小的数)放在第一行正中,比如n=5,则放在(0,2) int columns=(n-1)/2; /columns:0 based int lines=0; /lines:0 based int count=0; /用于计数是否填完 *(magic+(n*lines+columns)=start_no; /把1(或最小的数)放在第一行正中 count+; int i=lines,j=columns; /指针初始值,i:行指针，j:列指针 int max_lines=n-1,max_columns=n-1; /行最大，列最大;0 based int no=start_no+1; /被填的数 while(count n*n) if( i=0 & j=max_columns & (*(magic + ( n*i + j) ) != 0 ) ) /到达最右上角，直接填自己下边 i+; *(magic + ( n*i + j) ) = no; count+; no+; continue; if( i =0 ) /到达顶行，则从最低下行开始 i=max_lines; else i-; if( j = max_columns ) /到达最右列，则从最左开始 j=0; else j+; if( (*(magic + ( n*i + j) ) != 0 ) ) /应该的位置已经填过数,或到达右上角,则放在当前数的下边 j-; i+;i+; *(magic+( n*i + j) ) = no; count+; no+; return 0; /*- 2、双偶阶幻方 n为偶数，且能被4整除 (n=4，8，12，16，20) (n=4k，k=1，2，3，4，5) 先说明一个定义： 互补：如果两个数字的和，等于幻方最大数和最小数的和，即 n*n+1，称为互补。 先看看4阶幻方的填法：将数字从左到右、从上到下按顺序填写： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 这个方阵的对角线，已经用蓝色标出。将对角线上的数字，换成与它互补的数字。 这里，n*n+1 = 4*4+1 = 17； 把1换成17-1 = 16；把6换成17-6 = 11；把11换成17-11 = 6换完后就是一个四阶幻方。 16 2 3 13 5 11 10 8 9 7 6 12 4 14 15 1 对于n=4k阶幻方，我们先把数字按顺序填写。写好后，按4*4把它划分成k*k个方阵。因为n是4的倍数，一定能用4*4的小方阵分割。然后把每个小方阵的对角线，象制作4阶幻方的方法一样，对角线上的数字换成互补的数字，就构成幻方。 下面是8阶幻方的作法： (1) 先把数字按顺序填。然后，按4*4把它分割成2*2个小方阵 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) (2) 每个小方阵对角线上的数字，换成和它互补的数。 64 2 3 61 60 6 7 57 9 55 54 12 13 51 50 16 17 47 46 20 21 43 42 24 40 26 27 37 36 30 31 33 32 34 35 29 28 38 39 25 41 23 22 44 45 19 18 48 49 15 14 52 53 11 10 56 8 58 59 5 4 62 63 1 -*/ int Bi_Even_Construct(int n,int *magic ) Bi_Even_Construct_init( n, magic); /(1) 先把数字按顺序填 /(2) 每个小方阵对角线上的数字，换成和它互补的数 Bi_Even_Construct_Switch( n, magic); return 0; /*- (1) 初始化，先把数字按顺序填 -*/ int Bi_Even_Construct_init(int n,int *magic ) int no=1; for(int i=0;i n;i+) /(1) 先把数字按顺序填 for(int j=0;j n;j+) *(magic+)=no+; return 0; /*- (2) 每个小方阵对角线上的数字，换成和它互补的数 a的互补是n*n+1-a. 其中n是阶数 -*/ int Bi_Even_Construct_Switch(int n,int *magic ) /哪些行需要处理：0,3,4,7,.;列：0，3，4，7 for(int i=0;i n;i+) for(int j=0;j n;j+) if( (i%4=0 & j%4=0)| (i%4=0 & j%4=3)| (i%4=1 & j%4=1)| (i%4=1 & j%4=2)| (i%4=2 & j%4=1)| (i%4=2 & j%4=2)| (i%4=3 & j%4=0)| (i%4=3 & j%4=3) ) *(magic)=n*n+1-*(magic); / magic+; /指针下移 return 0; /*-3、单偶阶幻方 n为偶数，且不能被4整除 (n=6，10，14，18，22) (n=4k+2，k=1，2，3，4，5) 这是三种里面最复杂的幻方。 以n=10为例。这时，k=2 (1) 把方阵分为A，B，C，D四个象限，这样每一个象限肯定是奇数阶。用楼梯法，依次在A象限，D象限，B象限，C象限按奇数阶幻方的填法填数。 | A | B | - | C | D | 17 24 1 8 15 67 74 51 58 65 23 5 7 14 16 73 55 57 64 66 4 6 13 20 22 54 56 63 70 72 10 12 19 21 3 60 62 69 71 53 11 18 25 2 9 61 68 75 52 59 92 99 76 83 90 42 49 26 33 40 98 80 82 89 91 48 30 32 39 41 79 81 88 95 97 29 31 38 45 47 85 87 94 96 78 35 37 44 46 28 86 93 100 77 84 36 43 50 27 34 (2) 在A象限的中间行、中间格开始，按自左向右的方向，标出k格。A象限的其它行则标出最左边的k格。 17 24 1 8 15 67 74 51 58 65 23 5 7 14 16 73 55 57 64 66 4 6 13 20 22 54 56 63 70 72 10 12 19 21 3 60 62 69 71 53 11 18 25 2 9 61 68 75 52 59 92 99 76 83 90 42 49 26 33 40 98 80 82 89 91 48 30 32 39 41 79 81 88 95 97 29 31 38 45 47 85 87 94 96 78 35 37 44 46 28 86 93 100 77 84 36 43 50 27 34 (3) 将这些格，和C象限相对位置上的数，互换位置。 92 99 1 8 15 67 74 51 58 65 98 80 7 14 16 73 55 57 64 66 4 6 88 95 22 54 56 63 70 72 85 87 19 21 3 60 62 69 71 53 86 93 25 2 9 61 68 75 52 59 17 24 76 83 90 42 49 26 33 40 23 5 82 89 91 48 30 32 39 41 79 81 13 20 97 29 31 38 45 47 10 12 94 96 78 35 37 44 46 28 11 18 100 77 84 36 43 50 27 34 (4) 在B象限任一行的中间格，自右向左，标出k-1列。(注：6阶幻方由于k-1=0所以不用再作B、D象限的数据交换) 92 99 1 8 15 67 74 51 58 65 98 80 7 14 16 73 55 57 64 66 4 6 88 95 22 54 56 63 70 72 85 87 19 21 3 60 62 69 71 53 86 93 25 2 9 61 68 75 52 59 17 24 76 83 90 42 49 26 33 40 23 5 82 89 91 48 30 32 39 41 79 81 13 20 97 29 31 38 45 47 10 12 94 96 78 35 37 44 46 28 11 18 100 77 84 36 43 50 27 34 (5) 将B象限标出的这些数，和D象限相对位置上的数进行交换，即可完成。 92 99 1 8 15 67 74 26 58 65 98 80 7 14 16 73 55 32 64 66 4 6 88 95 22 54 56 38 70 72 85 87 19 21 3 60 62 44 71 53 86 93 25 2 9 61 68 50 52 59 17 24 76 83 90 42 49 51 33 40 23 5 82 89 91 48 30 57 39 41 79 81 13 20 97 29 31 63 45 47 10 12 94 96 78 35 37 69 46 28 11 18 100 77 84 36 43 75 27 34 -*/ int Single_Even_Construct(int n,int *magic) init_quadrant_ABCD( n, magic); return 0; /*- A，B,C,D各象限的子幻方阶数分别为(4n+2)/2=2n+1 对每个子幻方运用奇数阶的方法填充。 -*/ int init_quadrant_ABCD(int n,int *magic) int sub_n = n/2; /分成4个象限后，每象限的阶数sub_n int* sub_magic_A=new int(sub_n)*(sub_n); /A象限数组 int* sub_magic_B=new int(sub_n)*(sub_n); /B int* sub_magic_C=new int(sub_n)*(sub_n); /C int* sub_magic_D=new int(sub_n)*(sub_n); /D /初始化每个象限的子幻方 init_magic(sub_n,sub_magic_A); init_magic(sub_n,sub_magic_B); init_magic(sub_n,sub_magic_C); init_magic(sub_n,sub_magic_D); int start_no = 1; Odd_Construct( sub_n, sub_magic_A, start_no ); /构造A象限 start_no += sub_n * sub_n ; Odd_Construct( sub_n, sub_magic_D, start_no ); /D start_no += sub_n * sub_n; Odd_Construct( sub_n, sub_magic_B, start_no ); /B start_no += sub_n * sub_n; Odd_Construct( sub_n, sub_magic_C, start_no ); /C Swap_A_C(n,sub_magic_A,sub_magic_C); /处理A,D象限 Swap_B_D( n, sub_magic_B, sub_magic_D); /处理B，D象限 copy_quadrants_to_magic(n,magic,sub_magic_A,sub_magic_B,sub_magic_C,sub_magic_D); /将子幻方拷贝到最后的magic /释放子幻方内存 if( sub_magic_A!=NULL) delete sub_magic_A; sub_magic_A=NULL; if(sub_magic_B !=NULL) delete sub_magic_B; sub_magic_B=NULL; if(sub_magic_C !=NULL) delete sub_magic_C; sub_magic_C=NULL; if(sub_magic_D !=NULL) delete sub_magic_D; sub_magic_D=NULL; return 0; /*- 将子幻方ABCD拷贝到最后的magic -*/ int copy_quadrants_to_magic(int n,int* magic,int* sub_magic_A,int* sub_magic_B,int* sub_magic_C,int* sub_magic_D) int sub_n=n/2; int Ai=0 ; /A象限的下标 int Bi=0 ; /B象限的下标 int Ci=0 ; /C象限的下标 int Di=0 ; /D象限的下标 for(int i=0;i n;i+) /i,j是magic的循环变量 for(int j=0;j n;j+) if (i sub_n) if( j sub_n ) /记住A象限的数据 *(magic + n*i + j) = *(sub_magic_A + Ai ); Ai+; else /记住B象限的数据 *(magic + n*i + j) = *(sub_magic_B + Bi ); Bi+; else if( j sub_n ) /记住C象限的数据 *(magic + n*i + j) = *(sub_magic_C + Ci ); Ci+; else /记住D象限的数据 *(magic + n*i + j) = *(sub_magic_D + Di ); Di+; return 0; /*- (2) 在A象限的中间行、中