首页 > 代码库 > 分治 赛程安排

分治 赛程安排

2024-07-15 20:03:25   226人阅读

问题描述：有n个运动员进行循环赛，要求设计满足一下要求的日程表

1、  每两人必须比赛一次且只比赛一次

2、  每个选手每天只能比赛一次

3、  要求比赛时间尽可能短（即n为偶数时比赛n-1天，n为奇数时比赛n天）

一、分治法

算法思想，先算n/2的日程表，然后将循环赛日程表左上复制到右下，左下复制到右上，得到n的日程表，递归实现

 

 

#include <stdio.h>#define N 1000int a[N][N];int b[N]; bool odd(int n){    return n%2;}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 <stdio.h>#define N 1000int a[N][N];bool odd(int n){    return n & 1;}void init(){    int i;    for(i=1; i<=N; ++i)        a[i][0]=i;    ///for(int i=0;i<N;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<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;}

输出自己看一下  还有一个输出样式不一样的

#include <iostream>#include <string.h>#include <stdio.h>using namespace std;#define MAX 210int a[MAX][MAX];int main(){    int n;    while(scanf("%d", &n) != EOF)    {        int k;        memset(a,0,sizeof(a));        int l=2*n+1;        for(int i=1;i<=l;i++)        {k=i-1;            for(int j=1;j<=i;j++)            {                if(i!=j)                a[i][j]=k++;                if(k>l)                k=1;                a[j][i]=a[i][j];            }        }        for(int i=1;i<=l;i++)        {            for(int j=1;j<=l;j++)            {                printf("%d",a[i][j]);                //cout<<a[i][j];                if(j!=l)                printf(" ");            }            printf("\n");        }    }    return 0;}/*0 1 21 0 32 3 0*/

 


联系
我们