P1293循环赛问题.doc

循环赛问题
题目解析：
一、 认真观察图表，从小见大！
在问题的处理上，首先从规模小的情况开始分析，比如：n=2,n=4……，这样比较容易去发现解决问题的一般规律，可以将问题一分为四去看。
又如：当K=3时,如右图（一种方输出方案）
(第一列为可看成队员编号)蓝色区域内的输出，可看为红色对应元素加4得到把左上角(红)拷贝到右下角, 把左下角(蓝)拷贝到右上角。

《数据结构与算法设计》：P192
program xunhuansai;
const maxn=100;
var
a:array[1..maxn,1..maxn]of integer;
i,j,k,n:integer;
{分治法求解：从x号选手到y号选手的比赛日程的安 排过程}
procedure arrangment(x,y:integer);
var
day:integer;{用来判断选手是否相邻}
i,j,k,m:integer;
begin
day:=y-x;
if day=1 then {递归边界条件处理：选手相邻，直接输出解}
begin
a[x,1]:=y;
a[y,1]:=x;
end
else begin {分治法：规模二分}
m:=(x+y)div 2;
arrangment(x,m);{递归处理前一半选手}
arrangment(m+1,y);{递归处理后一半选手}
for i:=x to m do{合并前一半解，参看右上角蓝色区域中的赋值}
begin
a[i,day div 2+1]:=i+m-x+1;
for j:=day div 2+2 to day do
a[i,j]:=a[i+(m-x+1),j-(day div 2+1)];{对称下标赋值}
end;
for i:=m+1 to y do{合并后一半解}
begin
a[i,day div 2+1]:=i-(m-x+1);
for j:=day div 2+2 to day do
a[i,j]:=a[i-(m-x+1),j-(day div 2+1)];
end;
end;
end;
begin
readln(k);
n:=1;
for i:=1 to k do n:=n shl 1; {选手人数计算：n}
arrangment(1,n);{选手1号至n号比赛安排}
for i:=1 to n do
begin
write(i:3,'.');
for j:=1 to n-1 do write(a[i,j]:3);
writeln;
end;
end.

program xunhuansai2;
const maxn=100;
var
a:array[0..maxn-1,0..maxn-1]of integer;
i,j,n:integer;
{从k号运动员起共N号运动员单循环比赛日程表的过程}
procedure arrangment(k,n:integer);
var
i,j:integer;
begin
if n=2 then{n=2时，处理只2名运动员的情况，递归终止条件：直接输出问题解}
begin
a[k,0]:=k; a[k,1]:=k+1;
a[k+1,0]:=k+1; a[k+1,1]:=k;
exit;
end; {原问题＝处理区域1+处理区域2+处理区域3+处理区域4四个子问题之和}
arrangment(k,n div 2);{处理区域1：分治法处理：递归分解原问题与求解子问题}
arrangment(k+n div 2,n div 2);{处理区域2：}
for i:=k to k+n div 2-1 do
for j:=n div 2 to n-1 do
a[i,j]:=a[i+n div 2,j-n div 2];{做处理区域2的对称，求：处理区域3：}
for i:=k +n div 2 to k+n-1 do
for j:=n div 2 to n-1 do
a[i,j]:=a[i-n div 2,j-n div 2];{做处理区域1的对称，求：处理区域4：}
end;
begin
readln(n);
arrangment(1,n);
for i:=1 to n do
begin
write(i:3,'.');
for j:=1 to n-1 do write(a[i,j]:3);
writeln;
end;
end.

分治合策略总结：
（1） 原问题可以分解成多个子问题，这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
（2） 原问题在分解过程中，递归地求解子问题，由于递归都必须有一个终止条件，因此当分解后的子问题规模足够小时，应能够直接求解。
（3） 在求解并得出各个子问题的解后，应能够采用某种方式、方法合并或构造出原问题的解。
利用分治策略解题时，所需时间取决于分解后的子问题的个数、子问题规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一个有效方法。