任意阶幻方算法c++
// Magic.cpp : Defines the entry point for the console application.
//
/**-------------------------------------
陈海，GS0721526
功能：幻方构造
说明：幻方，亦称纵横图。台湾称为魔术方阵。将自然数1，2，3，……n*n排列成一个n*n方阵，
使得每行、每列以及两对角线上的各个数之和都相等，等于n/2*(n*n+1)，这样的方阵称为幻方。
8 1 6
3 5 7
4 9 2
数学上已经证明，对于n>2，n阶幻方都存在。
目前填写幻方的方法，是把幻方分成了三类，每类又有各种各样的填写方法
本算法来自：http://blog.csdn.net/northwolves/archive/2007/09/23/1796696.aspx
---------------------------------*/
#include "stdafx.h"
#include<iostream.h>
int get_n(); //读入阶数
int Odd_Construct(int,int*,int =1); //构造奇数阶
int Bi_Even_Construct(int,int*); //构造双偶阶
intBi_Even_Construct_init(int ,int * ); //双偶阶初始化
intBi_Even_Construct_Switch(int ,int * ); //双偶阶对调对角线
intinit_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 int[n*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<=100：\n");
cin>>n;
if(n<3 || n>100){
printf("\nN 必须在 [3,100]" );
continue;
}else
break;
}while(n>100);
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;
}
[解决办法]
这么好的帖子,支持.收藏
