分支算法循环赛日程表课程设计

Java 循环比赛日程表附有结果//输出表格a[i][j]（i =1,2,…,n;j=2,3,…,n）表示第i号选手在第j-1天的对手public class CirCompete {public void Table(int k,int[][]a){int n=1;for(int i=1;i<=k;i++){//假设k=个运动员要进行循环比赛n2n *=2; //通过k计算n值，实际是通过参赛人数计算出k值的}for(int i=1;i<=n;i++){a[1][i]=i; //打印出第一行即选手1的赛程表}int m=1;//控制每次填充表格i(i表示行)和j(j表示列)的起始填充位置for(int s=1;s<=k;s++){n/=2;//将问题分成k部分for(int t=1;t<=n;t++) {//对每一部分进行划分for(int i=m+1;i<=2*m;i++){ //控制行for(int j=m+1;j<=2*m;j++){//控制列a[i][j +(t - 1) * m *2] = a[i - m][j + (t - 1) * m * 2 - m];//右下角等于左上角a[i][j + (t - 1) * m * 2 -m] = a[i - m][j + (t - 1) * m * 2];//左下角等于右上角} }}m*=2;} }public static void main(String[] args) {CirCompete circompete = new CirCompete();int[][] a=new int[9][9];circompete.Table(3,a);//求8n个选手时候的比赛日程表23==for(int i=1;i<9;i++) {for(int j=1;j<9;j++) {System.out.print(a[i][j]+" ");}System.out.println();}}}运行结果：1 2 3 4 5 6 7 82 1 43 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 87 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1。

附件二【学生用】《算法分析与设计》综合训练实习报告题目：利用分治思想设计循环赛日程表学号姓名专业班级指导教师实践日期目录一、综合训练目的与要求 (1)二、综合训练任务描述 (1)三、算法设计 (1)四、详细设计及说明 (5)五、调试与测试 (5)六、实习日志 (8)七、实习总结 (8)八、附录：核心代码清单 (8)一、综合训练目的与要求本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。

本课综合训练的目的和任务：1. 巩固和加深学生对算法分析课程基本知识的理解和掌握；2. 培养利用算法知识解决实际问题的能力；3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力；4. 掌握书写算法设计说明文档的能力；5. 提高综合运用算法、程序设计语言、数据结构知识的能力。

二、综合训练任务描述有n个运动员要进行网球循环赛，设计比赛日程表：（1）每个选手必须与其他n-1个选手赛一次；（2）每个选手一天只能赛一次；（3）当n是偶数时，循环赛进行n-1天；当n是奇数时，循环赛进行n天；（4）要求掌握分治法或者多边形方法；（5）设计一个界面，显示产生的日程表；（6）编程语言不限；三、算法设计(1) 文字描述按分治策略，可以将所有的选手对分为两组（如果n是偶数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。

递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。

这时只要让这两个选手进行比赛就可以了。

下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。

(2)框图比赛人数nNNYNYNYYNYint i=1i<=Ni++a[1][i]=ii++m=1s=1s<=k?N=N/2int t=1t<=N?int i=m+1i<=2*mj=m+1j<=m+1a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m] a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]j++i++t++s++ m=m*2k+=1伪代码public static void copy(int n) {int m = n / 2;for (int i = 1; i <= m; i++)for (int j = 1; 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];}}public static void tournament(int n) {if (n == 1) {a[1][1] = 1;return;}if (odd(n)) {tournament(n + 1);}tournament(n / 2);makecopy(n);}public static boolean odd(int n) {return (n & 1) != 0;}public static void makecopy(int n) // makecopy 与copy算法类似，但是要区分n/2为奇数或偶数的情形{if (n / 2 > 1 && odd(n / 2))copyodd(n);elsecopy(n);}public static void copyodd(int n) // 实现n/2为奇数时的复制{int b[] = new int[size];int m = n / 2;for (int i = 1; i <= m; i++) {b[i] = m + i;b[m + i] = b[i];}for (int i = 1; i <= m; i++) // 这个循环比较难看懂，试着在纸上走走n=6时的情形，就能明白为什么要这么写 { for (int j = 1; j <= m + 1; j++) { if (a [i][j] > m) { a [i][j] = b[i];a [m + i][j] = (b[i] + m) % n; } elsea [m + i][j] = a [i][j] + m;}for (int j = 2; j <= m; j++) { a [i][m + j] = b[i + j - 1]; a [b[i + j - 1]][m + j] = i; }}}}四、详细设计及说明1.输入数字n 判断n 的奇偶性，根据情况进行分治法，安排赛程。

