我要啦免费统计

 

 

 

 

分治法循环赛日程表

算法分析与设计作业

 

 

 

 

 

 

 

 

 

姓名:蔡东赟

学号: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

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

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

4 判断奇偶... 4

5makecopy()与copy相似,并区分奇偶情况... 4

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

三、时间效率:... 5

 


 

一、问题描述:单循环赛

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

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

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

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

         将运动员从1N编号。

二、算法分析:

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的时候,每场必须有两个人,则每天只能有一场比赛,假设是12比赛,则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)分治法,

    Tournan):

If n==1  

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

 

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

copy(n); //填表

 

2n为偶数的情况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是偶数的情形。

   tournamentn:

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

       if n为奇数 tournamentn+1;return;//奇数的情况加上虚拟选手

       tournamentn/2;//分割

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

4 判断奇偶

odd(n):

      Return n&1;

5makecopy()与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=1m

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

      

       for i=1m

         for j=1m+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=2m

                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规模的问题做logNf(n)

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

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

posted on 2009-04-01 15:21 阅读(7850) 评论(0)  编辑 收藏 引用 所属分类: 作业算法相关杂项

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理