循环赛日程安排问题（分治法）

循环赛日程安排问题（分治法）

问题描写叙述:

设有n(n=2^k)支队伍參加循环赛，循环赛共进行n-1天，每支队伍要与其它n-1支队伍比赛一场，
且每支队伍每天必须比赛一场，不能轮空。试按此要求为比赛安排日程。

算法思路:

   我们先安排奇数下标位置与偶数下标位置之间的比赛，就有n/2场,方法非常easy，
   team[2k]=2k,全部奇数号组成一个序列[1,3...n-1]，
   然后循环移动n/2-1次（比方第2个序列就是[3,5...n-1,1]），
   然后将该序列填充在team的奇数位置上。

   接下来将队伍一分为二，奇数为一组，偶数为一组，
   分配安排其内部比赛（由于奇偶数之间前面已经安排过了啦）。
   以奇数组[1,3,5,7]为例(以n=8为例说明），
   我们仍然先安排奇数下标位置与偶数下标位置之间的比赛，
   也就是[15]与[37]之间的比赛，共同拥有2场(n/4)。

   接下来，再将队伍一分为二，得到[15],[37],[04],[26]，
   对每一部分，仍然是先安排奇数下标位置与偶数下标位置之间的比赛，共1场(n/8)。
   此时已不可再分出子队伍，计算结束。

对照赛安排编号：

从前文的分析能够看出，我们产生比赛日程安排是有规律可循，
先产生n/2，然后是n/4,...直到最后1场。因为n=2^k,
那么这些安排场次总数为2^(k-1)+2^(k-2)...+1=2^k-1=n-1，
恰好相符（其实是必定的）。

这样，对于给定一个编号id，我们首先能够判定相应场次安排须要进行几次队伍分裂。
方法非常easy，比如n=8，id=6，因为一次分烈得到n/2=4场，再次分裂可得n/4=2场，于是两次分裂就可以。
同一时候id-4=2，也就是说两次分裂后的第2个赛场安排，这个2用于对子队伍移位计算使用。

图示

代码

#include
#include
#include
#include
#include
using namespace std;

string transform(int num)
{
	bool add = false;
	if (num < 10) {
		add = true;
	}
	stack temp_stack;
	int temp_num;
	while (num != 0)
	{
		temp_num = num % 10;
		num /= 10;
		char temp_char = '0' + temp_num;
		temp_stack.push(temp_char);
	}
	string str;
	if (add) {
		str += '0';
	}
	while (!temp_stack.empty())
	{
		str += temp_stack.top();
		temp_stack.pop();
	}
	return str;
}

void game(vector arr, int day, vector> &result)
{
	int len = arr.size() / 2;
	for (int i = 0; i < len; i++)
	{
		for (int k = 0; k < 2 * len; k += 2)
		{
			string str;
			str += transform(arr[k]);
			str += "--";
			str += transform(arr[k + 1]);
  			result[day + i].emplace_back(str);
		}
		if (i == len - 1){
			break;
		}
		int rear = arr[0];
		for (int j = 0; j < arr.size() - 2; j += 2)
		{
			arr[j] = arr[j + 2];
		}
		arr[arr.size() - 2] = rear;
	}
	
	if (len == 1){
		return;
	}

	vector left(len), right(len);
	for (int i = 0; i < len; i++)
	{
		left[i] = arr[2 * i];
		right[i] = arr[2 * i + 1];
	}
	day += len;
	game(left, day, result);
	game(right, day, result);
}

void print(vector> &result)
{
	cout<<"循环赛日程安排为："<>k;
	int sum = (int) pow((double) 2, (double) k);
	vector arr(sum);
	for (int i = 0; i < sum; i++)
	{
		arr[i] = i + 1;
	}
	vector> result(sum - 1);
	game(arr, 0, result);
	print(result);
	return 0;
}

//输入案例
//4

博文参考链接