算法分析与设计PPT03-递归与分治 - 5 循环赛日程表.ppt

1、3.2.4循环赛日程表循环赛日程表问题描述：设有问题描述：设有n2k个运动员要进行网球循环赛。个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：现要设计一个满足以下要求的比赛日程表：1.每个每个选手必须与其他选手必须与其他n1个选手各赛一次；个选手各赛一次；2.每个每个选手一天只能参赛一次；选手一天只能参赛一次；3.循环赛循环赛在在n1天内结束。天内结束。l 请按此要求将比赛日程表设计成有请按此要求将比赛日程表设计成有n行和行和n1列的一个表列的一个表。l 在在表中的第表中的第i行，第行，第j列处填入第列处填入第i个选手在第个选手在第j天所遇到的选手，天所遇到的选手，其中其中1i

2、n，1jn1。13.2.4循环赛日程表循环赛日程表12345678214365873412785643218765123456781234天数天数21436587214312341278563412214321876543211个选手个选手4个选手个选手8个选手个选手2每个选手必须与其他每个选手必须与其他n1个选手各赛一次；个选手各赛一次；每个选手一天只能参赛一次；每个选手一天只能参赛一次；循环赛在循环赛在n1天内结束。天内结束。第第1 1天，天，1 1与与2 2比，比，2 2与与1 1比比/构造循环赛日程表，构造循环赛日程表，选手的数量选手的数量N2K3void Table(int k)in

3、t i,r;int n=1 k;/构造正方形表格的第一行数据构造正方形表格的第一行数据for(i=0;in;i+)a0i=i+1;/采用分治算法，构造整个循环赛日程表采用分治算法，构造整个循环赛日程表for(r=1;rn;r=1)for(i=0;in;i+=2*r)Copy(r,r+i,0,i,r);/Copy(r,i,0,r+i,r);/实现方阵的拷贝实现方阵的拷贝/源方阵的左上角顶点坐标（源方阵的左上角顶点坐标（fromx,fromy），行列数为），行列数为r/目标方阵的左上角顶点坐标（目标方阵的左上角顶点坐标（tox,toy），行列数为），行列数为rvoid Copy(int tox,int toy,int fromx,int fromy,int r)for(int i=0;ir;i+)for(int j=0;jr;j+)atox+itoy+j=afromx+ifromy+j;4