Algorithm 版 (精华区)
发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: [合集]怎样求这样一个矩阵？
发信站: 哈工大紫丁香 (2002年09月15日21:40:41 星期天), 站内信件
────────────────────────────────────────
hewind (Romen) 于 2002年09月02日20:00:28 星期一 说道:
哪位大虾能帮小弟解决如下要求的算法，急！！！！！！！
任意一个奇数N
能产生这样一个矩阵：其每行，每列，主副对角线上的和都相。
这个矩阵是如何求出来的？
────────────────────────────────────────
IntoGTS (岚叶知秋№→无名的旅人) 于 2002年09月02日20:05:41 星期一 说道:
看 1387
────────────────────────────────────────
zjliu (fly) 于 2002年09月02日20:16:56 星期一 说道:
matlab中用magic(N)就能搞定
────────────────────────────────────────
sino (茶水) 于 2002年09月02日21:39:09 星期一 说道:
matlab真cool 阿！
────────────────────────────────────────
SoonFaye (宠辱偕忘) 于 2002年09月03日08:29:04 星期二 说道:
有固定算法，分奇数(2n+1)、单偶数(4n+2)、双偶数(4n)三类
每种情况按照一定规则填到里面就成了，如果需要给我发信，明天我给你详细算法。
────────────────────────────────────────
wshefeng (wshefneg) 于 2002年09月03日17:27:41 星期二 说道:
如果可以的话就话就麻烦你了
────────────────────────────────────────
SoonFaye (宠辱偕忘) 于 2002年09月04日08:16:47 星期三 说道:
int M=15;//方阵阶数M
int flag; //方阵类型标志
int A[50][50];//预定义数组
for(int i=0;i<50;i++)
for(int ii=0;ii<50;ii++)
A[i][ii]=0;//初始化这个数组
if(M%2)
flag=1; //M是奇数
else
{
if(M%4)
flag=2; //M是单偶数
else
flag=3; //M是双偶数
}
if(M==2)
flag=10; //2阶方阵没有解
//此处以下处理M是奇数的情况
if(flag==1)
{
int x=(M-1)/2, y=0;
for(int i=1;i<=M*M;i++)
{
A[x][y]=i;
int a=x,b=y;
a++; b--;
if(b<0)b=M-1;
if(a==M)a=0;
if(A[a][b])
{
y++;
if(y==M)
y=0;
}
else
{
x=a; y=b;
}
}
}
//此处以下处理M是单偶数的情况
if(flag==2)
{
int MM=M/2;
int x=(MM-1)/2, y=0;
for(int i=1;i<=MM*MM;i++)
{
A[x][y]=i;
A[x+MM][y+MM]=i+MM*MM;
A[x+MM][y]=i+2*MM*MM;
A[x][y+MM]=i+3*MM*MM;
int a=x,b=y;
a++; b--;
if(b<0)b=MM-1;
if(a==MM)a=0;
if(A[a][b])
{
y++;
if(y==MM)
y=0;
}
else
{
x=a; y=b;
}
}
int r=(M-2)/4;
for(i=0;i<MM;i++)
{
for(int ii=0;ii<r;ii++)
{
int a=ii, b=i;
if(b==(MM-1)/2)
a++;
int SWAP=A[a][b];
A[a][b]=A[a][b+MM];
A[a][b+MM]=SWAP;
}
for(ii=M-1;ii>M-r;ii--)
{
int Sw=A[ii][i];
A[ii][i]=A[ii][i+MM];
A[ii][i+MM]=Sw;
}
}
}
//此处以下处理M是双偶数的情况
if(flag==3)
{
for(int i=0;i<M;i++)
for(int ii=0;ii<M;ii++)
A[i][ii]=i+1+ii*M;
for(i=0;i<M/4;i++)
for(int ii=0;ii<M/4;ii++)
{
int x=i*4, y=ii*4;
for(int p=0;p<4;p++)
{
int Mswaps;
int dqX=x+p, dqY=y+p;
if(dqX<M/2)
{
Mswaps=A[dqX][dqY];
A[dqX][dqY]=A[M-1-dqX][M-1-dqY];
A[M-1-dqX][M-1-dqY]=Mswaps;
}
dqX=x+p, dqY=y+3-p;
if(dqX<M/2)
{
Mswaps=A[dqX][dqY];
A[dqX][dqY]=A[M-1-dqX][M-1-dqY];
A[M-1-dqX][M-1-dqY]=Mswaps;
}
}
}
}
//以上代码完成操作
//以下输出结果
for(int j=0;j<M;j++)
for(int jj=0;jj<M;jj++)
{
char ss[20];
wsprintf(ss,"%d",A[j][jj]);
pDC->Rectangle(100+j*30,100+jj*30,131+j*30,131+jj*30);
CString tem=ss;
pDC->TextOut(104+j*30+9-3*tem.GetLength(),107+jj*30,tem);
}
//如果在VC6.0中，可以将以上代码全文直接粘贴到向导生成的单文档程序View类
//OnDraw(CDC* pDC)函数中。
奇数阶幻方构造方法(flag==1)：
德·拉·卢拜尔（De La Loubère）法则
首先将1放到第一行中间，然后将相继的数按自然顺序置入向右上方倾斜的
斜线上。到达边界时，从另一端开始。撞到填有数的格子，向右移动一格继续。
例如
17 24 01 08 15
23 05 07 14 16
04 06 13 20 22
10 12 19 21 03
11 18 25 02 09
单偶数阶幻方构造方法(flag==2)：
拉尔夫·斯特雷奇（Ralph Strachey）法则
对于M=4n+2;u=M/2
AC 先把整个幻方分成ABCD四个小幻方(如左)
DB 按照flag==1的方法构造A（1,u^2）；
B（u^2+1,2*u^2）；C（2*u^2+1,3*u^2）；D（3*u^2+1,4*u^2）。
将A的正中间行里从第二列起的n个方格、其他行里最靠左面的n个方格
与D中相应方格的数字互换。
然后将C的最右边的n-1列每个方格与B中的对应方格互换。
双偶数阶幻方构造方法(flag==3)：
将数自然顺序写入
例如M=8
12345678
9…………
……………
…………64
把每一个由4^2个方格组成的子块对角线上方格中的数字
换成其补格（中心对称格）中的数字。
通常，某阶幻方的解除了镜像、旋转外有多个(5阶幻方解超过1000万种)，这种方法仅得
到其中一个。
另外还有从M阶幻方基础上构造M+2阶幻方的标准方法，但是俺没编成程序。
算法出自：
上海教育出版社
通俗数学名著译丛《数学游戏与欣赏》第七章 幻方
【 在
hewind
(Romen) 的大作中提到: 】: 哪位大虾能帮小弟解决如下要求的算法，急！！！！！！！
────────────────────────────────────────
sino (茶水) 于 2002年09月04日08:29:59 星期三 说道:
参加ACM大赛吧！ :)
────────────────────────────────────────
SoonFaye (宠辱偕忘) 于 2002年09月04日08:57:48 星期三 说道:
大哥，这算法可是抄的~~~~ -_-!
────────────────────────────────────────
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：207.081毫秒