精华内容
下载资源
问答
  • 循环赛日程安排问题

    2021-03-09 17:34:07
    //team:比赛安排结构,team[2k]vsteam[2k+1]//len:team的总数//id:第id轮的安排,id的范围[1,len-1]voidgame(int*team,intlen,intid){intbase=2;while(id>len/base){id-=len/base;base<<=1;}for(inti=0;iin...

    // team: 比赛安排结构,team[2k] vs team[2k+1]

    // len:  team的总数

    // id:   第id轮的安排,id的范围[1, len-1]

    voidgame(int*team,intlen,intid){

    intbase= 2;

    while(id > len/base){

    id -= len/base;

    base<<= 1;

    }

    for(inti=0; i

    intstart = i+base/2+(id-1)*base;

    for(intj=0; j

    team[i*2*len/base+2*j] =base*j+i;

    team[i*2*len/base+2*j+1] = (start+base*j)%len;

    }

    }

    }

    // 以下是測试部分

    voiddump(int*arr,intlen){

    for(inti=0; i

    printf("%02d-%02d ", arr[i], arr[i+1]);

    printf("/n");

    }

    intmain(){

    constintlen = 16;

    intteam[len];

    for(inti=1; i

    game(team, len, i);

    printf("[%02d] ", i);

    dump(team, len);

    }

    return0;

    }

    输出结果:

    [01] 00-01 02-03 04-05 06-07 08-09 10-11 12-13 14-15

    [02] 00-03 02-05 04-07 06-09 08-11 10-13 12-15 14-01

    [03] 00-05 02-07 04-09 06-11 08-13 10-15 12-01 14-03

    [04] 00-07 02-09 04-11 06-13 08-15 10-01 12-03 14-05

    [05] 00-09 02-11 04-13 06-15 08-01 10-03 12-05 14-07

    [06] 00-11 02-13 04-15 06-01 08-03 10-05 12-07 14-09

    [07] 00-13 02-15 04-01 06-03 08-05 10-07 12-09 14-11

    [08] 00-15 02-01 04-03 06-05 08-07 10-09 12-11 14-13

    [09] 00-02 04-06 08-10 12-14 01-03 05-07 09-11 13-15

    [10] 00-06 04-10 08-14 12-02 01-07 05-11 09-15 13-03

    [11] 00-10 04-14 08-02 12-06 01-11 05-15 09-03 13-07

    [12] 00-14 04-02 08-06 12-10 01-15 05-03 09-07 13-11

    [13] 00-04 08-12 01-05 09-13 02-06 10-14 03-07 11-15

    [14] 00-12 08-04 01-13 09-05 02-14 10-06 03-15 11-07

    [15] 00-08 01-09 02-10 03-11 04-12 05-13 06-14 07-15

    展开全文
  • 算法(c++)——循环比赛日程安排问题 :设有n(n=2^k)支队伍參加循环赛循环赛共进行n-1天,每支队伍要与其它n-1支队伍比赛一场,且每支队伍每天必须比赛一场,不能轮空。试按此要求为比赛安排日程。运用分治递归法...

    目录

    一、问题描述

    二、解题思路

    三、代码

    四、结果

    五、总结

    六、完整程序代码包

    ShiYan_1_XunHuanBiSaiRiChengAnPai.rar-讲义文档类资源-CSDN下载算法(c++)——循环比赛日程安排问题更多下载资源、学习资料请访问CSDN下载频道.https://download.csdn.net/download/lcf0000/55674158


    一、问题描述

            循环比赛日程安排问题:设有n(n=2^k)支队伍參加循环赛,循环赛共进行n-1天,每支队伍要与其它n-1支队伍比赛一场,且每支队伍每天必须比赛一场,不能轮空。试按此要求为比赛安排日程。运用分治递归法解决该问题。

    二、解题思路

            首先安排奇数下标位置与偶数下标位置之间的比赛,就有n/2,team[2k]=2k,全部奇数号组成一个序列[1,3...n-1],然后循环移动n/2-1次(比方第2个序列就是[3,5...n-1,1]),然后将该序列填充在team的奇数位置上。

            接下来将队伍一分为二,奇数为一组,偶数为一组,分配安排其内部比赛(由于奇偶数之间前面已经安排过了啦)。以奇数组[1,3,5,7]为例(n=8为例说明),我们仍然先安排奇数下标位置与偶数下标位置之间的比赛,也就是[15][37]之间的比赛,共同拥有2(n/4)

            接下来,再将队伍一分为二,得到[15],[37],[04],[26],对每一部分,仍然是先安排奇数下标位置与偶数下标位置之间的比赛,共1(n/8)。此时已不可再分出子队伍,计算结束。

    三、代码

    #include <iostream>
    #include <stdio.h>
    #include <math.h>
    
    using namespace std;
    
    // team: 比赛安排结构,team[2j] vs team[2j+1]
    // n:  team的总数,n = 2^k
    // id:   第id轮的安排,id的范围[1, n-1]
    void game(int *team, int n, int id){
        int base = 2;
        while (id > n/base){
            id -= n/base;
            base <<= 1;
        }
        for (int i=0; i<base/2; ++i){
            int start = i+base/2+(id-1)*base;
            for (int j=0; j<n/base; ++j){
                team[i*2*n/base+2*j] = base*j+i;
                team[i*2*n/base+2*j+1] = (start+base*j)%n;
            }
        }
    }
    
    void dump(int *arr, int n){//输出每天比赛安排
        for (int i=0; i<n; i+=2)
            printf("%02d-%02d ", arr[i], arr[i+1]);
        printf("\n");
    }
    int main(){
        int k;
        printf("请输入k的值:")
        scanf("%d",&k);
        const int n = pow(2, k);
        int team[n];
        for (int i=1; i<n; ++i){
            game(team, n, i);
            printf("[%02d] ", i);
            dump(team, n);
        }
        return 0;
    }
    

    四、结果

            结果说明:第一行,输入k的值为4,意味着队伍总数n=2k;接下来的部分为每天的赛程安排,以第一行为例,[01]表示第一天,其后边的形如“00-01”的表示00号队伍与01号队伍比赛,以此类推,最终结果正确。

    五、总结

    1、分治的全称称为“分而治之”,分治即是将大问题划分为若干个规模较小、可以直接解决的子问题,然后解决这些子问题,最后将这些子问题的解合并起来,即是原问题的解。

    2、分治的步骤

            分治法的目的就是为了把无法解决的大问题分解成若干个能够解决小问题。通常来说,分治法可以归纳为三个步骤:

    (1)分解,将原问题分解成若干个与原问题结构相同但规模较小的子问题;

    2)解决,解决这些子问题。如果子问题规模足够小,直接求解,否则递归地求解每个子问题;

    3)合并,将这些子问题的解合并起来,形成原问题的解。

    3、对于本次实验问题:设有n=2^k个选手参加循环赛,要求设计一个满足以下要求比赛日程表:

    1)每个选手必须与其它n-1个选手各赛一次;

    2)每个选手一天只能赛一次。

            按照上面的要求,可以将比赛表设计成一个n行n-1列的二维表,其中第i行第j列的元素表示和第i个选手在第j天比赛的选手号。

            采用分治策略,可将所有参加比赛的选手分成两部分,n=2^k个选手的比赛日程表就可以通过n=2^k-1)个选手的的比赛日程表来决定。递归的执行这样的分割,直到只剩下两个选手,比赛日程表的就可以通过这样的分治策略逐步构建。

    六、完整程序代码包

    ShiYan_1_XunHuanBiSaiRiChengAnPai.rar-讲义文档类资源-CSDN下载算法(c++)——循环比赛日程安排问题更多下载资源、学习资料请访问CSDN下载频道.https://download.csdn.net/download/lcf0000/55674158

    展开全文
  • 问题描述:设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:(1)每个选手必须与其他n-1个选手各赛一次;(2)每个选手一天只能赛一次。按此要求,可将比赛日程表设计成一个 n 行n-1列的二维表...

    问题描述:

    设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:

    (1)每个选手必须与其他n-1个选手各赛一次;

    (2)每个选手一天只能赛一次。

    按此要求,可将比赛日程表设计成一个 n 行n-1列的二维表,其中,第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。

    算法分析:

    假设n位选手被顺序编号为1,2,3,…,n,比赛的日程表是一个n行n-1列的表格,i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则,可从其中一半选手(2^(n-1位)的比赛日程,导出全体n位选手的日程,最终细分到只有两位选手的比赛日程出发。

    可假设只有8位选手参赛,若1至4号选手之间的比赛日程填在日程表的左上角(4行3列),5至8号选手之间的比赛日程填在日程表的左下角(4行3列);那么左下角的内容可由左上角的对应项加上数字4得到。至此,剩余的右上角(4行4列)是为编号小的1至4号选手与编号大的5至8号选手之间的比赛日程安排。例如,在第4天,让1至4号选手分别与5至8号选手比赛,以后各天,依次由前一天的日程安排,让5至8号选手“循环轮转”即可。最后,比赛日程表的右下角的比赛日程表可由,右上角的对应项减去数字4得到。

    编程图例:

    ===================================================================

    |*| 选手    1天        2天        3天        4天        5天        6天        7天    |*|

    ===================================================================

    |*|    1号    |    2    |    3    |    4    ||    5    |    6    |    7    |    8    |*|

    |*|    2号    |    1    |    4    |    3    ||    6    |    7    |    8    |    7    |*|

    |*|    3号    |    4    |    1    |    2    ||    7    |    8    |    5    |    6    |*|

    |*|    4号    |    3    |    2    |    1    ||    8    |    5    |    6    |    5    |*|

    ========[左上角]========================[右上角]===================

    |*|    5号    |    6    |    7    |    8    ||    1    |    4    |    3    |    2    |*|

    |*|    6号    |    5    |    8    |    7    ||    2    |    1    |    4    |    3    |*|

    |*|    7号    |    8    |    5    |    6    ||    3    |    2    |    1    |    4    |*|

    |*|    8号    |    7    |    6    |    5    ||    4    |    3    |    2    |    1    |*|

    ========[左下角]========================[右下角]===================

    程序代码(C语言):

    #include

    #include

    int calendar[100][100];  //日程表数组

    void game(int k)

    {

    int p,q,m,number,i,j;

    number=k;

    p=m=1;

    calendar[1][1]=2;

    calendar[2][1]=1;

    while(m

    {

    ++m;

    p=2*p;

    q=2*p;

    //填充日程表的左下角

    for(i=p+1;i

    for(j=1;j

    calendar[i][j]=calendar[i-p][j]+p;

    //填充日程表的右上角

    calendar[1][p]=p+1;

    for(i=2;i<=p;++i)

    calendar[i][p]=calendar[i-1][p]+1;

    for(j=p+1;j

    {

    for(i=1;i

    calendar[i][j]=calendar[i+1][j-1];

    calendar[p][j]=calendar[1][j-1];

    }

    //填充日程表的右下角

    for(j=p;j

    for(i=1;i<=p;++i)

    calendar[calendar[i][j]][j]=i;

    }

    }

    int main()

    {

    int i,j,number,flag,k;

    printf(“请输入参赛人数:(必须是2的k次幂) “);

    scanf(“%d”,&number);

    flag=1;

    k=0;

    while(flag!=number){

    k++;

    flag*=2;

    }

    game(k);

    //输出二维表

    for(i = 1;i <= 8;i++)

    {

    for(j = 1;j < 8;j++)

    printf(“%4d”,calendar[i][j]);

    printf(“\n”);

    }

    printf(” “);

    system(“pause”);

    return 0;

    }

    展开全文
  • 一、问题背景设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:①每个选手必须与其他n-1个选手各赛一次;②每个选手一天只能赛一次。二、问题分析按此要求,可将比赛日程表设计成一个n×(n-1...

    一、问题背景

    设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:

    ①每个选手必须与其他n-1个选手各赛一次;

    ②每个选手一天只能赛一次。

    二、问题分析

    按此要求,可将比赛日程表设计成一个n×(n-1)的二维表,其中,(i, j)表示和第i个选手在第j天比赛的选手。

    •将所有参赛的选手分为两部分

    n=2^k个选手的比赛日程表就可以通过为n/2=2^(k-1)个选手设计的比赛日程表来决定。

    •递归地执行这种分割

    •直到只剩下2个选手(递归出口)比赛日程表的制定就变得足够简单

    只要让这2个选手进行比赛即可

    •求解过程是自底向上的迭代过程,其中图(c)左上角和左下角分别为选手1至选手4以及选手5至选手8前3天的比赛日程

    •将左上角部分的所有数字按其对应位置抄到右下角,将左下角的所有数字按其对应位置抄到右上角,这样,就分别安排好了选手1至选手4以及选手5至选手8在后4天的比赛日程,如图(c)所示。具有多个选手的情况可以依此类推。

    •把求解2k个选手比赛日程问题划分成依次求解21、22、…、2k个选手的比赛日程问题,换言之,2k个选手的比赛日程是在2^(k-1)个选手的比赛日程的基础上通过迭代的方法求得的。

    •在每次迭代中,将问题划分为4部分:

    ①左上角

    •左上角为2^(k-1)个选手在前半程的比赛日程;

    ②左下角

    •左下角为另2^(k-1)个选手在前半程的比赛日程,由左上角加2^(k-1)得到,例如22个选手比赛,左下角由左上角直接加2得到,23个选手比赛,左下角由左上角直接加4得到;

    ③右上角

    •将左下角直接抄到右上角得到另2^(k-1)个选手在后半程的比赛日程;

    ④右下角

    •将左上角直接抄到右下角得到2^(k-1)个选手在后半程的比赛日程;算法设计的关键在于寻找这4部分元素之间的对应关系

    三、算法描述

    void GameTable(int k, int a[ ][ ])

    {

    // n=2k(k≥1)个选手参加比赛,//二维数组a表示日程安排,数组下标从1开始n=2; //k=0,2个选手比赛日程可直接求得//求解2个选手比赛日程,得到左上角元素a[1][1]=1; a[1][2]=2;

    a[2][1]=2; a[2][2]=1;

    for (t=1; t

    //迭代处理,依次处理22, …, 2k个选手比赛日程 temp=n; n=n*2;

    //填左下角元素 for (i=temp+1; i<=n; i++ )

    for (j=1; j<=temp; j++)

    a[i][j]=a[i-temp][j]+temp;

    //左下角元素和左上角元素的对应关系 //填右上角元素 for (i=1; i<=temp; i++)

    for (j=temp+1; j<=n; j++)

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

    //填右下角元素 for (i=temp+1; i<=n; i++)

    for (j=temp+1; j<=n; j++)

    a[i][j]=a[i-temp][j-temp];

    }

    }

    四、时间复杂度分析

    迭代处理的循环体内部有3个循环语句,每个循环语句都是一个嵌套的for循环,且他们的执行次数相同,基本语句是最内层循环体的赋值语句,即填写比赛日程表中的元素。基本语句的执行次数是:

    故其时间复杂性为O(4^k)。

    展开全文
  • 循环赛日程安排问题是算法分析与设计中的经典问题,本程序采用C语言实现的,很好啊!!! 问题描述: 设有n(n = 2^k)位选手参加网球循环赛,循环赛共进行n-1天,每位选手要与其他n-1位选手比赛一场,且每位选手每天...
  • 分治法实现循环赛日程安排问题

    千次阅读 2020-05-14 12:17:56
    设有n=2^k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能参赛一次; (3)循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n...
  • 设有n=2^k个选手参加循环赛,要求设计一个满足以下要求比赛日程表: 1)每个选手必须与其它n-1个选手各赛一次; 2)每个选手一天只能赛一次。 大概思路 构造一个n*n矩阵,矩阵的第一列元素为1…n,代表该行其他比赛...
  • 【算法设计与分析】分治法与循环赛日程安排问题

    万次阅读 多人点赞 2018-10-15 17:22:27
    说明:这是武汉理工大学计算机学院【算法设计与分析】课程的第一次实验第二题:分治法与循环赛日程安排问题 >>点击查看WUTer计算机专业实验汇总 谨记:纸上得来终觉浅,绝知此事要躬行。 一、问题描述: ...
  • 本程序运用分治的思想,实现了循环赛日程安排问题的求解, 生成日程表,输出。 代码简述 通过用户输入数据,程序输入检测,动态分配空间, 调用生成日程表函数,显示输出。 其中,生成日程..
  • 循环赛日程安排问题 设有16个运动员将进行网球循环赛。现要设计一个满足以下要求的比赛日程表:⑴ 每个选手必须与其它15个选手各赛一场,⑵ 每个选手一天只能赛一场,⑶ 循环赛进行15天。 算法实现: package ...
  • 算法(c++)——循环比赛日程安排问题
  • 实验一 分治法 【实验目的】 1、深刻理解并掌握“分治算法”的设计思想;...循环赛日程安排 一、实验内容: 设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表: 1、每个选手必须与其他n-1个
  • 分治法:循环赛日程安排问题

    万次阅读 多人点赞 2016-05-12 23:00:13
    问题:设有n=2^k个选手参加循环赛,要求设计一个满足以下要求比赛日程表: 1)每个选手必须与其它n-1个选手各赛一次; 2)每个选手一天只能赛一次。 分析,按照上面的要求,可以将比赛表设计成一个n行n-1列的二维...
  • 循环赛日程

    2014-12-26 12:19:49
    该文档详细的讲解了循环赛日程表的算法分析与实现,并在这个文档中分了多种算法来分析循环赛日程表,并分析了各种算法的复杂度
  • 利用C语言实现分治法的一个实例——循环赛程问题
  • 循环赛日程问题

    2021-02-10 08:39:22
    最近在学习算法分析与设计这门课时,遇到了循环赛日程问题。我感觉课本上的方法并不是很好(浪费空间而又不好理解),而网上流传的代码也基本和课本上类似,于是我决定用自己的方式来实现这个算法。目录问题描述设有...
  • 设有n=2^k个选手参加循环赛,要求设计一个满足以下要求比赛日程表: 1)每个选手必须与其它n-1个选手各赛一次; 2)每个选手一天只能赛一次。 思路: 边长为2的次方,暴力分治 #include <bits/stdc++.h> using...
  • 循环赛日程安排(C语言)

    千次阅读 多人点赞 2018-11-24 18:35:18
    问题: 一年一度的欧洲冠军杯马上就要打响,在初赛阶段采用循环制,设共有n队参加,初赛共进行(n-1)天,每队要和其他各队进行一场比赛。要求每队每天只能进行一场比赛,并且不...比赛日程安排 算法训练 比赛安排 ...
  • 问题:设有n=2^k个选手参加循环赛,要求设计一个满足以下要求:1)每个选手必须与其它n-1个选手各赛一次;2)每个选手一天只能赛一次。3)循环赛共进行 n -1 天。分析:按照上面的要求,可以将比赛表设计成一个n行n-1列...
  • #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;cmath&gt; #include &lt;cstdlib&gt; #define maxn 10000 ...v...
  • 设有n=2^k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表: 1、每个选手必须与其他n-1个选手各赛一次; 2、每个选手一天只能参赛一次; 3、循环赛在n-1天内结束。 按此要求,可将比赛日程表设计...
  • 循环赛日程表的分治算法实现实验报告_gxl深 圳 大 学 实 验 报 告课程名称: 算法设计与分析实验项目名称: 分治算法--矩阵相乘的Strassen算法及时间复杂性分析或--循环赛日程表的分治算法实现或--多项式乘积问题的...
  • 本文采用分治算法来解决循环赛日程表的安排问题。通过对问题的详细分析,列出1到10个选手的比赛日程表,找出两条规则,作为算法实现的依据,而后采用c语言实现算法,通过测试分析,程序运行结果正确,运行效率较高。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,204
精华内容 481
关键字:

循环赛日程安排问题