单循环比赛日程报告.doc

数 据 结 构 课程设计报告 设计题: 单循环比赛日程 院 系： 经济学 专业班级： 电务2008-2 学 指导师 周长红 2010年7月16日 指导教师评语 指导教师： 年 月 日 成绩评定 学 号 任务 成绩 0801060626 宋宇星 编程序、查资料等 0801060623 刘泽梅 写报告、查资料等 目 录 1.设计内容 1 1.1问题描述 1 1.2设计要求 1 1.3开发环境 1 1.4研究思路 1 2.设计步骤 3 2.1需求分析 3 2.2概要设计 3 2.3详细设计 5 2.4调试分析 9 2.5测试结果 12 3.设计成果展示 14 3.1用户手册 14 3.2程序运行部分截图 14 4.总结与心得体会 17 附 录 21 1.设计内容 1.1问题 有n个编号为1到n的运动员参加某项运动的单循环比赛，即每个运动员要和所有其它运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在n-1天内结束。 1.2设计1）输入运动员人数n(n=10000); (2) 输出一个n阶方阵A[1..N,0..N-1],当j0时，A[i,j]表示第i名运动员在第j天的比赛对手。 1.3开发环Microsoft Visual C++ 1.4研究思路 首先，我们要证明老师提供的问题，有错误。 错误在于：整个赛程，当N为偶数的时候，N-1天能够结束，而当N为奇数的时候，只能在至少N天结束。 错误分析：原命题中“整个赛程在N-1天结束”，这在N为奇数下的情况不成立， 因为，由已知“每个运动员要和所有其它运动员进行一次比赛”则每个运动员总共进行N-1场，又由每一场有两个运动员参加，N个运动员就进行了C=[N*（N-1）]/2场比赛，又因为已知“要求每个运动员每天只进行一场比赛”则每人每天只能进行1 场，所有运动员为N，每一场由两个运动员参加，后面分两个方面分析： 1、当N为偶数的时候，每天只能出现的场数为N/2场,推出至少的天数为C/(N/2)=N-1场，这与命题中“且整个赛程在N -1天内结束。”不矛盾 2、当N为奇数的时候，由于每个运动员每天只能进行一场，所以每天能进行的总场数最多只能为（N-1）/2场，则整个赛程的天数最少需要 天数 C/[(N-1)/2]=N天，这与原命题“且整个赛程在N -1天内结束。”矛盾。 比如N=3的时候，每场必须有两个人，则每天只能有一场比赛，假设是1和2比赛，则3号运动员没有对象比赛，所以一天最多一场比赛，这个比赛需要的比赛场数C=3场，则整个比赛需要的天数为C/1=3天 由此依照命题前部分要求得出，当N为偶数的情况 循环赛可以进行N-1天，当N为奇数的时候，循环赛至少要进行N天。 其次，介绍一下研究思路。 这题中，老师给的运动员的人数范围为：n=10000，所以，在处理的时候就要考虑到运行时间的问题以及如何安排的问题。这样就考虑到用“分治法”，即将大数逐步分解成小数，先将小数安排完，在将小数的合并推算成大数的安排方法，这里面就用到了递归的调用问题。 在这个程序的运行过程并不需要像游戏的华丽接口，且要求输出一个矩阵即可，所以，选择比较熟悉的C++环境开发。 2.设计骤 2.1,能用Microsoft Visual C++ 输出想要的结果： 1：输入形式是一个小于10000的正整数。 2：输出一个n阶方阵A[1..N,0..N-1],当j0时，A[i,j]表示第i名运动员在第j天的比赛对手。 因为在输入的数很大时，在C++的运行接口中不能完整的显示出来，故希望通过一种方式把此程序的运行结果导入到WORD或者是TXT檔中，在这里只以导入到TXT中为例。 2.2概要设计 1、定义一个二维数组足够放下所要输出的矩阵，形式如下： #define M 10000 int a[M][M+1],b[M]; 2、按照程序运行顺序，涉及相关的函数： 1）、要有一个主函数，形式如下： main() { …… …… …… tourna(n）； …… …… ｝ 2）、将“分”“和”两部分函数整合起来的函数，即： void tourna(int n) { …… } 3）、合并算法： void makecopy(int n) /*合并算法