循环赛日程表实验报告

1、精选优质文档-倾情为你奉上天津工程师范学院算法与程序计 -课程设计报告 班级：计科0813班学号：姓名：设计时间：2009.12.2112.25一课程设计名称：循环赛日程表二.实验内容问题描述:设有n位选手参加网球循环赛，n=2k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按一下要求为比赛安排日程，（1） 每位选手必须与其他n-1格选手格赛一场；（2） 每个选手每天只能赛一场；（3） 循环赛一共进行n-1天；请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中1in,1jn-1

2、。三.实验目的1.运用分治法，设计解决上述问题的算法，设计出比赛日程表，在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手（其中1in,1jn-1）。2.掌握分治算法的应用。四算法原理运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解。1.分治法:对于一个规模为n的问题，若该问题可以容易的解决（比如说规模n较小），则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归的解决这些子问题，然后将个子问题的解合并，得到原问题的解。2.分治法的解题步骤（由三个步骤组成）l 划分（divide）：将原问题分解为若干个规模较小、相互独立、与原问

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

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

5、 arrangement()函数（本程序的核心函数），（3）print函数（输出函数）1.main（）函数传值调用void arrangement（）函数int k;输入k值main()计算参赛人数n值计算参赛人数n=2k调用print()函数，输出到屏幕结束2.void arrangement()函数void arrangement(int n,int N,int k,int a100100)NNYNYNYYNYint i=1i<=Ni+a1i=ii+m=1s=1s<=k?N=N/2int t=1t<=N?int i=m+1i<=2*mj=m+1j<=m+1ai

6、j+(t-1)*m*2 = ai-mj+(t-1)*m*2-maij+(t-1)*m*2-m = ai-mj+(t-1)*m*2j+i+t+s+m=m*2结束3.print（）函数i+NNYYvoid print(int n,int a100100)int i=1i<=nint j=1j<=nj+cout<<setw(4)<<setfill(' ')<<aijcout<<endl“”结束九关键程序功能及其实现的说明1. .main（）函数（1）函数功能：在屏幕上输入k值，计算参赛人数n，然后调用void arrange

7、ment()函数和print（）函数。（2）函数实现：先定义一个k，然后在键盘上输入一个k值，并赋值给k（假设输入3）；运用for循环，计算参赛人数n的值for (int i=1;i<=k;i+) n *= 2;可得n=8，即有八个人参赛。然后调用void arrangement()函数和print（）函数，并传值。2.void arrangement()函数(1)函数功能：对所有运动员的赛程进行安排，并将其存入数组内。(2)函数实现：由main（）函数得到k值为3，n值为8用一个for循环输出日程表的第一行for(int i=1;i<=N;i+) a1i = i；12345678

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+)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分 同理，对第二部分（即三四行），划分为两部分，第三部分同理最后，根

9、据以上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-m = ai-mj+(t-1)*m*2;/*左下角的值等于右上角的值 */ 例：由初始化的第一行填充第二行1234567821436587由s控制的第一部分填完。然后是s+，进行第二部分的填充123456782143658734127856432

10、18765最后是第三部分的填充1234567821436587341278564321876556781234658721437856341287654321这样循环，直到填充完毕，a数组被赋予新值。3.print（）函数（1）函数功能：将安排好的赛事日程，即二维数组ann-1输出到屏幕。（2）函数主要功能实现：函数主要运用一个for循环，将二维数组ann-1输出到屏幕。for( int i=1;i<=n;i+)/控制行cout<<setw(3)<<setfill(' ')<<ai1<<"|"for(in

11、t j=2;j<=n;j+) /控制列 cout<<setw(4)<<setfill(' ')<<aij; cout<<endl;十程序运行结果十一.体会程序主要运用了：数据输入、函数调用、函数传值、for循环以及二维数组等主要结构和功能。根据分治算法，将本问题进行了由小规模到大规模的求解设计，程序设计的关键点在于如何对问题进行划分和填充公式的归纳。在划分时，主要运用了两个for循环；在填充时，运用了两个for循环。通过这次程序设计，加深了对分治算法的认识。解决具体问题时，程序故重要，但一个好的算法更加重要。本程序的得意之处

12、在于，经过仔细研究，找到了划分的方法，并推导出了表格填充的两个公式。不足之处也在此，即花费了很长时间来推导这个，对算法掌握还不够熟练。十二.工具软件及运行环境1.工具软件：Microsoft Visual C+ 6.02.运行环境：Win32 Console Application专心-专注-专业附：#include<iostream>#include<iomanip>using namespace std;void print(int n,int a100100);void arrangement(int n,int N,int k,int a100100);int

13、main() int k; int a100100; int n=1; cout<<"请输入 k"<<endl; cin >> k; for (int i=1;i<=k;i+) n *= 2;/n=2k cout<<"参赛人数"<<n<<endl; int N=n; arrangement(n, N, k, a); print(n,a); void arrangement(int n,int N,int k,int a100100)for(int i=1;i<=N;i+)

14、 a1i = i;int m =1;for (int s=1;s<=k;s+) N/=2; 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+) aij+(t-1)*m*2=ai-mj+(t-1)*m*2-m; aij+(t-1)*m*2-m=ai-mj+(t-1)*m*2; m *= 2; void print(int n,int a100100)cout<<"-"<<"循环赛日程表"<<"-"<<endl;cout<<endl;cout<<"日期"for(int p=1;p<n;p+)cout<<setw(4)<<setfill('-')<