设有n个运动员,要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表
(1).每个选手必须与其他n-1个选手各赛一场
(2).每个选手一天只能赛一次
(3).循环赛一共进行n-1天
此题一般都是用递归分治解决,但是就是有点麻烦,这次介绍一种简单点的方法:多边形轮转法。



(1).每个选手必须与其他n-1个选手各赛一场
(2).每个选手一天只能赛一次
(3).循环赛一共进行n-1天
基本思路:当有奇数个人的时候画一个多边形,中心填0,例如当有5个人时,像这样:
平行的人比赛,5<->2,4<->3,1和0打,表示轮空:
此时转动多边形:
依次轮换,转动5次既是全部的结果。
当人数为偶数的时候,把0替换为人即可。
注意: 一定要画奇数边的多边形
当人数为偶数的时候,把0替换为人即可。
注意: 一定要画奇数边的多边形
#include<bits/stdc++.h>
using namespace std;
int main()
{
int l,r,n;
int num ;
scanf("%d",&n);
num = n;
n = (n%2==1) ? n: (n-1); // 当是偶数人的时候,变成奇数,用于画多边形
for(int i = 1; i <=n ; i++)//每个顶点轮转一次
{
//当是奇数人的时候,每天都会有人轮空
if(num%2==1) printf("第%d天:%d 轮空\n", i,i,n);
//否则的话和中心的n号比赛
else printf("第%d天:\n%d <--> %d\n",i,i,num);
//计算左边右边的人(平行的人),取余是判断是否超过n人
l = (i+1) % n ? (i+1) % n : n;
r = (i-1) % n ? (i-1) % n : n;
for(int j = 1; j<=n/2; j++)//平行边数的遍历
{
printf("%d <---> %d\n",l,r);
l = (l+1) % n ? (l+1) % n : n;
r = (r-1) % n ? (r-1) % n : n;
}
}
}

京公网安备 11010502036488号