【精选】【算法】循环赛日程表基础教程,包括 n=奇数的情况~ |
您所在的位置:网站首页 › 网球基本教程 › 【精选】【算法】循环赛日程表基础教程,包括 n=奇数的情况~ |
循环赛日程表
一、问题描叙
设有n=2^k个运动员要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一场; (2)每个选手一天只能赛一次; (3)循环赛一共进行n-1天。 二、问题分析按此要求可将比赛日程表设计成n行n-1列的表,在表中第 i 行和第j 列处填入第 i 个选手在第 j 天所遇到的对手。 例如,当选手的人数为8人时,其比赛日程表如下图: 算法实现步骤: (1)当k=1时,即人数为2人,此情况为最简单的情况 此时表为 1 2 2 1 (2)当k=2时,人数为4人,循环表为 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 (3)当k=3时,人数为8人,此时循环表为 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 以此类推,我们不难发现,我们可以用分治的方法实现,先自顶向下分解,直到分解到最简单的情况,即人数为2人,这时就可以两两比赛,表的填充为对角填充的方式,然后再自底向上填充表格,具体的看上面的k=1,k=2,k=3时形成的循环表就很好理解了。 三、源代码展示 #include #include #define N 50 void GameTable(int k,int array[][N]); void print(int k,int array[][N]); //输出二维数组 main() { int k; int array[N][N]; printf("\t\t****************************************\n"); printf("\t\t**\t\t循环赛日程表 **\n"); printf("\t\t****************************************\n\n"); printf("设参赛选手的人数为n(n=2^k),请输入k 的值:"); do { scanf("%d",&k); if(k!=0) { GameTable(k,array); print(k,array); } else printf("您输入的数据有误,请重新输入"); }while(k!=0); } void GameTable(int k,int array[][N])//数组下标从1开始 { int i,j,s,t; int n=1; for(i=1;i array[i][j+(t-1)*m*2]=array[i-m][j+(t-1)*m*2-m]; //右上角等于左上角的值 array[i][j+(t-1)*m*2-m]=array[i-m][j+(t-1)*m*2]; //左下角等于右上角的值 } m*=2; } } void print(int k,int array[][N]) { int i,j; int num=pow(2,k); printf("%d人的循环赛日程表如下\n",num); for(i=1;i printf("%d\t",array[i][j]); } printf("\n"); } } 四、程序结果展示![]() n为奇数情况请参考这篇文章:https://juejin.im/post/5b515ec9e51d45191556fc3c Reference: 1、https://www.cnblogs.com/crx234/p/5988418.html 2、计算机算法设计与分析王晓东第五版。(如果需要对应课后习题答案的话可以评论区留言,我会发链接哒) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |