主题：各位高手们帮小弟做一道题好不好 我会给高分
gxb624
[专家分：0] 发布于 2005-07-25 17:03:00
Problem
在N*N的棋盘上(1<=N<=10)填入1,2,...N*N共N*N个数,使得任意两个相邻的数之和为素数.
例如,当N=2时,有
1 2
4 3
Input
输入第一行为一整数T,表示有T组测试数据.
每组测试数据一行,为一整数N(1<=N<=10)
要求：
输出满足条件的最小序列的方案。
最小序列即将每一行连接起来组成一行，然后使前面的尽可能小，当第一个数字相同时则比较下面一个，依次类推。
比如当Ｎ＝２时，序列为1 2 4 3，当无满足条件的方案时输出"NO"。
输入样例
1
2
输出样例
1 2
4 3
谢谢
回复列表 （共14个回复）
11 楼
泡泡糖 [专家分：230] 发布于 2005-07-27 20:58:00
怎么这么长！
12 楼
MagicG [专家分：650] 发布于 2005-07-27 22:34:00
偶淹在汗里了```
13 楼
雾川沧助 [专家分：0] 发布于 2005-07-29 08:34:00
同上!狂汗啊!
:>...........................................
14 楼
我笨故我在 [专家分：0] 发布于 2005-07-29 14:06:00
这不是NOIP97提高的题吗？很简单的！我的程序：
program tju1025;
const
maxn=10;
maxsum=2*sqr(maxn)-1;
var
prime:array[2..maxsum] of boolean;
ans:array[1..maxn,1..maxn,1..maxn]of byte;
next:array[0..sqr(maxn)]of byte;
t,i,n,x,y:byte;
finish:boolean;
procedure calprime;
var
i,t:byte;
begin
fillchar(prime,sizeof(prime),true);
for i:=2 to trunc(sqrt(maxsum)) do begin
if not prime[i] then continue;
t:=i+i;
while t<=maxsum do begin
prime[t]:=false;
inc(t,i);
end;
end;
end;
procedure search(x,y:byte);
var
p,i:byte;
begin
p:=0;
while next[p]>0 do begin
i:=next[p];
if ((x=1) or prime[i+ans[n,x-1,y]]) and ((y=1) or prime[i+ans[n,x,y-1]]) then begin
ans[n,x,y]:=i;
next[p]:=next[i];
if y=n then
if x=n then finish:=true else search(x+1,1)
else
search(x,y+1);
next[p]:=i;
if finish then exit;
end;
p:=i;
end;
end;
begin
calprime;
for n:=1 to maxn do begin
for i:=sqr(n-1) to sqr(n)-1 do
next[i]:=i+1;
finish:=false;
search(1,1);
if not finish then ans[n,1,1]:=0;
end;
read(t);
for i:=1 to t do begin
read(n);
if ans[n,1,1]=0 then
writeln('NO')
else
for x:=1 to n do begin
for y:=1 to n-1 do
write(ans[n,x,y],' ');
writeln(ans[n,x,n]);
end;
end;
end.
我来回复
您所在位置：