循环赛⽇程表_分治法题⽬： 设有n=2^k个运动员要进⾏⽹球循环赛。

现要设计⼀各满⾜⼀下要求的⽐赛⽇程表： 1、每个选⼿必须与其他n-1个选⼿各⽐赛⼀次。

2、每个选⼿⼀天只能赛⼀次。

3、循环赛⼀共进⾏n-1天。

按照此要求可以将⽐赛⽇程表设计成⼀个n*n的⼆维表，第⼀列表⽰选⼿，接下来的每⼀列依次表⽰将要⽐赛的每⼀天选⼿。

下⾯以8个选⼿为例：思路： 按照分治法，可将所有选⼿进⾏⼆分，n个选⼿的⽐赛安排可通过n/2个选⼿的⽇程表来决定。

递归地⽤这种⼀分为⼆的策略对选⼿进⾏分割，知道只剩两个选⼿，⽇程表显然直接安排即可。

下图为8个选⼿的⽐赛⽇程表： 图1算法步骤： 1、利⽤⼀个for循环初始化选⼿1的⽇程安排，即图1中的第⼀⾏。

2、根据选⼿1的⽇程安排来安排选⼿2。

此刻为最⼩规模，以相邻的每两天即四个最⼩单元为⼀组，例如选⼿⼀第⼀天要跟选⼿2⽐赛，那么相应选⼿2也要跟选⼿1⽐赛，所以将图1中的第⼀⾏第⼀列序号抄到第⼆⾏第⼆列，将第⼀⾏第⼆列序号抄到第⼆⾏第⼀列。

依次，第3、4列，第5、6列，第7、8列也是。

3、根据选⼿1、2的⽇程安排可以按照左上⾓数据抄到右下⾓，右上⾓数据抄到左下⾓安排出选⼿3、4的⽇程。

4、最后根据前四选⼿，可以将所有⼈的⽇程表都安排出来。

下⾯是java实现完整代码：1package competition;23import java.util.Scanner;45public class Com {6private static Scanner scanner;78public static void main(String [] args) {9int k; //注意，n才是选⼿的⼈数，k只是问题要划分的⼦问题规模数，即n=2^k10 System.out.println("输⼊k：");11 scanner = new Scanner(System.in);12 k=scanner.nextInt();13int a[][]=new int[pow(2,k)+1][pow(2,k)+1];14 table(k, a);15for(int i=1; i<pow(2,k)+1; i++){16for(int j=1; j<pow(2,k); j++){17 System.out.print(a[i][j]+" ");18 }19 System.out.println(a[i][pow(2,k)]);20 }21 }2223static void table(int k, int [][]a){24int n=pow(2,k);25for(int i=1; i<=n; i++) a[1][i]=i;26int m=1;//定义M为记录每⼀次填充时i、j的起始填充位置27for(int s=1; s<=k; s++){//分治规模28 n/=2;29for(int t=1; t<=n; t++)//t是每⼀层分治中进⾏对称的单位的个数30for(int i=m+1; i<=2*m; i++)//控制⾏31for(int j=m+1; j<=2*m; j++){//控制列32 a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];//右下⾓的值等于左上⾓的值33 a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];//左下⾓的值等于右上⾓的值34 }35 m*=2;36 }37 }3839static int pow(int a, int n) {//幂函数40int res=1;41for(int i=0; i<n; i++)42 res*=a;43return res;44 }45 }。

摘要分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2 时，只要做一次比较即可排好序；当n = 3时只要做两次比较即可……而当n 较大时，问题就不容易那么处理了。

要想直接解决一个较大的问题，有时是相当困难的。

分治算法的基本思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k 个子问题，1 < k < n+1，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治算法就是可行的。

由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。

由此自然引出递归算法。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

本次课程设计正是采用分治算法来解决循环赛日程表的安排问题。

根据算法的设计结果，采用 c 语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。

关键词：分治算法目录摘要 (I)1问题描述 (1)2问题分析 (2)3算法设计 (3)4算法实现 (8)5测试分析 (12)结论 (13)参考文献 (14)1问题描述设有n 位选手参加网球循环赛，n=2k，循环赛共进行n-1 天，每位选手要与其他n-1 位选手比赛一场，且每位选手每天比赛一场，不能轮空，按以下要求为比赛安排日程，1)每位选手必须与其他n-1 格选手格赛一场；2)每个选手每天只能赛一场；3)循环赛一共进行n-1 天；请按此要求将比赛日程表设计成有n 行和n-1 列的一个表。

