循环日程赛问题

循环日程赛是利用分治法解决的经典问题之一。

问题描述

设有n = 2^k 个选手参加比赛，要求设计一个日程赛安排表，满足：

1. 每个选手都与其他n-1个选手各自比赛一次；
2. 每个选手每天只比赛一次；
3. 比赛进行n-1天。

设计分析

设计日程赛安排表可以用一个n行n-1列的二维数组来表示，a[i][j]即表示第i个选手在第j天遇到的对手。

要想利用分治法解决该问题，就必须将整个问题进行划分，划分成容易解决的子问题进行求解。按照分治法的思想，我们可以将n个选手一分为二，计算n/2个选手日程赛的情况，继续划分，直至两个选手时，此时为最简单的情况，以此解决n个选手的情况。

当n=2时，2个选手，此情况下最为简单：

当n=4时，4个选手，我们先用穷举的方法得到结果：

我们可以看出填表的规律：

1. 表的左上子表等于表的右下子表，左下子表等于右上子表；
2. 左下子表的元素等于左上角子表对应元素加2^k-1;
3. 左上子表对应的是前2^k-1个选手的比赛前半程的比赛日程;左下角子表是后2^k-1个选手的比赛前半程比赛日程。

根据这个规律我们再来验证n=8的情况：

可以看出此规律是正确的。

因此在编写程序进行填表时我们就通过分治法的思想，进行划分，首先填写2⁰个选手的情况，再根据规律填写2¹、2²……2ⁿ的情况。

源代码

#include<iostream>
#include<vector>
using namespace std;

//非递归
void Arrange(vector<vector<int> > &a) {
	if (a.size() == 0)
		return;
	a[0][0] = 1;			//初始化
	int row = a.size();     //总行数
	for (int i = 1; (0x1 << i) <= row ; i++) {
		int length = (0x1 << i);  //当前需要填充的小矩阵的行数
		int s = length / 2;

		//左下角
		for (int j = 0; j < s; j++) {
			for (int k = 0; k < s; k++) {
				a[j + s][k] = a[j][k] + s;
			}
		}

		//右上角
		for (int j = s; j < length; j++) {
			for (int k = 0; k < s; k++) {
				a[k][j] = a[j][k];
			}
		}

		//右下角
		for (int j = 0; j < s; j++) {
			for (int k = 0; k < s; k++) {
				a[j + s][k + s] = a[j][k];
			}
		}
	}
}

//递归
void copy(vector<vector<int> > &a,int n) {
	int m, i, j;
	m = n / 2;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j + m] = a[i][j] + m;	//左下角
			a[i + m][j] = a[i][j] + m;	//右上角
			a[i + m][j + m] = a[i][j];	//右下角
		}
	}
}

void tournament(vector<vector<int> > &a,int n) {
	if (n == 1) {
		a[0][0] = 1;
		return;
	}
	tournament(a, n / 2);
	copy(a,n);
}

int main() {
	int n;
	cout << "输入比赛人数：（人数必须为2^k倍）";
	cin >> n;
	vector<vector<int> > a(n, vector<int>(n));	//日程赛数组
	tournament(a, n);	//递归分治法
	Arrange(a);		//非递归循环法

	cout << "\t";
	for (int i = 0; i < n-1; i++)
		cout<< "第" << i + 1 << "天" << "\t";
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j == 0)
				cout << "选手" << i + 1 << ":" << "\t";
			else
				cout << a[i][j] << "\t";
		}
		cout << endl;
	}


	system("pause");
	return 0;
}

运行结果

将输出结果改进得更可视化、一目了然；