1. 幻方
把1至n*n的正整数填在n行n列的正方形图内,使每一行、每一列和二条对角线上n个数之和都相等。这样的方阵图叫做幻方。如右图所示是一个3行3列的幻方。
下面的程序生成一个n行n列的幻方。生成幻方的方法是:
法1.如果n为奇数,第一个数1填入第1行中间,下一个数填入的位置为:
(1)如果已填的数的个数为n的倍数,则填入下一行;
(2)否则填入上一行右一列。如果向上越界,则填至最后一行;如果向右越界,填至最前一列。
法2.如果n=4k,如下图所示,先将1~n*n的数按行优先的次序填入表格中。然后将表格分为k*k个小表格,每个小表格有4行4列。将每个小表格中二条对角线上的8个数以n*n+1去减,即如果原来位置上的数为x,则替换为n*n+1-x。
法3.如果n=4k+2,如下图所示,先将表格分成A、B、C、D四块,每块都是奇数行奇数列的,根据填入奇数幻方的方法,按ADBC的次序填好。然后:
(1)交换A、C块中间一列从中间一个元素开始的k个;
(2)交换A、C块其余各行第1列开始的k列;
(3)交换B、D块从中间1列左数k-1列;
请将程序补充完整。
program cz2011_5;
const maxn=1000;
var n,i,j,n1,i1,j1,p,k,tmp:longint;
a:array[1..maxn,1..maxn]of longint;
begin
readln(n);
if n=2 then begin writeln('No Solution!');exit;end;
if n mod 2=1 then begin
i:=1;j:=(n+1) div 2;
for p:=1 to n*n do begin
a[i,j]:=p;
if p mod n=0 then inc(i)
else begin
i:=i-1;j:=j+1;
if i<1 then i:=n;
if j>n then j:=1;
end;
end;
end else if n mod 4=0 then begin
for i:=1 to n do
for j:=1 to n do begin
a[i,j]:=(i-1)*n+j;i1:=i mod 4;j1:=j mod 4;
if (i1=j1)or(i1+j1=1) then a[i,j]:=n*n+1-a[i,j];
end;
end else begin
n1:=n div 2;
i:=1;j:=(n1+1) div 2; //stock A
for p:=1 to n1*n1 do begin
a[i,j]:=p;
if p mod n1=0 then i:=i+1
else begin
i:=i-1;j:=j+1;
if i<1 then i:=n1;
if j>n1 then j:=1;
end;
end;
i:=1+n1;j:=n1+(n1+1) div 2; //stock D
for p:=1+n1*n1 to 2*n1*n1 do begin
a[i,j]:=p;
if p mod n1=0 then i:=i+1
else begin
i:=i-1;j:=j+1;
if i<1+n1 then i:=n;
if j>n then j:=1+n1 ;
end;
end;
i:=1;j:=n1+(n1+1) div 2; //stock B
for p:=1+n1*n1*2 to 3*n1*n1 do begin
a[i,j]:=p;
if p mod n1=0 then i:=i+1
else begin
i:=i-1;j:=j+1;
if i<1 then i:=n1;
if j>n then j:=1+n1;
end;
end;
i:=1+n1;j:=(n1+1) div 2; //stock C
for p:=1+n1*n1*3 to n1*n1*4 do begin
a[i,j]:=p;
if p mod n1=0 then i:=i+1
else begin
i:=i-1;j:=j+1;
if i<1+n1 then i:=n;
if j>n1 then j:=1;
end;
end;
k:=n1 div 2 ;
for i:=1 to n1 div 2 do //swap some of A and D
for j:=1 to k do begin
tmp:=a[i,j];a[i,j]:=a[i+n1,j];a[i+n1,j]:=tmp;end;
for i:=n1 div 2+2 to n1 do //swap some of A and D
for j:=1 to k do begin
tmp:=a[i,j];a[i,j]:=a[i+n1,j];a[i+n1,j]:=tmp;end;
i:=(1+n1)div 2;
for j:=0 to k-1 do begin
tmp:=a[i,j+i];a[i,j+i]:=a[i+n1,j+i];a[i+n1,j+i]:=tmp;end;
j1:=n1+(1+n1) div 2; //swap some of B and C
for j:=0 to k-2 do
for i:=1 to n1 do begin
tmp:=a[i,j1-j];a[i,j1-j]:=a[i+n1,j1-j];a[i+n1,j1-j]:=tmp;end;
end;
for i:=1 to n do begin
for j:=1 to n-1 do write(a[i,j],' ');writeln(a[i,n]);end;
end.
2. 完美覆盖
有一个n行m列的棋盘,以1×2的多米诺骨牌去覆盖n×m的棋盘。当棋盘中的每一个格子都只被一块多米诺骨牌覆盖时,这种覆盖叫多米诺骨牌的完美覆盖。如下图所示,2行3列的棋盘,有3种完美覆盖方案。
以下程序求得总方案数。程序从第1行第1列开始,以行优先的顺序逐格尝试各格子的不同覆盖方案。
rogram cz2011_6;
const maxn=100;maxm=100;
var
n,m,i,j:longint;
ans:extended;
f:array[1..maxn,1..maxm]of longint;
procedure domino(i,j:longint);
begin
if i>n then begin
ans:=ans+1 ;
exit;
end;
if f[i,j]<>0 then
begin
if j<m then
domino(i,j+1)
else
domino( i+1,j );
end
else
begin
if (f]i,j]=0) and (f[i,j+1]=0) then
begin
f[i,j]:=1;
f[i,j+1]:=1;
if j<m then
domino(i,j+1)
else
domino( i+1,j );
f[i,j]:=0;f[i,j+1]:=0;
end;
if (f]i,j]=0) and (f[i+1,j]=0) then
begin
f[i,j]:=2;
f[i+1,j]:=2;
if j<m then
domino(i,j+1)
else
domino( i+1,j );
f[i,j]:=0;f[i+1,j]:=0;
end;
end;
end;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
f[i,j]:=0;
ans:=0;
domino( 1,1 );
writeln(ans:0:0);
end.