走刀口

问题描述:

• 设有n(n = 2^k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天必须比赛一场，不能轮空。试按此要求为比赛安排日程。

编程思想:

假设n位选手被顺序编号为1,2,3,…,n，比赛的日程表是一个n行n-1列的表格，i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则，可从其中一半选手(2^(n-1位)的比赛日程，导出全体n位选手的日程，最终细分到只有两位选手的比赛日程出发。可假设只有8位选手参赛，若1至4号选手之间的比赛日程填在日程表的左上角(4行3列)，5至8号选手之间的比赛日程填在日程表的左下角(4行3列)；那么左下角的内容可由左上角的对应项加上数字4得到。至此，剩余的右上角(4行4列)是为编号小的1至4号选手与编号大的5至8号选手之间的比赛日程安排。例如，在第4天，让1至4号选手分别与5至8号选手比赛，以后各天，依次由前一天的日程安排，让5至8号选手“循环轮转”即可。最后，比赛日程表的右下角的比赛日程表可由，右上角的对应项减去数字4得到。

具体实现:

/**
 * @brief 循环赛日程安排，分治法
 *
 * @param[in] A 数组指针
 * @param[in] k 选手数幂，如2^k位选手
 */
void GameTable(int** A, int k)
{
	int n = 2;
	A[0][0] = 1;
	A[0][1] = 2;
	A[1][0] = 2;
	A[1][1] = 1;

	for (int t = 1; t < k; ++t)
	{
		int temp = n;
		n *= 2;

		int i = 0, j = 0;
		//左下角
		for (i = temp; i < n; ++i)
		{
			for (j = 0; j < temp; ++j)
			{
				A[i][j] = A[i - temp][j] + temp;
			}
		}

		//右上角
		for (i = 0; i < temp; ++i)
		{
			for (j = temp; j < n; ++j)
			{
				A[i][j] = A[i + temp][j - temp];
			}
		}

		//右下角
		for (i = temp; i < n; ++i)
		{
			for (j = temp; j < n; ++j)
			{
				A[i][j] = A[i - temp][j - temp];
			}
		}
	}
}
int main()
{
	float k = 3.0f;
	int personCount = pow(2.0f, k);
	int** A = new int*[personCount];
	for (int t = 0; t < personCount; ++t)
	{
		A[t] = new int[personCount];
	}
	GameTable(A, k);

	for (int i = 0; i < personCount; ++i)
	{
		for (int j = 0; j < personCount; ++j)
		{
			cout << A[i][j] << " ";
		}
		cout << endl;
	}
}

执行结果图: