例5 比赛安排（1996年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题）
设有2^n（n<=6）个球队进行单循环比赛，计划在2^n-1天内完成，每个队每天进行一场比赛，设计一个比赛安排，使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为：
|
队 |
1 |
2 |
3 |
4 |
时间 |
|
比赛 |
1 – 2 |
3 – 4 |
第一天 | ||
|
1 – 3 |
2 – 4 |
第二天 | |||
|
1 – 4 |
2 – 3 |
第三天 | |||
分析：已知参加比赛的球队数x(x=2^n)，要设计一个比赛安排表。分析题目要求（单循环比赛的比赛规则），我们可以归纳出比赛安排表必须满足的条件：
①球赛需要在x-1天内完成。
②每个球队每天有且只能有一场比赛。
③任意两个球队必须进行过一场比赛，并且只能进行一场比赛。
当只有两个球队进行比赛时，比赛安排表的设计非常简单，只要让两个球队直接进行一场比赛就可以了。当不止两个球队时，我们可以将所有的球队分成两半。x个球队的比赛安排表就可以通过x/2个球队的比赛安排表来产生。这样递归地使用这种一分为二的方法对球队进行分割，直到只剩下两个球队。
|
日期\球队 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
2 |
2 |
1 |
4 |
3 |
6 |
5 |
8 |
7 |
|
3 |
3 |
4 |
1 |
2 |
7 |
8 |
5 |
6 |
|
4 |
4 |
3 |
2 |
1 |
8 |
7 |
6 |
5 |
|
5 |
5 |
6 |
7 |
8 |
1 |
2 |
3 |
4 |
|
6 |
6 |
5 |
8 |
7 |
2 |
1 |
4 |
3 |
|
7 |
7 |
8 |
5 |
6 |
3 |
4 |
1 |
2 |
|
8 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
如图，是一张8个球队的比赛安排表。其中第i行与第j列相交的数字a(i,j)表示第j个球队在第i-1天所遇到的对手。（表的第一行为8个球队的编号）如果用a(i1..i2,j1..j2)表示表中从第i1行到第i2行与从第j1列到第j2列相交的部分，那么，这张8×8的表a(1..8,1..8)可以分成左上角a(1..4,1..4)、右上角a(1..4,5..8)、左下角a(5..8,1..4)和右下角a(5..8,5..8)四个部分。仔细分析这四个部分，我们会发现：右下角a(5..8,5..8)和左上角a(1..4,1..4)完全相同；左下角a(5..8,1..4)和右上角a(1..4,5..8)完全相同。再继续分析每一个部分，都具有同样的规律。比如左上角a(1..4,1..4)，我们又可以把它分成a(1..2,1..2)、a(1..2,3..4)、a(3..4,1..2)和a(3..4,3..4)四个部分，并且a(3..4,3..4)和a(1..2,1..2)完全相同， a(3..4,1..2)和a(1..2,3..4)完全相同。
根据上面分析出来的规律，使用分治算法的思想，我们要设计一张8×8的比赛安排表a(1..8,1..8)，只需要设计出表的上半部分，即两张4×4的安排表a(1..4,1..4)和a(1..4,5..8)即可。之后，通过已经设计出来的表的左上角a(1..4,1..4)复制出表的右下角a(5..8,5..8)，通过右上角a(1..4,5..8)复制出表的左下角a(5..8,1..4)。即一张8×8的比赛安排表a(1..8,1..8)，可以通过两张4×4的比赛安排表a(1..4,1..4)和a(1..4,5..8)产生。同样，4×4的比赛安排表a(1..4,1..4)，可以通过两张2×2的比赛安排表a(1..2,1..2)和a(1..2,3..4)产生；a(1..4,5..8)可以通过a(1..2,5..6)和a(1..2,7..8)产生。
分解到最后，a(1,1)、a(1,2)、……、a(1,8)都是单独的一个数字，分别为8个球队的编号1、2、……、8，即这张8×8的比赛安排表的第一行。
如何将a(1,1)、a(1,2)、……、a(1,8)这8个数字合并成一张完整的比赛安排表（原问题的解）呢？我们可以将整个合并过程分成三个阶段：
第一阶段，将这8个已知的数字（可以看成8张1×1的比赛安排表）合并成4张2×2的比赛安排表。这一阶段需要进行4次合并操作：①将a(1,1)和a(1,2)合并成a(1..2,1..2)；②将a(1,3)和a(1,4)合并成a(1..2,3..4)；③将a(1,5)和a(1,6)合并成a(1..2,5..6)；④将a(1,7)和a(1,8)合并成a(1..2,7..8)。这一阶段产生表的前两行。
第二阶段，将表的第一二行（可以看成4张2×2的比赛安排表）合并成两张4×4的比赛安排表。这一阶段需要进行两次合并操作：①将a(1..2,1..2)和a(1..2,3..4)合并成a(1..4,1..4)；②将a(1..2,5..6)和a(1..2,7..8)合并成a(1..4,5..8)。这一阶段产生表的前四行。
第三阶段，将表的前四行（可以看成2张4×4的比赛安排表）合并成一张8×8的比赛安排表。这一阶段只需要进行一次合并操作：将a(1..4,1..4)和a(1..4,5..8)合并成a(1..8,1..8)。这一阶段将产生一张完整的比赛安排表。
#include<stdio.h>
#define MAX 64
void Arrange(int a[][MAX], int n, int left, int right);
int main()
{
int a[MAX][MAX] = {0};
int i, j, n = 8;
for (i=0; i<n; ++i)//先确定第1行：球队的编号
a[0][i] = i + 1;
Arrange(a, n, 0, n-1);//递归产生各个方阵
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
printf("%3d", a[i][j]);
printf("\n");
}
getchar();
return 0;
}
/*
函数功能：比赛安排，为n（=2^k）个球队安排比赛，使在n-1天内每个队都与不同的对手比赛
输入变量： int a[][MAX]， 数组a中存储各球队的比赛情况
int n, 球队的数量，也即方阵的大小
int left, 数组a的左边界
int right, 数组a的右边界
输出变量：int a[][MAX]， 数组a中存储各球队的比赛情况
返回值： 无
*/
void Arrange(int a[][MAX], int n, int left, int right)//递归产生各个方阵
{
if (n < 2)//球队数量少于2，不做任何操作
return;
int i, j;
int mid = (left+right)/2;//把方阵分成两半
n /= 2;
Arrange(a, n, left, mid);//递归处理左上角方阵
Arrange(a, n, mid+1, right);//递归处理右上角方阵
for (i=0; i<n; i++)
{
for (j=left; j<=mid; j++)//已经得到方阵的左上角，则由左上角推出右下角
{
a[i+n][j+n] = a[i][j];
}
for (j=mid+1; j<=right; j++)//已经得到方阵的右上角，则由右上角推出左下角
{
a[i+n][j-n] = a[i][j];
}
}
}
也可以写成非递归的方式：
/*
函数功能：比赛安排，为n（=2^k）个球队安排比赛，使在n-1天内每个队都与不同的对手比赛
输入变量： int a[][MAX]， 数组a中存储各球队的比赛情况
int max, 球队的数量，也即方阵的大小
输出变量：int a[][MAX]， 数组a中存储各球队的比赛情况
返回值： 无
*/
void Arrange(int a[][MAX], int max)
{
int i, j, k, n, left, right, mid;
for (i=0; i<max; ++i)//先确定第1行：球队的编号
a[0][i] = i + 1;
for (n=2; n<=max; n*=2)//依次安排2，4，8。。。个球队
{
for (left=0; left<max-1; left+=n)//当前被安排的球队的左边界
{
right = left + n - 1;//当前被安排的球队的右边界
mid = (left + right) / 2;
k = n / 2;//将球队分成左右两半处理，每半有k个球队
for (i=0; i<k; i++)
{
for (j=left; j<=mid; j++)//由左上角推出右下角
{
a[i+k][j+k] = a[i][j];
}
for (j=mid+1; j<=right; j++)//由右上角推出左下角
{
a[i+k][j-k] = a[i][j];
}
}
}
}
}
练习
1． 计算x的N次方(N>=0)。
2．元三次方程求解(noip2001tg)
问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数
(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，
且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后5位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*(x2)<0，则在(x1，x2)之间一定有一个根。
样例
输入：1 -5 -4 20
输出：-2.00 2.00 5.00
3．例4的分而治之算法扩充到n> 1个硬币的情形。需要进行多少次重量的比较？
评论