在表中的第i 行和第j 列处填入第i 个选手在第j 天所遇到的选手，其中1≤i ≤n,1≤j ≤n-1 。

2问题分析运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解。

利用分治法设计循环赛日程表摘要:对于单循环赛的比赛日程安排问题,利用分治算法给出了可读性较好的设计，并分析了各种假设下的时间复杂度。

关键词:分治算法;复杂度;递归;循环赛引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易求解，所需的计算时间也越少。

分治法是计算机科学中经常使用的一种算法。

设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

1分治法应用条件及一般步骤1.1 分治法的应用条件1.1.1能将n个数据分解成k个不同子集合，且得到的k个子集合是可以独立求解的子问题，其中11&&odd(n/2)) copyodd(n);else copy(n);}void copyodd(int n){int m=n/2;for(int i=0;i=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=1;j<m;j++){a[i][m+j]=b[i+j];a[b[i+j]][m+j]=i;}}}分析算法的时间性能:当n/2为奇数时，基本语句的执行次数是：当n/2为偶数时，基本语句的执行次数是：综上，时间复杂度为O(4k )。

2.3 运行结果及分析当输入n为2时，输出：0 11 0在上面n=2时的日程表（二维表）中，左边第一列表示球队编号，第二列表示在某天碰到的对手球队的编号。

推广之，对于n行n列的二维日程表，那么，a[0][0]，a[1][0]，……，a[n-1][0]表示参加循环赛的n支球队的编号；a[0][1]，a[0][2]，……，a[0][n-1]表示球队a[0][0]在第1，2，……,n-1天碰到的对手球队编号。

a[i][j]（i,j<n）表示编号为a[i][0]的球队在第j日遇到的对手球队的编号。

以下同。

问题描述：设有n个运动员要进行网球循环赛。

设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能赛一次；（3）当n是偶数时，循环赛进行n-1天。

当n是奇数时，循环赛进行n天。

分析过程：这个问题的解搜索空间是一个n的全排列。

要求的解是其中的n个排列，满足条件：第1列n个元素值按增序排列；每行每列没有相同的数。

也是一个幻方（除对角线的和不作要求）的问题。

1.n=11）2. n=2（表2）3.n=3,(1) 添加一个虚拟选手4#，构成n+1＝4(2) 4/2＝2，分两组，每组各自安排（1 2），（3 4）(3)每组跟另一组分别比赛（拷贝）这是四个人比赛的安排(4)把虚选手置为0(表4)3人赛程这是三个人比赛的安排4. n=4, 见表35. n=5, (1)加一个虚选手，n+1=6。

安排好6个人的比赛后，把第6个人用0表示即得5人的。

(2) 分成两组(1 2 3) （4 5 6），各3名选手(3) 依照表4，安排第1组；按表5安排第2组(除0元素外，都加3)（表5）(4) 把表5排于表4下方(5) 把同一天都有空的两组安排在一起比赛(按这种安排，肯定每天只有一对空组，？)。

