P1293循环赛问题.doc

循环赛问题题目解析：一、 认真观察图表，从小见大！在问题的处理上，首先从规模小的情况开始分析，比如：n=2,n=4，这样比较容易去发现解决问题的一般规律，可以将问题一分为四去看。又如：当K=3时,如右图（一种方输出方案）(第一列为可看成队员编号)蓝色区域内的输出，可看为红色对应元素加4得到把左上角(红)拷贝到右下角, 把左下角(蓝)拷贝到右上角。数据结构与算法设计：P192program xunhuansai;const maxn=100;var a:array1.maxn,1.maxnof 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 ax,1:=y; ay,1:=x; end else begin 分治法：规模二分 m:=(x+y)div 2; arrangment(x,m);递归处理前一半选手 arrangment(m+1,y);递归处理后一半选手 for i:=x to m do合并前一半解，参看右上角蓝色区域中的赋值 begin ai,day div 2+1:=i+m-x+1; for j:=day div 2+2 to day do ai,j:=ai+(m-x+1),j-(day div 2+1);对称下标赋值 end; for i:=m+1 to y do合并后一半解 begin ai,day div 2+1:=i-(m-x+1); for j:=day div 2+2 to day do ai,j:=ai-(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(ai,j:3); writeln; end;gram xunhuansai2;const maxn=100;var a:array0.maxn-1,0.maxn-1of integer; i,j,n:integer;从k号运动员起共N号运动员单循环比赛日程表的过程procedure arrangment(k,n:integer); var i,j:integer; begin if n=2 thenn=2时，处理只2名运动员的情况，递归终止条件：直接输出问题解 begin ak,0:=k; ak,1:=k+1; ak+1,0:=k+1; ak+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 ai,j:=ai+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 ai,j:=ai-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(ai,j:3); writeln; end;end.分治合策略总结：（1） 原问题可以分解成多个子问题，这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。（2） 原问题在分解过程中，递归地求解子问题，由于递归都必须有一个终止条件，因此当分解后的子问题规模足够小时，应能够直接求解。（3） 在求解并得出各个子问题的解