比赛日程安排.doc

摘要:对于单循环赛的比赛日程安排问题,利用分治算法给出了可读性较好的设计,并详细分析了各种假设下的时间复杂度。/8/view- 关键词:分治算法;复杂度;递归;循环赛中图分类号::A 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。分治法是计算机科学中经常使用的一种算法。设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。但是不是所有问题都适合用分治法解决。当求解一个输入规模为n且取值又相当大的问题时,使用蛮力策略效率一般得不到保证。 1分治法应用条件及一般步骤 ,就可以考虑用分治法来提高解决问题的效率。(1)能将这n个数据分解成k个不同子集合,且得到的k个子集合是可以独立求解的子问题,其中1<k<=n; (2)分解所得到的子问题与原问题具有相似的结构,便于利用递归或循环机制; (3)合并各个子问题的解,就是原问题的解。 : (10分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题; (2)求解子问题:若子问题规模较小而容易被解决则直接解,否则再继续分解为更小的子问题,直到容易解决; (3)合并:将已求解的各个子问题的解,合并为原问题的解。需要注意的是,不是所有的分治法都比简单的蛮力法更有效。 2循环赛分治算法下面,我们应用分治法解决循环赛日程表的设计问题。 ,设计一个满足下面要求的比赛日程表: (1)每支球队必须与其他n-1支球队各赛一次; (2)每支球队一天只能比赛一次; (3)当n为偶数时,比赛进行n-1天;当n为奇数时,比赛进行n天。按此要求,可将比赛日程表设计成一个n行n列的二维表。 =2k(k=1、2、3、4,……,n=2、4、8、16,……)时,此时问题比较简单。按照分治的策略,可将所有参赛的选手分为两部分,n=2k个选手的比赛日程表就可以通过为n/2=2k-1个选手设计的比赛日程表来决定。递归地执行这种分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单:只要让这2个选手进行比赛就可以了。再逐步合并子问题的解即可得到原问题的解。算法如下: voidtourna(intn)//基本的分治算法{ if(n==1){a[0][0]=1;return;} tourna(n/2);//分治 copy(n);//合并} voidcopy(intn) { intm=n/2; for(inti=0;i<m;i++) for(intj=0;j<m;j++) { //由左上角小块的值算出对应的右上角小块的值 a[i][j+m]=a[i][j]+m; //由右上角小块的值算出对应的左下角小块的值 a[i+m][j]=a[i][j+m]; //由左上角小块的值算出对应的右下角小块的值 a[i+m][j+m]=a[i][j]; } } 分析算法的时间性能,迭代处理的循环体内部有2个循环语句,基本语句是最内层循环体的赋值语句,即填写比赛日程表中的元素。基本语句的执行次数是:T(n)=T(n)3-0(4), 所以算法的时间复杂度为0(4)。下