求能计算所有方阵的程序

lordbyorn · 发表于 2003-7-6 19:28:34

N 阶方阵是把 1 - N^2 填在 N*N 的矩阵里，
使得每行、每列、对角线的和都相等；
N 能做到多大就多大拉。

下面是我的一个程序（N=5 时就难于忍受了）：

/***********************
*** Fifth version *****
***********************/
#include<time.h>
#include<stdio.h>
#define Max 100
int END;
int M;
int sum;
int maxnum,minnum;
int data[Max*Max];
int flags[Max*Max];
FILE *outfile;
time_t start,end;
int bottom,top,left;
int head,tail,cursor;
void init();
void bye();
void range(int);
void magic(int);
void output(void);
void print_status(void);
main()
{
init();
magic(0);
bye();
return 0;
}
void init()
{
int i;
outfile=fopen("result.txt","w");
for(i=0;i<Max*Max;i++)flags[i]=0;
printf(" Input M:");
scanf("%d",&M);
sum=(M*M+1)*M/2;
END=M*M-1;
start=time(&start);
fprintf(outfile,"start at %s\n//////////////////////////////////\n",ctime(&start));
}
void bye()
{
end=time(&end);
fprintf(outfile,"\n//////////////////////////////////\nend at %s\n",ctime(&end));
fclose(outfile);
}
void magic(int n)
{
int i;
int max;
range(n);
i=minnum;
max=maxnum;
for(;i<=max;i++)
{if(flags[i]==0){
flags[i]=1;
data[n]=i+1;
if(n==(END)){output(); }
else magic(n+1);
flags[i]=0;
}
}
return;
}
void output()
{
int i,j;
for(i=0;i<M;i++)
{for(j=0;j<M;j++)
{
fprintf(outfile,"%5d",data[i*M+j]);
}
fputc('\n',outfile);
}
fputs("*****************************************\n",outfile);
fflush(outfile);
}
/******************* This function to large!!! ************/
/* calculate the range for the next data */
void range(int n) //not so easy to understand.
{
static int i,j,k;
static int used=0;
used=0;
i=(n/M)*M;
cursor=n%M;
j=i+cursor;
left=sum;
for(;i<j;i++)
used+=data[i];
k=M-cursor-1;
top=bottom=sum-used-1;
for(i=END;k>0;i--)
if(flags[i]==0)
{bottom-=i+1;k--;}
tail=END;
k=M-cursor-1;
for(i=0;k>0;i++)
if(flags[i]==0)
{top-=i+1;k--;}
head=0;
for(;flags[head]!=0;head++);
minnum=bottom>head?bottom:head;
for(;flags[tail]!=0;tail--);
maxnum=top<tail?top:tail;
cursor=n/M;
j=(n%M);
for(used=0,i=0;i<cursor;i++)
used+=data[i*M+j];
top=bottom=sum-used-1;
for(i=END,k=M-cursor-1;k>0;i--)
if(flags[i]==0)
{bottom-=i+1;k--;}
for(i=0,k=M-cursor-1;k>0;i++)
if(flags[i]==0)
{top-=i+1;k--;}
minnum=minnum>bottom?minnum:bottom;
maxnum=maxnum<top?maxnum:top;
if(cursor==j)
{
for(used=0,i=0;i<cursor;i++)
used+=data[i*M+i];
top=bottom=sum-used-1;
for(i=END,k=M-cursor-1;k>0;i--)
if(flags[i]==0)
{bottom-=i+1;k--;}
for(i=0,k=M-cursor-1;k>0;i++)
if(flags[i]==0)
{top-=i+1;k--;}
minnum=minnum>bottom?minnum:bottom;
maxnum=maxnum<top?maxnum:top;
}
if((cursor+j+1)==M)
{
for(used=0,i=0,j=M-1;i<cursor;i++,j--)
used+=data[i*M+j];
top=bottom=sum-used-1;
for(i=END,k=M-cursor-1;k>0;i--)
if(flags[i]==0)
{bottom-=i+1;k--;}
for(i=0,k=M-cursor-1;k>0;i++)
if(flags[i]==0)
{top-=i+1;k--;}
minnum=minnum>bottom?minnum:bottom;
maxnum=maxnum<top?maxnum:top;
}
}

复制代码

lordbyorn · 发表于 2003-7-6 19:48:07

这个很难的。
如果有人在 10 天内写出程序，用 1 hour 计算出 N=10的所有方阵的话，我跳楼算了！！

maillistcs · 发表于 2003-7-6 20:43:21

你跳楼吧

maillistcs · 发表于 2003-7-6 20:52:16

问题表述不清楚,没有说清是否是数字1到N^2 添入的数字是否允许重复.

kj501 · 发表于 2003-7-6 21:04:56

这种方阵称为幻方。是一个历史悠久的数学问题。看看这个就清楚了。
http://yamaths.myrice.com/zhghf/

libinary · 发表于 2003-7-6 21:44:45

随手写了一个，中间的循环部分怎么看都觉得难看的很，呵呵
这个程序只能处理奇数的方阵，偶数的我还没搞懂。
(一个小时用不了吧，一秒钟就完了)

#include <stdio.h>
int *a;
int main(int argc, char *argv[])
{
int n, x, y, i;
if(argc == 1){
fprintf(stderr, "usage: %s number\n", argv[0]);
exit(-1);
}
n = atoi(argv[1]);
a = (int *)calloc(n * n, sizeof(*a));
x = n / 2;
y = n - 1;
i = 1;
*(a + y * n + x) = i;
++x; ++y; ++i;
while(i <= n * n){
if(i % n == 1){
y -= 2;
--x;
}
if(x >= n)
x = 0;
if(y >= n)
y = 0;
*(a + y * n + x) = i;
++x; ++y; ++i;
}
for(y = n - 1; y >= 0; --y){
for(x = 0; x < n; ++x)
printf("%2d ", *(a + y * n + x));
printf("\n");
}
free(a);
exit(0);
}

复制代码

kj501 · 发表于 2003-7-6 22:05:18

libinary兄，楼主的意思是计算所有满足条件的方阵，不是只计算一个。

libinary · 发表于 2003-7-6 22:16:40

哦，没搞懂楼主的意思。

lordbyorn · 发表于 2003-7-6 23:15:32

写奇数的我自己都还其它写法.

难的地方在于要写出所有的.

lordbyorn · 发表于 2003-7-6 23:17:07

最初由 maillistcs 发表
问题表述不清楚,没有说清是否是数字1到N^2 添入的数字是否允许重复.

我认为大家都知道这样的问题.

		自动登录	找回密码
密码			注册