分治算法——乒乓球赛日程安排

日程安排"/>

分治算法——乒乓球赛日程安排

问题：

设有n位选手参赛，初赛进行n-1天，每位选手每天必须比赛一次，不能轮空。编程求解赛程安排。

分析：

• 求n位选手的赛程安排，可采用分治算法的思想，将问题规模不断缩小，比如缩小到8，4，2等规模大小；

• 分析2，4，8等小规模时的赛程安排：

AC

#include <bits/stdc++.h>
#define maxn 64
using namespace std;
int a[maxn+1][maxn+1]={0};
void game(int k,int n){            //处理编号k开始的n个选手的日程 int i,j;if(n==2){a[k][1]=k;                //参赛选手编号 a[k+1][1]=k+1;            //对阵选手编号 a[k][2]=k+1;              //参赛选手编号 a[k+1][2]=k;              //对阵选手编号 }else{game(k,n/2);game(k+n/2,n/2);for(i=k;i<k+n/2;i++){          //填充右上角 for(j=n/2+1;j<=n;j++){a[i][j]=a[i+n/2][j-n/2];}}for(i=k+n/2;i<k+n;i++){        //填充右下角 for(j=n/2+1;j<=n;j++){a[i][j]=a[i-n/2][j-n/2];}}}
}int main(){int i,j,m;cout<<"请输入参赛选手人数："<<endl;cin>>m;j=2;for(i=2;i<8;i++){j*=2;if(j==m)break;} if(i>=8){cout<<"参赛选手人数必须为2的整数次幂，且不超过64！"<<endl;getchar();return 0; }game(1,m);cout<<endl<<"编号";for(i=2;i<=m;i++)cout<<setw(2)<<i-1<<"天";cout<<endl;for(i=1;i<=m;i++){for(j=1;j<=m;j++){cout<<setw(4)<<a[i][j];}cout<<endl;}getchar();return 0;
}