比赛日程安排.doc

摘要:对于单循环赛的比赛日程安排问题,利用分治算法给出了可读性较好的设计,并详细分析了各种假设下的时间复杂度。
中国论文网/8/view-
关键词:分治算法;复杂度;递归;循环赛
中图分类号::A
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。分治法是计算机科学中经常使用的一种算法。设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。但是不是所有问题都适合用分治法解决。当求解一个输入规模为n且取值又相当大的问题时,使用蛮力策略效率一般得不到保证。

1 分治法应用条件及一般步骤


若问题能满足以下所列条件,就可以考虑用分治法来提高解决问题的效率。
(1)能将这n个数据分解成k个不同子集合,且得到的k个子集合是可以独立求解的子问题,其中1<k<=n;
(2)分解所得到的子问题与原问题具有相似的结构,便于利用递归或循环机制;
(3)合并各个子问题的解,就是原问题的解。

采用分治算法解决问题的基本步骤为:
(10分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
(2)求解子问题:若子问题规模较小而容易被解决则直接解,否则再继续分解为更小的子问题,直到容易解决;
(3)合并:将已求解的各个子问题的解,合并为原问题的解。
需要注意的是,不是所有的分治法都比简单的蛮力法更有效。

2 循环赛分治算法

下面,我们应用分治法解决循环赛日程表的设计问题。

有n支球队参加循环赛,设计一个满足下面要求的比赛日程表:
(1)每支球队必须与其他n-1支球队各赛一次;
(2)每支球队一天只能比赛一次;
(3)当n为偶数时,比赛进行n-1天;当n为奇数时,比赛进行n天。
按此要求,可将比赛日程表设计成一个n行n列的二维表。

当n=2k(k=1、2、3、4,……,n=2、4、8、16,……)时,此时问题比较简单。按照分治的策略,可将所有参赛的选手分为两部分,n=2k个选手的比赛日程表就可以通过为n/2=2k-1个选手设计的比赛日程表来决定。递归地执行这种分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单:只要让这2个选手进行比赛就可以了。再逐步合并子问题的解即可得到原问题的解。
算法如下:
void tourna(int n)//基本的分治算法
{
if(n==1){a[0][0]=1;return;}
tourna(n/2);//分治
copy(n); //合并
}
void copy(int n)
{
int 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];
//由