题目：
设有N个运动员要进行网球循环赛，设计一个满足以下要求的比赛日程表
(1)每个选手必须与其他n-1个选手各赛一次
(2)每个选手一天只能赛一次
(3)当n是偶数，循环赛进行n-1天，当n是奇数，循环赛进行n天。
思路分析：
如果n是奇数，其实就等于n+1种情况下将第n+1号选手轮空。所以只要考虑n是偶数的情况。用分治的思想来做，转换成n/2的子问题。考虑两种情况：
一、n/2为偶数。这种情况比较简单。例如n=4时。
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
可由n=2的子问题推出。
1 21 2 3 4
2 12 1 4 3
1 2 3 4 3 4 1 2
2 1-->4 3 --> 4 3 2 1
第一次变换下半部分=上半部分+n/2,第二次沿对角线对称。
二、n/2为奇数。由于n/2是奇数，子问题考虑n/2+1的情况。怎么由n/2+1的情况推出n的情况？
例如n=6时。先考虑它的子问题n=4时
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
由于四号选手是非法的所以：
1 2 3 0
2 1 0 3
3 0 1 2
同理推出
1 2 3 0
2 1 0 3
3 0 1 2
4 5 6 0
5 4 0 6
6 0 4 5
对第四列(第三天)，只有一号选手和四号选手没比赛，那就让他们比。推出
1 2 3 4
2 1 5 3
3 6 1 2
4 5 6 1
5 4 2 6
6 3 4 5
之后的两天，考虑为比过的两位选手比赛就行了。比赛的顺序按未比赛的后几个选手顺序取模。例如前三天出现了4那后两天为5 6。前三天出现了5后两天为6 4。
如此处理即可得到
1 2 3 4 5 6
2 1 5 3 6 4
3 6 1 2 4 5
4 5 6 1 2 3
5 4 2 6 3 1
6 3 4 5 1 2
#include
#include
#include
#include
using namespace std;
int mp[1100][1100];
void dfs(int n)
{
if(n==1)
{
mp[1][1]=1;
return ;
}
if(n&1) n++;
int t=n/2;
dfs(t);
for(int i=1;i<=t;i++)
for(int j=1;j<=t+1;j++)
{
if(mp[i][j]>t)
{
mp[i+t][j]=i;
mp[i][j]=i+t;
int c=i+t+1;
for(int k=t+2;(t&1)&&k<=n;k++,c++)
{
if(c==i+t) c++;
if(c>n) c-=n/2;
mp[i][k]=c;
mp[c][k]=i;
}
}
else
{
mp[i+t][j]=mp[i][j]+t;
if((t%2==0)||t==1)
{
mp[i+t][j+t]=mp[i][j];
mp[i][j+t]=mp[i+t][j];
}
}
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(mp,0,sizeof(mp));
if(n&1) dfs(n+1);
else dfs(n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n+(n&1);j++)
{
cout<n?0:mp[i][j]);
cout<
}
cout<
}
cout<
}
}
如果觉得《网球循环赛分治算法c语言 【算法作业】 循环赛问题 分治算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
