循环赛日程表_文档.docVIP

循环赛日程表文档 一、问题描述： 设有n个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表： 1.每个选手必须与其他n-1个选手各赛一次； 2.每个选手一天只能参赛一次； 3.n是偶数时,循环赛在n-1天内结束。n是奇数时,循环赛进行n天. 二：程序源代码： #include stdio.h #includestdlib.h void Table ( int **a , int n); int main() { int i=1,j; int days,n; int **a; //日程表数组 printf(请输入运动员人数：); scanf(%d,n); if (n=1) printf(不可能出现此数据); else { a=new int* [n+1]; //行表示运动员 days = n%2==0?n-1:n; //比赛天数，n是偶数时,n-1天。n是奇数时,n天. for(i=1;i=(n+1);i++) a[i] = new int [days+1]; } if(n%2!=0) Table(a,n); else { Table(a,n-1); //加入第n个运动员的比赛日程，只需将其加入到前n-1个运动员日程中轮空位置即可 for(i=1;i=n;i++) { a[i][i]=n; a[n][i]=i; } } //输出表头 printf(\n ); for(j=1;j=days;j++) printf(第%d天 ,j); printf(\n); //输出比赛日程 for(i=1;i=n;i++) { printf(第%d号 ,i); for(j=1;j=days;j++) printf(%d ,a[i][j]); printf(\n); } printf(\n); system(pause); } void Table ( int **a , int n) { int i,j,m1,m2; int *b; //指向对阵关系数组 //建立初始对阵关系（,n-1,2,n-2,...,i,n-i） b=new int [n]; //0下标不用 for(i=1;i=n/2;i++) { b[2*i-1]=i; b[2*i]=n-i; } for(i=1;i=n;i++)//i控制天数变化 { a[i][i]=0; //n为奇数时在第i天第i号运动员轮空 for(j=1;j=(n-1);j+=2) { //第i天m1与m2对阵 m1=((b[j]+i)=n)?(b[j]+i):(b[j]+i)%n; m2=((b[j+1]+i)=n)?(b[j+1]+i):(b[j+1]+i)%n; a[m1][i]=m2; a[m2][i]=m1; } } } 三：程序输出范例： 1.n为偶数时。 2.n为奇数时： 其中“0”表示这一天该运动员不与其他运动员比赛。 四：算法设计分析： 单循环赛，是所有参加比赛的队伍均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。这种竞赛方法满足（假设有n支队伍）：a、每支队伍必须与其他n-1支队伍各赛一次；b、每支队伍每轮只能进行一场比赛。很明显，当 n为奇数时，需进行n轮比赛；当 n为偶数时，需进行n-1轮比赛。首先考虑n为奇数的情况，在此基础上再考虑n为偶数时的情况。?　　(1)当比参赛队（或人）为奇数即n=2*k-1 (n≥2)时，考虑到每轮均有一支队伍轮空，先将队伍一分为二，每轮比赛在前后两部分中依次选取一支队伍进行比赛，第一轮将k号选手轮空，利用对称性，将1号队伍和n号队伍比赛，2号队伍和n-1号队伍比赛，依此类推排完第一轮选手的比赛；第二轮将k+1号队伍轮空，再将2号队伍和1号队伍比赛，3号队伍和n号队伍比赛，依此类推排完第二轮选手的比赛；为了避免两个队之间出现重复比赛，所以用循环队列的方式解决每轮轮空队伍的编号，即编号为n的队伍轮空的下一轮为编号1的队伍轮空。例：7支队伍参加比赛的排法：　　循环队列?　　第一轮 1-7 2-6 3-5?　　第二轮 2-1 3-7 4-6?　　第三轮 3-2 4-1 5-7?　　第四轮 4-3 5-2 6-1?　　第五轮 5-4 6-3 7-2?　　第六轮 6-5 7-4 1-3?　　第七轮 7-6 1-5 2-4? 　　(2)当比赛队伍数为偶数即n