问题:设有n=2^k个选手参加循环赛,要求设计一个满足以下要求比赛日程表:
1)每个选手必须与其它n-1个选手各赛一次;
2)每个选手一天只能赛一次。
按照上面的要求,可以将比赛表设计成一个n行n-1列的二维表,其中第i行第j列的元素表示和第i个选手在第j天比赛的选手号,也就是对手。
采用分治策略,可将所有参加比赛的选手分成两部分,n=2^k个选手的比赛日程表就可以通过n=2^(k-1)个选手的的比赛日程表来决定。递归的执行这样的分割,直到只剩下两个选手,比赛日程表的就可以通过这样的分治策略逐步构建。
从0开始对列编号,0列是自己跟自己打,1列是第一天比赛的对手号码。表的颜色相同部分是一样的。
队伍只有两个时:
队伍四个时:
队伍八个时:
算法如下:
初始化一个数组a[n-1][n-1],输入:队伍数目n。
一、n=0的时候
a[0][0]=1;
二、n>0
1、n>0的时候把问题一分为二,递归地把左上角的矩阵生成好。
2、然后根据左上角矩阵,让右上角矩阵对应元素+n/2。
3、再把左下角元素和右上角元素对应起来,右下角元素和左上角元素对应起来。
代码
#include<iostream>using namespace std;#define M 10000int a[M][M]={0};void merge(int n){int m= n/2;for(int i=0;i<m;i++)for(int j=0;j<m;j++){a[i][j+m]=a[i][j]+m; //由左上角得到右上角a[i+m][j]=a[i][j+m]; //由右上角得到左下角a[i+m][j+m]=a[i][j]; //由左上角得到右下角}}void arrangement(int n){if(n==1){a[0][0]=1;return;}arrangement(n/2); merge(n); }int main(){int n;cout<<"请输入需要比赛的队伍数(偶数):"<<endl;cin>>n;cout<<"赛程安如下:"<<endl;arrangement(n);for(int i=0; i<n;i++){for(int j=0;j<n;j++)cout<<a[i][j]<<" ";cout<<endl;}return 0;}
如果觉得《算法-分治法-循环赛的日程安排》对你有帮助,请点赞、收藏,并留下你的观点哦!