设有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; } } }