分治法循环赛日程表

算法分析与设计作业

 

 

 

 

 

 

 

 

 

姓名：蔡东赟

学号：3106007039

班级：06软件04班

组员：蔡东赟

完成日期：2009-3-22

 

分治法循环日程表... 1

算法分析与设计作业... 1

姓名：蔡东赟... 1

学号：3106007039. 1

班级：06软件04班... 1

组员：蔡东赟... 1

完成日期：2009-3-22. 1

目录：

一、问题描述：单循环赛... 3

二、算法分析：... 3

1.    首先我要证明老师提供的问题，有错误。... 3

2.    算法思路(N可能为奇数，也可能是偶数) 3

总体思路：按分治策略，将所有分为两半，n个选手可以通过n/2个选手设计的比赛日程表来决定。递归地用一分为二的略对选手进行分割，直到只剩下两个选手。... 3

存储结构：... 3

数组 a[i][j], a[i][j]表示运动员i在第j天所遇到的选手... 3

详细思路：... 4

（1）分治法，... 4

（2）n为偶数的情况Copy（）函数：A.将左上角递归计算出的小块的所有数字按其相对位置抄到右下角，B.将右上角的小块的所有数字加n/2后按其相对位置抄到左下角，将左下角的小块中的所有数字按其相对位置抄到右上角    4

（3）一般性描述：n为偶数; n是奇数时增加一个虚拟选手n+1，将问题转换为n是偶数的情形。    4

（4） 判断奇偶... 4

（5）makecopy（）与copy相似，并区分奇偶情况... 4

(6)copyodd(n)实现n/2为奇数的时候的复制... 4

三、时间效率：... 5

 

 

一、问题描述：单循环赛

•         赛程问题:    有N个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。

•         试用分治法为这N个运动员安排比赛日程。

•         要求每个运动员每天只进行一场比赛，

•         且整个赛程在N -1天内结束。

•         将运动员从1到N编号。

二、算法分析：

1.     首先我要证明老师提供的问题，有错误。

整个赛程，当N为偶数的时候，N-1天能够结束，

而当N为奇数的时候，只能在至少N天结束，、

错误地方：原命题中“整个赛程在N-1天结束”，这在N为奇数下的情况不成立

 A. 因为，由已知 “每个运动员要和所有其他运动员进行一次比赛”则 每个运动员总共进行N-1场，又由每一场有两个运动员参加，N个运动员就进行了[N*（N-1）]/2，设为C

   B.又因为已知“要求每个运动员每天只进行一场比赛”则没人每天只能进行1

场，所有运动员为N，每一场由两个运动员参加，

 当N为偶数的时候，每天只能出现的场数为N/2场,推出==》至少的天数为C/(N/2)=N-1场，这与命题中“且整个赛程在N -1天内结束。”不矛盾

 当N为奇数的时候，由于每个运动员每天只能进行一场，所以每天能进行的总场数最多只能为（N-1）/2场，则整个赛程的天数最少需要 天数 C/[(N-1)/2]=N天，这与原命题“且整个赛程在N -1天内结束。”矛盾，

比如N=3的时候，每场必须有两个人，则每天只能有一场比赛，假设是1和2比赛，则3号运动员没有对象比赛，所以一天最多一场比赛，这个比赛需要的比赛场数C=3场，则整个比赛需要的天数为C/1=3天

 

由此依照命题前部分要求得出，当N为偶数的情况 循环赛可以进行N-1天，当N为奇数的时候，循环赛至少要进行N天。

2.     算法思路(N可能为奇数，也可能是偶数)

总体思路：按分治策略，将所有分为两半，n个选手可以通过n/2个选手设计的比赛日程表来决定。递归地用一分为二的略对选手进行分割，直到只剩下两个选手。

对于N为奇数的情况可以虚拟多一个选手，使其编程N+1个选手的日程表，最然后忽略虚拟运动员参与的比赛。对于分割时候N/2的情况也做特殊处理, 前n/2轮比赛空选手与下一个未参赛的选手进行比赛

 

 

存储结构：

数组 a[i][j], a[i][j]表示运动员i在第j天所遇到的选手

 

 

详细思路：

（1）分治法，

    Tourna（n）：

If n==1  

       a[1][1]=1;return;

 

tourna(n/2);//递归分割

copy(n); //填表

 

（2）n为偶数的情况Copy（）函数：A.将左上角递归计算出的小块的所有数字按其相对位置抄到右下角，B.将右上角的小块的所有数字加n/2后按其相对位置抄到左下角，将左下角的小块中的所有数字按其相对位置抄到右上角

Viod copy(int n){

   Int m=n/2;

   For i=1àm

      For j=1--->m{

   a[i][j+m]=a[i][j]+m;// 小块的数值抄到右下角

   a[i+m][j]=a[i][j+m];// 右上抄到左下

   a[i+m][j+m]=a[i][j];//   左下抄到右上

}

        

}

----------------------------------------------------------------------------------------------------------------------

（3）一般性描述：n为偶数; n是奇数时增加一个虚拟选手n+1，将问题转换为n是偶数的情形。

   tournament（n）:

       if n==1 : a[1][1]=1;return;//分割到最后

       if n为奇数 ：tournament（n+1）;return;//奇数的情况加上虚拟选手

       tournament（n/2）;//分割

       makecopy(n);//这个函数copy分n为偶数很n为奇数的情况

（4） 判断奇偶

odd(n):

      Return n&1;

（5）makecopy（）与copy相似，并区分奇偶情况

     makecopy(n):

        if n/2>1 &&add(n/2) copyodd(n);//对n/2为奇数的情况的处理

        else copy(n);//偶数的情况

 (6)copyodd(n)实现n/2为奇数的时候的复制

    n/2奇数的一种处理方法：前n/2轮比赛空选手与下一个未参赛的选手进行比赛

 

 

    Copyodd(n):

       Int m=n/2

       For i=1→m

         b[i]=m+i;b[m+i]=b[i];

      

       for i=1→m

         for j=1→m+1{

            if a[i][j]>m:

                 a[i][j]=b[i];a[m+i][j]=(b[i]+m)%n;

            else

               a[m+i][j]=a[i][j]+m;

            for j=2→m

                a[i][m+j]=b[i+j-1];

                a[b[i+j-1]][m+j]=i

 

          }

三、时间效率：

 T(n)=T(n/2)+f(n)

 f(n)为copy的时间

f(n)=(n/2)^2

推出：T(n)=T(n/2)+(n/2)^2

N规模的问题做logN次f(n)

T(n)属于O（∑O((n/(2^k))^2)） 1<=k<log(n) 也就是T(n)∈O(n^2)

计算规模减少，但是时间复杂度一样增长