循环赛日程表实验报告

天津工程师范学院1《算法与程序计》--课程设计报告班级：计科0813班学号：02210081302姓名：设计时间：2009.12.21—12.25天津工程师范学院天津工程师范学院2一．课程设计名称：循环赛日程表二.实验内容问题描述:设有n位选手参加网球循环赛，n=2^k，循环赛共进行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。三.实验目的1.运用分治法，设计解决上述问题的算法，设计出比赛日程表，在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手（其中1≤i≤n,1≤j≤n-1）。2.掌握分治算法的应用。四．算法原理运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解。天津工程师范学院31.分治法:对于一个规模为n的问题，若该问题可以容易的解决（比如说规模n较小），则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归的解决这些子问题，然后将个子问题的解合并，得到原问题的解。2.分治法的解题步骤（由三个步骤组成）划分（divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。解决（conquer）：若子问题规模较小，则直接求解；否则递归求解各子问题。合并（conbine）：将各子问题的解合并为原问题的解五．问题分析假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则，可从其中以半选手的比赛日程，导出全体n位选手的的日程，最终细分到只有两位选手的比赛日程出发。六．设计步骤1.先设计主函数（main函数），然后设计两个函数，分别是安排赛事进行填制表格的函数（voidarrangement(intn,intN,intk,inta[100][100])函数）和输出到屏幕函数（voidprint(intn,inta[100][100])）。天津工程师范学院42.在主函数（main（））里调用voidarrangement（）函数，对比赛日程进行安排，根据分而治之原则，绘制比赛日程表格，然后调用voidprint（）函数，将安排好的比赛日程输出到屏幕上。七．关键数据结构1.运用一个二维数组a[i][j]，对安排好的赛事日程进行排列和保存，并在屏幕上输出。2.使用二维数组的原因：因为根据题目要求，比赛日程表是一个n行n-1列的表格，用a[i][j]代表第i号选手在第j天遇到的对手，所以用一个二维数组表示。八．程序结构程序主要由三个函数组成：（1）main（）函数（主函数），（2）voidarrangement()函数（本程序的核心函数），（3）print函数（输出函数）1.main（）函数天津工程师范学院5传值调用voidarrangement（）函数intk;输入k值main()计算参赛人数n值计算参赛人数n=2^k调用print()函数，输出到屏幕结束天津工程师范学院6voidarrangement(intn,intN,intk,inta[100][100])NNYNYNYYNYinti=1i=Ni++a[1][i]=ii++m=1s=1s=k?N=N/2intt=1t=N?inti=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结束2.voidarrangement()函数天津工程师范学院73.print（）函数i++NNYYvoidprint(intn,inta[100][100])inti=1i=nintj=1j=nj++coutsetw(4)setfill('')a[i][j]coutendl“”结束天津工程师范学院8九．关键程序功能及其实现的说明1..main（）函数（1）函数功能：在屏幕上输入k值，计算参赛人数n，然后调用voidarrangement()函数和print（）函数。（2）函数实现：①先定义一个k，然后在键盘上输入一个k值，并赋值给k（假设输入3）；②运用for循环，计算参赛人数n的值for(inti=1;i=k;i++)n*=2;可得n=8，即有八个人参赛。③然后调用voidarrangement()函数和print（）函数，并传值。2.voidarrangement()函数(1)函数功能：对所有运动员的赛程进行安排，并将其存入数组内。(2)函数实现：由main（）函数得到k值为3，n值为8①用一个for循环输出日程表的第一行for(inti=1;i=N;i++)a[1][i]=i；12345678②然后定义一个m值，m初始化为1，m用来控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置。天津工程师范学院9③用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。for(ints=1;s=k;s++)N/=2;④用一个for循环对③中提到的每一部分进行划分for(intt=1;t=N;t++)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分同理，对第二部分（即三四行），划分为两部分，第三部分同理⑤最后，根据以上for循环对整体的划分和分治法的思想，进行每一个单元格的填充。填充原则是：对角线填充for(inti=m+1;i=2*m;i++)//i控制行for(intj=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];/*左下角的值等于右上角的值*/}例：由初始化的第一行填充第二行天津工程师范学院101234567821436587由s控制的第一部分填完。然后是s++，进行第二部分的填充12345678214365873412785643218765最后是第三部分的填充1234567821436587341278564321876556781234658721437856341287654321⑥这样循环，直到填充完毕，a[][]数组被赋予新值。3.print（）函数（1）函数功能：将安排好的赛事日程，即二维数组a[n][n-1]输出到屏幕。天津工程师范学院11（2）函数主要功能实现：函数主要运用一个for循环，将二维数组a[n][n-1]输出到屏幕。for(inti=1;i=n;i++)//控制行{coutsetw(3)setfill('')a[i][1]|;for(intj=2;j=n;j++)//控制列coutsetw(4)setfill('')a[i][j];coutendl;}十．程序运行结果十一.体会程序主要运用了：数据输入、函数调用、函数传值、for循环以及二维数组等主要结构和功能。根据分治算法，将本问题进行了由小规模到大规模的求解设计，程序设计的关键点在于如何对问题进行划分和填充公式的归纳。在划分时，主要运用了两个for循环；在填充时，运用了两个for循环。天津工程师范学院12通过这次程序设计，加深了对分治算法的认识。解决具体问题时，程序故重要，但一个好的算法更加重要。本程序的得意之处在于，经过仔细研究，找到了划分的方法，并推导出了表格填充的两个公式。不足之处也在此，即花费了很长时间来推导这个，对算法掌握还不够熟练。十二.工具软件及运行环境1.工具软件：MicrosoftVisualC++6.02.运行环境：Win32ConsoleApplication天津工程师范学院13附：#includeiostream#includeiomanipusingnamespacestd;voidprint(intn,inta[100][100]);voidarrangement(intn,intN,intk,inta[100][100]);intmain(){intk;inta[100][100];intn=1;cout请输入kendl;cink;for(inti=1;i=k;i++)n*=2;//n=2^kcout参赛人数nendl;intN=n;arrangement(n,N,k,a);print(n,a);}voidarrangement(intn,intN,intk,inta[100][100]){for(inti=1;i=N;i++){a[1][i]=i;}intm=1;for(ints=1;s=k;s++){N/=2;for(intt=1;t=N;t++){for(inti=m+1;i=2*m;i++)for(intj=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;}}voidprint(intn,inta[100][100]){cout------------------------------循环赛日程表------------------------------endl;coutendl;cout日期;for(intp=1;pn;p++)coutsetw(4)setfill('-')p;coutendl;for(inti=1;i=n;i++){coutsetw(3)setfill('')a[i][1]|;for(intj=2;j=n;j++)coutsetw(4)setfill('')a[i][j];coutendl;}}