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

秒速五厘米 2022-09-06 10:27 189阅读 0赞

## 问题： ##

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

--------------------

## 分析： ##

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

--------------------

![20][]

![23][]  
![21][]

--------------------

## 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;
    }

[20]: /images/20220829/66749ffa6f7d48898492b46d53f71f6c.png
[23]: /images/20220829/a0be6ad66b634b71b177e3412f23e55b.png
[21]: /images/20220829/30f7f34710624aeb83f9aa47e883a5c4.png