摘要分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2 时，只要做一次比较即可排好序；当n = 3时只要做两次比较即可……而当n较大时，问题就不容易则处理了要想直接解决一个较大的问题，有时是相当困难的分治算法的根本思想是，将一个难以直接解决的大问题，分割成一些规模较小的一样问题，以便各个击破，分而治之如果原问题可分割成k个子问题，1 < k < n+1，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，则这种分治算法就是可行的由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解由此自然引出递归算法分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法本次课程设计正是采用分治算法来解决循环赛日程表的安排问题根据算法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确，运行效率较高关键词：分治算法目录摘要I1 问题描述12 问题分析23 算法设计34 算法实现75 测试分析11结论12参考文献13. z.-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 z.-2 问题分析运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解1.分治法:对于一个规模为n的问题，假设该问题可以容易的解决〔比方说规模n较小〕，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式一样，递归的解决这些子问题，然后将个子问题的解合并，得到原问题的解2.分治法的解题步骤〔由三个步骤组成〕² 划分〔divide〕：将原问题分解为假设干个规模较小、相互独立、与原问题形式一样的子问题² 解决〔conquer〕：假设子问题规模较小，则直接求解；否则递归求解各子问题² 合并〔conbine〕：将各子问题的解合并为原问题的解假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格i行j列的表格内容是第i号选手在第j天的比赛对手根据分而治之的原则，可从其中以半选手的比赛日程，导出全体n位选手的的日程，最终细分到只有两位选手的比赛日程出发。
z.-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()函数〔输出函数〕三个函数的程序构造如下所示：1) main()函数调用void Table〔〕函数int k;输入k值main()计算参赛人数n值计算参赛人数n=2k调用Out ()函数，输出到屏幕完毕传值图 312) void Table ()函数void Table(int n, int a[100][100])NNYNYNYYNYint 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*2完毕图3-23) Out〔〕函数i++NNYYvoid Out(int n,int a[100][100])int i=1i<=nint j=1j<=nj++printf("%4d〞,a[i][j]);printf("\n〞);完毕图3-3. z.-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；12345678②然后定义一个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];/*右下角的值等于左上角的值*/ a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2];/*左下角的值等于右上角的值*/} 例：由初始化的第一行填充第二行1234567821436587由s控制的第一局部填完然后是s++，进展第二局部的填充12345678214365873412785643218765最后是第三局部的填充1234567821436587341278564321876556781234658721437856341287654321⑥这样循环，直到填充完毕，a[][]数组被赋予新值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", a[i][j]); } printf("\n"); } printf("\n");. z.-5测试分析程序编译成功后，执行程序，在提示下输入k值，程序即可算出参赛的队员人数n〔n = 2k〕，同时屏幕显示我们需要的循环赛日程表，程序运行结果如图5-1所示：图 51. z.-结 论程序主要运用了：数据输入、函数调用、函数传值、for循环以及二维数组等主要构造和功能。
根据分治算法，将本问题进展了由小规模到大规模的求解设计，程序设计的关键点在于如何对问题进展划分和填充公式的归纳在划分时，主要运用了两个for循环；在填充时，运用了两个for循环通过这次程序设计，加深了对分治算法的认识解决具体问题时，程序故重要，但一个好的算法更加重要本程序的得意之处在于，经过仔细研究，找到了划分的方法，并推导出了表格填充的两个公式缺乏之处也在此，即花费了很长时间来推导这个，对算法掌握还不够熟练 z.-参考文献[1] 王晓。