田径运动会赛程安排-Read.doc

年级 04计算机科学与技术系 （2）班 姓名 余志中 学号 0410101080 PAGE PAGE 16 田径运动会赛程安排 题目：在一个田径运动会上，已知有m个选手参加比赛，运动项目共有n个，这包括若干个诸如100m之类的以个人形式参加的单项和4×100m之类的多人参加的集体项目。另外，每位选手最多可参加3个单项，集体项目则不限制。为使选手能正常比赛，需要对赛程作合理安排。请构造出有关模型和数据结构，设计出合理安排赛程的算法和程序，以使每位选手都能正常地参加比赛，并要求比赛时间尽可能短。 一 问题分析和任务定义 问题分析：首先怎样考虑选手报名情况，我们可以规定有m个选手报名参加了这次田径运动会项目，并给他们从1到m编号代替他们。由于实际情况我们规定有n个田径比赛项目，分别为个人形式参加的单项项目为100米等。多人参加的集体项目有4*100米等项目。由于题目规定每位选手最多可参加3个单项，集体项目不限制。所以我们假设每人参加的项目就用1表示，没参加用0表示。可以用列表来表示相关模型，例如模型如下： 项目 项目m 选手n 100 1500 铅球 跳高 跳远 4*100 8*100 1 0 0 1 0 0 1 1 2 1 0 0 1 0 1 0 3 1 1 0 1 0 0 1 4 0 0 1 0 1 0 0 5 0 0 0 1 1 0 0 由于选手参加的条件不能超过3个单人项目，所以在参加之前先判断是否符合条件，若不符合则对选手排除。 任务定义： 比赛赛程要求时间尽可能的短，所以需要两方面的条件，如下： 项目之间由于比赛场地的限制，不能同时进行。其中能同时进行的要判断哪些能同时进行，而田赛场地不同所以都能同时进行。 在条件（一）的情况下，同一个选手选择了相同项目不能同时进行. 功能： 编号1到100个选手参加7个项目分别是100米， 1500米，铅球，跳高，跳远单人项目和4*100米，8*100米等多人项目。 每个项目参加的人数，而且要判断多人比赛项目报名参加的人数，是否能正确分组。 根据报名表合理安排赛程 输入形式：输入各个项目的报名表，以及跑道的规则（整形） 输出形式：根据报名表输出赛程的安排，其中包括项目的先后顺序，以及项目的参加人数。（整形） 算法的功能：在有限的时间内尽可能短的合理的安排赛程 测试所需的数据和类型：参加人数100人，每个项目所报的人数。 二 概要设计和数据结构的选择 数据结构：由上表可示，可用矩阵来存储表格中的数据，可设如下： 矩阵A[m][n]存储各个结点，各结点包含两个成员 运动项目和整形变量1或0，1表示n参加了m项目，0表没有参加。 主程序的简体流程图: 定义数组并赋值 定义数组并赋值 判断每人参加单项是否符合条件各项参加的人数由跑道规则判断各项能否同时进行 判断每人参加单项是否符合条件 各项参加的人数 由跑道规则判断各项能否同时进行 各项 各项项目参加的人没有重复 能同时进行的项目 能同时进行的项目 排出田径运动会的赛程 排出田径运动会的赛程 三 详细设计和编码 先用结构体存储各个结点的信息，每个选手参加单人项目和多人项目用1表示不参加用零表示各项目的信息，结构体五存储表示项目能同时进行的用tag表示。然后存储各个项目参加的人数和场地的信息，以及每轮比赛的所需时间。再用一个结构体存储每个人的信息包括每人参加的单项和多项以及总的项目数； typedef struct { int n;//n=1为单项，n>1时为集体项目 int data; int T;//参加标志符 }N1; typedef struct { N1 tod[maxsize1]; int sum1;//单项比赛项目数 int sum2;//集体比赛项目数 int sum;//比赛总项目数 }N2; typedef struct { N2 pre[maxsize2];//存放每位选手参加项目信息 int H;//选手个数 }N3; N3 list1; typedef struct { int M1;//项目M1 int M2;//项目M2 int tg;//M1，M2可以同时进行标志 }N4; typedef struct { N4 a[maxsize3];//数组每个元素存放所有可以同时进行的两个项目 int gb; }N5; N5 list2; typedef struct { int pop;//比赛项目 char cd;//比赛项目举行场地 }N6; typedef struct { N6 tod[maxsize1];