【题目描述】

设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他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

【题目分析】

    以m=3（即 n=2^3=8）为例，可以根据问题要求，制定出如下表所示的一种方案∶

    以表格的中心为拆分点，将表格分成 A、B、C、D 四个部分，就很容易看出有 A=D，B= C，并且这一规律同样适用于各个更小的部分。

        设有n个选手的循环比赛，其中 n=2^m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行 n-1天。要求每天没有选手轮空，以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。

从八位选手的循环比赛表中可以看出，这是一个具有对称性的方阵，可以把方阵一分为四来看，那么左上角的 4×4 的方阵就是前四位选手的循环比赛表，而右上角的 4*4 的方阵就是后四位选手的循环比赛表，它们在本质上是一样的，都是4 个选手的循环比赛表，所不同的只是选手编号不同而已，将左上角中方阵的所有元素加上 4 就能得到右上角的方阵。下方的两个方阵表示前四位选手和后四位选手进行交义循环比赛的情况，同样具有对称性，将右上角方阵复制到左下角即得到1、2、3、4 四位选手和 5、6、7、8 四位选手的循环比赛表，根据对称性，右下角的方阵应与左上角的方阵相同。这样，八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来.同样地，四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来，而两名选手的循环比赛表可以说是已知的，这种程序设计方法叫做分治法，其基本思想是把一个规模为 n 的问题分成若干个规模较小的问题，使得从这些较小问题的解易于构造出整个问题的解。

程序中用数组 arr 记录 n 名选手的循环比赛表，整个循环比赛表从最初的 1*1的方阵按上述规则生成出2*2 的方阵，再生成出 4*4 的方阵，…，直到生成出整个循环比赛表为止。变量half表示当前方阵的大小，也是要生成的下—个方阵的大小的一半。

【参考代码】

#include<stdio.h>  int arr[1000][1000];  int m;  int main()  {  	int i,j,n,k=1,half=1;  	scanf("%d",&m);  	// 1<<m 相当于2^m  	n=1<<m;  	arr[0][0]=1;  	while(k<=m)       			//构造右上方方阵  	{  		for(i=0;i<half;i++)  			for(j=0;j<half;j++)  				arr[i][j+half]=arr[i][j]+half;  	  		for(i=0;i<half;i++)  		//对称交换构造下半部分方阵  			for(j=0;j<half;j++)  			{  				arr[i+half][j]=arr[i][j+half];   //左下方方降等于右上方方阵  				arr[i+half][j+half]=arr[i][j];     //右下方方降等于左上方方阵  			}  		half*=2;  		k++;  	}   	for(i=0;i<n;i++)  	{  		for(j=0;j<n;j++)  			printf("%d ",arr[i][j]);  		printf("\n");  	}  	return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});