课程设计说明书(论文)用纸
摘 要
分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2 时，只要做一次比较即可排好序；当n = 3时只要做两次比较即可……而当n较大时，问题就不容易那么处理了。要想直接解决一个较大的问题，有时是相当困难的。分治算法的基本思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1 < k < n+1，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治算法就是可行的。由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此自然引出递归算法。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
本次课程设计正是采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。
关键词：分治算法
I
课程设计说明书(论文)用纸
目 录
摘 要 ......................................................................................................... I 1 问题描述 ................................................................................................. 1 2 问题分析 ................................................................................................. 2 3 算法设计 ................................................................................................. 3 4 算法实现 ................................................................................................. 7 5 测试分析 ............................................................................................... 11 结 论 ....................................................................................................... 12 参考文献 ................................................................................................... 13
II
课程设计说明书(论文)用纸
1 问题描述
设有n位选手参加网球循环赛，n=2k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按以下要求为比赛安排日程，
1) 2) 3)
每位选手必须与其他n-1格选手格赛一场； 每个选手每天只能赛一场； 循环赛一共进行n-1天；
请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n,1≤j≤n-1。
第1页 共13页
课程设计说明书(论文)用纸
2 问题分析
运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解。
1.分治法:对于一个规模为n的问题，若该问题可以容易的解决（比如说规模n较小），则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互且与原问题形式相同，递归的解决这些子问题，然后将个子问题的解合并，得到原问题的解。 2.分治法的解题步骤（由三个步骤组成）
划分（divide）：将原问题分解为若干个规模较小、相互、与原问题形式相同的子问题。
解决（conquer）：若子问题规模较小，则直接求解；否则递归求解各子问题。
合并（conbine）：将各子问题的解合并为原问题的解
假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则，可从其中以半选手的比赛日程，导出全体n位选手的的日程，最终细分到只有两位选手的比赛日程出发。
第2页 共13页
课程设计说明书(论文)用纸
3 算法设计
1.设计步骤：
1) 先设计主函数(main函数)，然后设计两个函数，分别是安排赛事进行填制表格的函数（void Table(int n, int a[100][100])函数）和输出到屏幕函数（void Out(int n,int a[100][100])）。
2) 在主函数(main())里调用void Table()函数，对比赛日程进行安排，根据分而治之原则，绘制比赛日程表格，然后调voidOut()函数，将安排好的比赛日程输出到屏幕上。 2.关键数据结构
1) 运用一个二维数组a[i][j]，对安排好的赛事日程进行排列和保存，并在屏幕上输出。
2) 使用二维数组的原因：因为根据题目要求，比赛日程表是一个n行n-1列的表格，用a[i][j]代表第i号选手在第j天遇到的对手，所以用一个二维数组表示。 3.程序结构
程序主要由三个函数组成： 1) main()函数（主函数）；
2) void Table()函数（本程序的核心函数）； 3) Out()函数（输出函数） 三个函数的程序结构如下所示：
第3页 共13页
课程设计说明书(论文)用纸
1) main()函数
计算参赛人数n=2k 计算参赛人数n值 输入k值 int k; main()
图 3-1
传值 调用void Table（）函数 调用Out ()函数，输出到屏幕 结束 2) void Table ()函数
第4页 共13 页
课程设计说明书(论文)用纸
void Table(int n, int a[100][100]) int i=1 i<=n Y N m=1 i++ s=1 i++ a[1][i]=i s<=k? Y N n=n/2 s++ int t=1 m=m*2 N t<=n? Y int i=m+1 i<=2*m Y N t++ j=m+1 i++ N j<=m+1 Y 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] j++ 结束 图3-2
第5页 共13 页
课程设计说明书(论文)用纸
3) Out（）函数
void Out(int n,int a[100][100]) int i=1 N i<=n Y i++ int j=1 j<=n Y printf(“%4d”,a[i][j]); N printf(“\\n”); j++ 结束
图3-3
第6页 共13 页
课程设计说明书(论文)用纸
4 算法实现
关键程序功能及程序的说明如下： 1. main（）函数
（1）函数功能：在屏幕上输入k值，计算参赛人数n，然后调用void Table()函数和Out（）函数。
（2）函数实现：
①先定义一个k，然后在键盘上输入一个k值，并赋值给k（假设输入3）；
②运用for循环，计算参赛人数n的值 for (int i=1;i<=k;i++) n *= 2;
可得n=8，即有八个人参赛。
③然后调用void Table()函数和Out（）函数，并传值。 2.void Table()函数
(1)函数功能：对所有运动员的赛程进行安排，并将其存入数组内。
(2)函数实现：由main（）函数得到k值为3，n值为8 ①用一个for循环输出日程表的第一行 for(int i=1;i<=n;i++) a[1][i] = i；
第7页 共13页
课程设计说明书(论文)用纸
1 2 3 4 5 6 7 8 ②然后定义一个m值，m初始化为1，m用来控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置。
③用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。
for (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控制列
{ a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m];/*右下角的值等于左上角的值 */
第8页 共13 页
课程设计说明书(论文)用纸
a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2];/*左下角的值等
于右上角的值 */
}
例：由初始化的第一行填充第二行 1 2 2 1 3 4 4 3 5 6 6 5 7 8 8 7 由s控制的第一部分填完。然后是s++，进行第二部分的填充 1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
5 6 7 8
6 5 8 7
7 8 5 6
8 7 6 5
最后是第三部分的填充 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 ⑥这样循环，直到填充完毕，a[][]数组被赋予新值。
第9页 共13 页
课程设计说明书(论文)用纸
3.Out（）函数
（1）函数功能：将安排好的赛事日程，即二维数组a[n][n-1]输出到屏幕。
（2）函数主要功能实现：
函数主要运用一个for循环，将二维数组a[n][n-1]输出到屏幕。 for (i = 1; i<= n; i++) { for (j = 1; j<= n; j++) {
printf(\"%4d\ } printf(\"\\n\"); } printf(\"\\n\");
第10页 共13 页
课程设计说明书(论文)用纸
5 测试分析
程序编译成功后，执行程序，在提示下输入k值，程序即可算出参赛的队员人数n（n = 2k），同时屏幕显示我们需要的循环赛日程表，程序运行结果如图5-1所示：
图 5-1
第11页 共13页
课程设计说明书(论文)用纸
结 论
程序主要运用了：数据输入、函数调用、函数传值、for循环以及二维数组等主要结构和功能。根据分治算法，将本问题进行了由小规模到大规模的求解设计，程序设计的关键点在于如何对问题进行划分和填充公式的归纳。在划分时，主要运用了两个for循环；在填充时，运用了两个for循环。
通过这次程序设计，加深了对分治算法的认识。解决具体问题时，程序故重要，但一个好的算法更加重要。
本程序的得意之处在于，经过仔细研究，找到了划分的方法，并推导出了表格填充的两个公式。不足之处也在此，即花费了很长时间来推导这个，对算法掌握还不够熟练。
第12页 共13页
课程设计说明书(论文)用纸
参考文献
[1] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007：102-121. [2] 严蔚敏 吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997：170-179. [3] 谭浩强.C程序设计(第三版) [M].北京：清华大学出版社，2005：1-378. [4] 王志刚 李卫华著.需求工程导引[M].北京：人民邮电出版社，2003. [5] 陆惠恩著.实用软件工程[M].北京：清华大学出版社，2006. [6] 吕凤翥著.C++语言基础教程（第二版）[M].北京：清华大学出版社，2007.
第13页 共13页
