P1293循环赛问题.doc

P1293循环赛问题.doc循环赛问题题目解析:认真观察图表,从小见大!在问题的处理上,首先从规模小的情况开始分析,比如:n=2,n=4……,这样比较容易去发现解决问题的一般规律,可以将问题一分为四去看。又如:当K=3时,如右图(一种方输出方案)(第一列为可看成队员编号)蓝色区域内的输出,可看为红色对应元素加4得到把左上角(红)拷贝到右下角,把左下角(蓝)拷贝到右上角。《数据结构与算法设计》:P192programxunhuansai;constmaxn=100;vara:array[1..maxn,1..maxn]ofinteger;i,j,k,n:integer;{分治法求解:从x号选手到y号选手的比赛日程的安排过程}procedurearrangment(x,y:integer);varday:integer;{用来判断选手是否相邻}i,j,k,m:integer;beginday:=y-x;ifday=1then{递归边界条件处理:选手相邻,直接输出解}begina[x,1]:=y;a[y,1]:=x;endelsebegin{分治法:规模二分}m:=(x+y)div2;arrangment(x,m);{递归处理前一半选手}arrangment(m+1,y);{递归处理后一半选手}fori:=xtomdo{合并前一半解,参看右上角蓝色区域中的赋值}begina[i,daydiv2+1]:=i+m-x+1;forj:=daydiv2+2todaydoa[i,j]:=a[i+(m-x+1),j-(daydiv2+1)];{对称下标赋值}end;fori:=m+1toydo{合并后一半解}begina[i,daydiv2+1]:=i-(m-x+1);forj:=daydiv2+2todaydoa[i,j]:=a[i-(m-x+1),j-(daydiv2+1)];end;end;end;beginreadln(k);n:=1;fori:=1tokdon:=nshl1;{选手人数计算:n}arrangment(1,n);{选手1号至n号比赛安排}fori:=1tondobeginwrite(i:3,'.');forj:=1ton-1dowrite(a[i,j]:3);writeln;end;;constmaxn=100;vara:array[0..maxn-1,0..maxn-1]ofinteger;i,j,n:integer;{从k号运动员起共N号运动员单循环比赛日程表的过程}procedurearrangment(k,n:integer);vari,j:integer;beginifn=2then{n=2时,处理只2名运动员的情况,递归终止条件:直接输出问题解}begina[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,ndiv2);{处理区域1:分治法处理:递归分解原问题与求解