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

1、分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2时，只要做一次比较即可排好序；当n = 3时只要 做两次比较即可而当n较大时，问题就不容易那么处理了。要想直接解决一 个较大的问题，有时是相当困难的。分治算法的基本思想是，将一个难以直接解 决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果 原问题可分割成k个子问题，1 k n+1，且这些子问题都可解，并可利用这些 子问题的解求出原问题的解，那么这种分治算法就是可行的。由分治算法产生的 子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况 下，反复应用分

2、治手段，可以使子问题与原问题类型一致而其规模却不断缩小， 最终使子问题缩小到很容易求出其解。由此自然引出递归算法。分治与递归像一 对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。本次课程设计正是采用分治算法来解决循环赛日程表的安排问题。根据算 法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确，运行 效率较高。关键词：分治算法 TOC o 1-5 h z 摘要I HYPERLINK l bookmark10 o Current Document 1问题描述1 HYPERLINK l bookmark16 o Current Document 2问题分析2 HYPE

3、RLINK l bookmark21 o Current Document 3算法设计3 HYPERLINK l bookmark49 o Current Document 4算法实现.7 HYPERLINK l bookmark96 o Current Document 5测试分析11结 论12 HYPERLINK l bookmark99 o Current Document 参考文献.131问题描述设有n位选手参加网球循环赛，n=2k,循环赛共进行n-1天，每 位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按以下要求为比赛安排日程，1)每位选手必须与其他n-1格选

4、手格赛一场;2)每个选手每天只能赛一场;3)循环赛一共进行n-1天;请按此要求将比赛日程表设计成有n行和n-1列的一个表。在 表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中 1 WiWn,1 WjWn-1。2问题分析运用分治法，将原问题划分为较小问题，然后由较小问题的解 得出原问题的解。分治法:对于一个规模为n的问题，若该问题可以容易的解决（比 如说规模n较小），则直接解决，否则将其分解为k个规模较小的子 问题，这些子问题相互独立且与原问题形式相同，递归的解决这些 子问题，然后将个子问题的解合并，得到原问题的解。分治法的解题步骤（由三个步骤组成）划分（divide）：将原问题分

5、解为若干个规模较小、相互独立、与 原问题形式相同的子问题。解决（conquer）：若子问题规模较小，则直接求解；否则递归求 解各子问题。合并（conbine）：将各子问题的解合并为原问题的解假设n位选手顺序编号为1，2, 3n，比赛的日程表是一个 n行n-1列的表格。i行j列的表格内容是第i号选手在第j天的比 赛对手。根据分而治之的原则，可从其中以半选手的比赛日程，导 出全体n位选手的的日程，最终细分到只有两位选手的比赛日程出 发。3算法设计1.设计步骤:1）先设计主函数（main函数），然后设计两个函数，分别是安排赛事进行填制表格的函数（void Table（int n, int a1001

6、00涵数）和输出到屏幕函数（void Out（int n,int a100100）。2）在主函数（main（）里调用void Table（涵数，对比赛日程进行安排，根据分而治之原则，绘制比赛日程表格，然后调voidOut（）函数，将安排好的比赛日程输出到屏幕上。2.关键数据结构1）运用一个二维数组aij，对安排好的赛事日程进行排列和保存，并在屏幕上输出。2）使用二维数组的原因：因为根据题目要求，比赛日程表是一个n行n-1列的表格，用aij代表第i号选手在第j天遇到的对手，所以用一个二维数组表示。程序结构程序主要由三个函数组成:1）main （）函数（主函数）;2） void Table（）函数

7、（本程序的核心函数）;3）Out （）函数（输出函数）三个函数的程序结构如下所示:1) main()函数图3-12) void Table ()函数图3-23) Out ()函数图3-34算法实现关键程序功能及程序的说明如下：1. main ()函数函数功能：在屏幕上输入k值，计算参赛人数n,然后调 用void Table()函数和Out()函数。函数实现：先定义一个k，然后在键盘上输入一个k值，并赋值给k (假 设输入3)；运用for循环，计算参赛人数n的值for (int i=1;i=k;i+)n *= 2;可得n=8，即有八个人参赛。然后调用void Table()函数和Out()函数，

8、并传值。2.void Table ()函数函数功能：对所有运动员的赛程进行安排，并将其存入数组 内。函数实现：由main()函数得到k值为3，n值为8用一个for循环输出日程表的第一行for(int i=1;i=n;i+)a1i = i；12345678然后定义一个m值，m初始化为1, m用来控制每一次填充表格时i (i表示行)和j (j表示列)的起始填充位置。用一个for循环将问题分成几部分，对于k=3, n=8，将问题 分成3大部分，第一部分为，根据已经填充的第一行，填写第二行， 第二部分为，根据已经填充好的第一部分，填写第三四行，第三部 分为，根据已经填充好的前四行，填写最后四行。for

9、 (int s=1;s=k;s+) n/=2;用一个for循环对中提到的每一部分进行划分for(int t=1;t=n;t+)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分：同理，对第二部分(即三四行)，划分为两部分，第三部分同理最后，根据以上for循环对整体的划分和分治法的思想，进行 每一个单元格的填充。填充原则是：对角线填充for(int i=m+1;i=2*m;i+) /i 控制行for(int j=m+1;j=2*m;j+) /j 控制列( aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-m;/* 右下角的值等 于左上角的值*/aij+(t-1)*m*2-

10、m = ai-mj+(t-1)*m*2;/* 左下角的值等于右上角的值*/例：由初始化的第一行填充第二行3.Out ()函数函数功能：将安排好的赛事日程，即二维数组ann-1 输出到屏幕。函数主要功能实现：函数主要运用一个for循环，将二维数组ann-1输出到屏幕。for (i = 1; i= n; i+)( for (j = 1； j= n; j+)(printf(%4d, aij); printf(n); printf(n);5测试分析程序编译成功后，执行程序，在提示下输入k值，程序即可算 出参赛的队员人数n (n = 2k),同时屏幕显示我们需要的循环赛日程 表，程序运行结果如图5-1所

11、示：m. C:WINDOWSsystem32cmd. exe87654321785634126587214312345B78图5-1程序主要运用了：数据输入、函数调用、函数传值、for循环以 及二维数组等主要结构和功能。根据分治算法，将本问题进行了由 小规模到大规模的求解设计，程序设计的关键点在于如何对问题进 行划分和填充公式的归纳。在划分时，主要运用了两个for循环； 在填充时，运用了两个for循环。通过这次程序设计，加深了对分治算法的认识。解决具体问题 时，程序故重要，但一个好的算法更加重要。本程序的得意之处在于，经过仔细研究，找到了划分的方法， 并推导出了表格填充的两个公式。不足之处也在此，即花费了很长 时间来推导这个，对算法掌握还不够熟练。参考文献1王晓东.计算机算法设计与分析M.北京：电子工业出版社，2007： 102-121. 严蔚敏吴