例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个硬币的情形。需要进行多少次重量的比较？
评论