问题描述:有n个运动员进行循环赛,要求设计满足一下要求的日程表
1、
每两人必须比赛一次且只比赛一次
2、
每个选手每天只能比赛一次
3、
要求比赛时间尽可能短(即n为偶数时比赛n-1天,n为奇数时比赛n天)
一、分治法
算法思想,先算n/2的日程表,然后将循环赛日程表左上复制到右下,左下复制到右上,得到n的日程表,递归实现
实现代码:
//循环赛日程表
#include
#define N
1000
int
a[N][N];
int
b[N];
inline
bool odd(int n)
{
return n & 1;
}
void
copy(int n)//将左上角抄到右下角,将右上角加n/2后抄到左下角,将左下角抄到右上角
{
int m=n/2;
int i,j;
for(i=1;i<=m;++i)
for(j=1;j<=m;++j)
{
a[i][j+m]=a[i][j]+m;//将左上角抄到右下角
a[i+m][j]=a[i][j+m];//将右上角加n/2后抄到左下角
a[i+m][j+m]=a[i][j];//将左下角抄到右上角
}
}
void
copyodd(int n)//n/2为奇数时的复制,让轮空选手与下一个为参赛选手进行比赛
{
int m=n/2;
int i,j;
for(i=1;i<=m;++i)
{
b[i]=m+i;
b[m+i]=b[i];
}
for(i=1;i<=m;++i)
{
for(j=1;j<=m+1;++j)
{
if(a[i][j]>m)
{
a[i][j]=b[i];
a[m+i][j]=(b[i]+m)%n;
}
else
a[m+i][j]=a[i][j]+m;
}
for(j=2;j<=m;++j)
{
a[i][m+j]=b[i+j-1];
a[b[i+j-1]][m+j]=i;
}
}
}
void
makecopy(int n)
{
if(n/2>1 &&
odd(n/2)) copyodd(n);
else copy(n);
}
void
tour(int n)
{
if(n==1)
{
a[1][1]=1;
return;
}
if(odd(n))
{
tour(n+1);//当n为奇数,就设置一个虚拟的n+1,然后就有偶数个人了。。。。和一休的那个分马很像啊
return;
}
tour(n/2);
makecopy(n);
}
void
out(int n)
{
if(n==1)
{
printf("1\n");
return;
}
int i,j;
int m;
if(odd(n))
m=n+1;
else
m=n;
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
if(a[i][j]>n)//当比赛日程是与那位虚拟出来的n+1号选手比赛时,输出0,代表轮空
printf("0 ");
else
printf("%d ",a[i][j]);
}
printf("\n");
}
}
int
main()
{
int n;
while(scanf("%d",&n),n)
{
tour(n);
out(n);
}
return 0;
}
2、多边形法(我的实现),通过旋转多边形的一种巧妙方法
//循环赛日程表
#include
#define N
1000
int
a[N][N];
inline
bool odd(int n)
{
return n & 1;
}
void
init()
{
int i;
for(i=0;i
a[i][0]=i;
}
void
tour(int n)
{
if(odd(n))
tour(n+1);
else
{
int i,j,k;
int m=n-1;
int p,q;
for(i=1;i<=m;++i)//第一天到第n-1天
{
j=i;
p=j+1;
if(p>m) p=p-m;
a[p][i]=n;
a[n][i]=p;
for(k=0;k<=n/2-2;++k)
{
q=j-k;
p=j+k+2;
if(p>m) p-=m;
if(q<=0) q+=m;
a[q][i]=p;
a[p][i]=q;
}
}
}
}
void
out(int n)
{
if(n==1)
{
printf("1\n");
return;
}
int i,j;
int m;
if(odd(n))
m=n+1;
else
m=n;
for(i=1;i<=n;++i)
{
for(j=0;j
{
if(a[i][j]>n)
printf("0 ");
else
printf("%d ",a[i][j]);
}
printf("\n");
}
}
int
main()
{
int n;
init();
while(scanf("%d",&n),n)
{
tour(n);
out(n);
}
return 0;
}
4、
多边形法(王晓东算法设计与分析教材上的实现,比较费解,比较牛逼)
#include
#define N
1000
int
a[N][N];
int
b[N];
inline
bool odd(int n)
{
return n & 1;
}
void
init()
{
int i;
for(i=0;i
a[i][0]=i;
}
void
tour(int n)
{
a[n][1]=n;
if(n==1) return;
int m=odd(n) ? n : n-1;
int i,j,k,r;
for(i=1;i<=m;++i)
{
a[i][1]=i;
b[i]=i+1;
b[m+i]=i+1;
}
for(i=1;i<=m;++i)
{
a[1][i+1]=b[i];
a[b[i]][i+1]=1;
for(j=1;j<=m/2;++j)
{
k=b[i+j];
r=b[i+m-j];
a[k][i+1]=r;
a[r][i+1]=k;
}
}
}
void
out(int n)
{
if(n==1)
{
printf("1\n");
return;
}
int i,j;
int m;
if(odd(n))
m=n+1;
else
m=n;
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
if(a[i][j]>n)
printf("0 ");
else
printf("%d ",a[i][j]);
}
printf("\n");
}
}
int
main()
{
int n;
init();
while(scanf("%d",&n),n)
{
tour(n);
out(n);
}
return 0;
}
如果觉得《循环日程表递归法c语言 分治与递归——循环赛日程表》对你有帮助,请点赞、收藏,并留下你的观点哦!