(6) 第一组的(1 2 3)和第2组的(4 5 6)分别比赛。

但是由于(1,4), (2, 5), (3 6)已经比赛过了，所以在后面的安排中不能再安排他们比赛。

1 2 34 5 6首先，1#只能和5#或6#比赛。

(a)若1#－5#，由于3#和6#已经比赛过，所以只能安排: 2#－6#，3#－4#(b)若1#－6#，由于2#和5#已经比赛过，只能安排：2#－4#，3#－5#这样安排后前三行的后两列，后三行的后两列由上面的三行来定：表8就是6名选手的比赛日程安排。

将其中的6号作为虚拟选手，把6换成0，即得5名选手的赛程安排表：（表9）5人赛程6 n=6，见表8。

7 n=7, 添加1，n+1=8。

利用分治法设计循环赛日程表作者：王猛来源：《科技经济市场》2008年第07期摘要:对于单循环赛的比赛日程安排问题,利用分治算法给出了可读性较好的设计，并分析了各种假设下的时间复杂度。

关键词:分治算法;复杂度;递归;循环赛引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易求解，所需的计算时间也越少。

分治法是计算机科学中经常使用的一种算法。

设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

1分治法应用条件及一般步骤1.1 分治法的应用条件1.1.1能将n个数据分解成k个不同子集合，且得到的k个子集合是可以独立求解的子问题，其中11.1.2分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；1.1.3合并各个子问题的解，就是原问题的解。

1.2 分治法的一般步骤1.2.1分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；1.2.2求解子问题：若子问题规模较小而容易解决则直接解，否则再继续分解为更小的子问题，直到容易解决；1.2.3合并：将已求解的各个子问题的解，合并为原问题的解。

2 循环赛分治算法2.1 问题描述有n支球队参加循环赛，设计一个满足下面要求的比赛日程表：2.1.1每支球队必须与其他n-1支球队各赛一次；2.1.2每支球队一天只能比赛一次；2.1.3当n为偶数时，比赛进行n-1天；当n为奇数时，比赛进行n天。

2.2 算法分析当n=2k （k=1、2、3、4……）时，比较简单。

按照分治的策略，可将所有参赛的选手分为两部分，n＝2k 个选手的比赛日程表就可以通过为n/2＝2k-1 个选手设计的比赛日程表来决定。

递归地执行这种分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单，只要让这2个选手进行比赛就可以了。

再逐步合并子问题的解即可得到原问题的解。

