2.8 赛程安排

2.8.1 问题描述

n(n=2k)个选手参赛，设计一个满足以下要求的比赛日程表：

  • 每个选手必须与其他n-1个选手各比赛一次；
  • 每个选手一天只能比赛一次；
  • 循环赛一共进行n-1天。

我们需要得出如下这样的的赛程表：
@图2.8 赛程表

2.8.2 算法思路

整体思路：由赛程表我们可以看出，赛程表分为四大区域，我们要做的是，

  • 将左上角的内容复制到右下角
  • 左上角的内容加上n/2得到左下角
  • 左下角复制到右上角

区域不断以2指数倍增大，并不断重复上述步骤，最终填满整张表。

2.8.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static int[][] getSchedule(int k) {
	int n=(int)Math.pow(2,k);
	int[][] table=new int[n][n];//建表
	table[0][0]=1;
	for(int i=1;i<=k;i++) {
		int newStartIndex=(int)Math.pow(2, i-1);
		int newLength=newStartIndex*2;
		/*核心代码*/
		matrixCopy(table,0,0,newStartIndex,newStartIndex,newLength/2);//左上角复制到右下角
		matrixCopyAdd(table,0,0,newStartIndex,0,newLength/2,newLength/2);//左上角复制并增加到左下角
		matrixCopy(table,newStartIndex,0,0,newStartIndex,newLength/2);//左下角复制到右上角
	}
	return table;	
}

///////////////////////////////////
//复制且增加
private static void matrixCopyAdd(int[][] table, int i_s, int j_s, int i_d, int j_d, int length, int add) {
	for(int i=0;i<length;i++) {
		for(int j=0;j<length;j++) {
			table[i_d+i][j_d+j]=table[i_s+i][j_s+j]+add;
		}
	}
}
//////////////////////////////////
//复制
private static void matrixCopy(int[][] table, int i_s, int j_s, int i_d, int j_d,  int length) {
	for(int i=0;i<length;i++) {
		for(int j=0;j<length;j++) {
			table[i_d+i][j_d+j]=table[i_s+i][j_s+j];
		}
	}
}