算法理论与分析实验

《算法理论与分析实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一：1、问题描述：设计一个满足以下耍求的比赛日程表：(1)每个选手必须与其他n・l个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行ml天。用分治法实现。2、算法描述：按分治策略，将所有分为两半，n个选手可以通过n/2个选手设计的比赛日程表来决定。递归地用一分为二的略对选手进行分割，直到只剩下两个选手。对于n为奇数的情况可以虚拟多一个选手，使其编程n+1个选手的日程表，最然后忽略虚拟运动员参与的比赛。对于分割时候n/2的情况也做特殊处理，HUn/2轮比赛空选手与下一个未参赛的选手进行比赛。伪代码如下：voidtournament(intm){if(

2、m==l){A[0][0]=l;return;elseif(isodd(m))〃如果m为奇数，则m+1是偶数toumament(m+l);〃按照偶数个选于•来求解replaceVirtual(m+l);〃然后把第m+1号虚选手置成0return;}else//r如果m是偶数，Itoumament(m/2);〃分治，先安排第1组的in/2人比赛makecopy(m);〃合并，根据算法，构造左下、右下、右上、右下的矩阵return;〃判断m的奇偶性boolisodd(m)Returnm&l;〃m为奇数，返回1,m为偶数，返回0/*makecopy:当前有m位(偶数)选手，

3、分成两组，每组由m/2位选手构成由第一组的m/2位选手的安排来构成第二组的比赛安排，第一组与第二组的比赛女排。要区分m/2为奇数和偶数两种情况*/voidmakecopy(intm){if(isodd(m/2))//m/2为奇数copyodd(m/2);else//m/2为偶数copyeven(m/2);}/*copyeven:m为偶数时用，由前1组的m位选手的女排，来构成第2组m位选手的赛程安排，以及两组之间的比赛安排*/voidcopyeven(intm){if(isodd(m))return;intij;for(j=O;j

4、m){for(i=0;i

5、j]=A[i-m]

6、j-m];//ftl左上角拷贝到右下角}}return;}/*copyodd:m为奇数时用,

7、

8、

9、

10、]01组的m位选手的安排，来构成笫2组m位选手的赛程安排，以及两组Z间的比赛安排。这时和ni为偶数时的处理有区别。*

11、/voidcopyodd(intm)inti,j;for(j=0;j<=m;j++)//l.求第2组的女排(前m天){for(i=0;ivm;i++)〃行{if(A[i]fj]!=O){A[i+m]U]=A[i][j]+m;}else〃特殊处理：两个队各有一名选手有空，安排他们比赛{A[i+m]

12、j]=i+l;A[i][j]二i+m+1;}〃安排两组选手Z间的比赛(后m-1天)for(i=0,j=m+l;j<2*m;j++){A[i][j]=j+1;//2.1号选手的后m・l天比赛A[(A[i][j]-1)][j]=i+1;〃3.他的对手后m-1天的安排〃以下的取值要

13、依赖于1号选手的安排，所以之询先安排1号的赛程for(i=l;i

14、选手人数:10第1列是选手编号12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321PressanykeytocontinueX4、源程序#include#includeint**A;int*schedule;intN=1;//int*指针数组,//int数组，一维数组保存二维数组的数据〃问题的规模。初始化时会设定//isodd：判断X是否奇数，是则