算法如下：void tourna(int n){if(n==1){a[0][0]=1;return;}tourna(n/2);copy(n);}void copy(int n){int m=n/2;for(int i=0;ifor(int j=0;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];}基本语句的执行次数是：T(n)=3=O(4k ),所以算法的时间复杂度为O( 4k)。

【算法-分治策略应⽤】循环赛⽇程表问题⼀、分治策略基本思想1、Divide将原始问题划分或者归结为规模较⼩的⼦问题（多数情况下是划分成2个）2、Conquer递归或迭代求解每个⼦问题3、Combine将⼦问题的解综合得到原问题的解注意：1、⼦问题与原始问题性质完全⼀样2、⼦问题之间可彼此独⽴地求解3、递归停⽌时⼦问题可直接求解⽐较典型的应⽤例⼦是“归并排序法”和“快速排序法”，详细可以参考屈婉玲等编著的《算法设计与分析》（第2版）P26和P37，此处不再赘述。

⼆、题⽬分析和建模1. 问题描述设有n=2k个选⼿要进⾏⽐赛，设计的⽐赛⽇程表需要满⾜以下要求：1）每个选⼿必须与其他n-1个选⼿各赛⼀次；2）每个选⼿⼀天只能赛⼀次；3）整场循环赛⼀共进⾏n-1天。

2. 题⽬建模将⽐赛⽇程表设计成n⾏×n-1列的⼀个表，表中第i⾏第j列的元素表⽰第i个选⼿在第j天所遇到的选⼿。

（1）⾸先看只有两个选⼿的⽇程表（k=1，n=2，2⾏×1列表格，循环赛进⾏1天）：表1 循环赛⽇程表（2⼈）（2）四个选⼿的⽇程表（k=2，n=4，4⾏×3列表格，循环赛进⾏3天）：⾸先n=22，所以应该退化到求解两个2⼈循环赛的问题，⽇程表构建如下：表1 循环赛⽇程表（2⼈） 表2 循环赛⽇程表（2⼈）将表2抄在表1右侧构成表1*，将表1抄在表2右侧构成表2*，将表1*与表2*按次序上下拼接，构成表3：表3 循环赛⽇程表（4⼈）由于表1和表2中运动员完全不同，拼接之后每⼀⾏和每⼀列都不会存在两个相同号码，也就是说拼接后不会产⽣⼀个选⼿在同⼀天和另外⼀个选⼿⽐赛两次的情况，说明这种拼接是合理的。

（3）⼋个选⼿的⽇程表（k=3，n=8，8⾏×7列表格，循环赛进⾏7天）n=23，⾸先应该退化到4⼈循环赛问题，再退化到2⼈循环赛问题，4⼈退化到2⼈已在（2）中详细描述，此处只说明如何退化到4⼈问题：表3 循环赛⽇程表（4⼈） 表4 循环赛⽇程表（4⼈）拼接⽅法与（2）中相同，构成表5：表5 循环赛⽇程表（8⼈）三、算法设计（1）设计思想：设n=2k采⽤分治策略，将所有参加⽐赛的选⼿分成两部分，n=2k个选⼿的⽐赛⽇程表就可以通过两个n=2k-1个选⼿的⽐赛⽇程表来决定。

分治法——循环赛⽇程表1、问题描述：有n=2^k个远动员选⼿，设计⽐赛⽇程表实现：（1）每个选⼿必须与n-1个选⼿⽐赛（2）每个选⼿⼀天只⽐赛⼀场（3）⽐赛共进⾏n-1天输⼊：n⼈输出：n⾏n-1列，第i⾏第j列表⽰第i个选⼿第j天遇到的对⼿，不包含第⼀列表⽰为选⼿编号举例：2⼈1 22 12、问题分析通过化⼤为⼩，分⽽治之的思想，将多⼈的⽐赛⽇程缩⼩为2⼈的⽇程。

以此倒推所有⼈的⽇程。

注意多⼈⽇程规律：以四⼈为例：1 2 | 3 42 1 | 4 3----------3 4 | 1 24 3 | 2 1这样⼀个矩阵分为四个区，左上和右下⼀样，左下和右上⼀样，且右上是左上对应的数字加了n/2.3、代码实现1 #include <stdio.h>2 #include <string.h>34#define N 1285int matrix[N][N] = {0};67void fun(int n)8 {9int i;10int j;11if (n<=0)12 {13return;14 }15if (n>2)16 {17 fun(n/2);18for (i=1;i<=n/2;i++)19 {20for (j=n/2+1;j<=n;j++)21 {22 matrix[i][j] = matrix[i][j-n/2] + n/2;23 }24 }25for (i=n/2+1;i<=n;i++)26 {27for (j=1;j<=n/2;j++)28 {29 matrix[i][j] = matrix[i-n/2][j+n/2];30 }31 }32for (i=n/2+1;i<=n;i++)33 {34for (j=n/2+1;j<=n;j++)35 {36 matrix[i][j] = matrix[i-n/2][j-n/2];37 }38 }39 }40else41 {42 matrix[1][1] = 1;43 matrix[1][2] = 2;44 matrix[2][1] = 2;45 matrix[2][2] = 1;46 }47 }4849void main()50 {51 fun(8);5253int i,j;54for (i=1;i<=8;i++)55 {56for (j=1; j<=8; j++)57 {58 printf("%d ",matrix[i][j]);59 }60 printf("\n");61 }62 }。