主要内容 #
- 问题描述
- 算法分析
- 参考程序
1. 问题描述 #
设有N个选手进行循环比赛,其中N=2^M,要求每名选手要与其他N-1名选手都赛一次,每名选手每天比赛一次,循环赛共进行N-1天,要求每天没有选手轮空。
输入:M
输出:表格形式的比赛安排表
样例输入
3
样例输出
第一行为八名选手的编号,下面七行依次是每位选手每天的对手。
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
2. 算法分析 #
以m = 3(n = 8)为例,可以根据问题要求制定出如下表的一种方案:
以表格的中心为拆分点,将表格分为A、B、C、D四个部分,就很容易看出有A = D, B = C,并且同样的规律适用于各个更细小的部分。
从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四看,左上角4*4的方阵就是前四位选手的循环比赛表,而右上角的4*4的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,将左上角所有的元素加上4就能得到右上角的方阵。
下方的的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况,同样具有对称性,将右上角方阵复制到左下角即得到1、2、3、4四位选手和5、6、7、8四位选手的循环比赛表,根据对称性,右下角的方阵应与左上角的方阵相同。这样,八名选手的循环比赛表可以由四名选手的循环比赛表得到。同样地,四名选手的循环比赛表可以由两名选手的循环比赛表根据对称性生成出来,而两名选手的循环比赛表是已知的。
程序中用数组matchlist记录n名选手的循环比赛表,整个循环比赛表从最初的1*1方阵按照上述规则生成出2*2的方阵,再生成出4*4的方阵,···直到生成出整个循环比赛表为止,变量half表示当前方阵的大小,也就是要生成的下一个方阵大小的一半。
3. 参考程序 #
#include <iostream> using namespace std; const int MAXN=1025,MAXM=11; int marchlist[MAXN][MAXN]; int m; int main(){ printf("Input m:"); scanf("%d",&m); int n=1<<m,k=1,half=1; // 1<<m 相当于2^m marchlist[0][0]=1; while(k<=m){ for(int i=0;i<half;i++){ //构造右上方方阵 for(int j=0;j<half;j++){ marchlist[i][j+half]=marchlist[i][j]+half; } } for(int i=0;i<half;i++){ //对称交换构造下半部分方阵 for(int j=0;j<half;j++){ marchlist[i+half][j]=marchlist[i][j+half]; //左下方方阵等于右上方方阵 marchlist[i+half][j+half]=marchlist[i][j]; //右下方方阵等于左上方方阵 } } half*=2; k++; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ printf("%4d",marchlist[i][j]); } printf("\n"); } return 0; }