单循环赛中选手胜负序列求解问题

单循环赛中选手胜负序列求解问 XX学院 计算机科学与技术系 课程报告 2008 ,2009 学年第 2 学期 课程 数据结构与算法 课程设计名称 单循环赛中选手胜负序列求解问题 学生姓名 学号 专业班级 指导教师 2009 年 2 月 题目:单循环赛中选手胜负序列求解问题 一、 问题和任务定义 单循环赛: 单循环赛，是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。如果参赛球队不多，而且时间和场地都有保证，通常都采用这种竞赛方法。 单循环比赛轮次的计算 本题可有两种不同的理解，一个是按比赛的积分排名产生胜负序列，第二个是按比赛过程中各个选手间的胜负关系产生胜负序列，下面具体分析: (1) 按比赛中积分排名产生胜负序列: 比赛可规定各个选手之间均遭遇且只遭遇一次，比赛时胜方得1分，负方不得分，在比赛结束时按积分排名进行排序，由此产生胜负序列关系。 (2) 按比赛过程中各个选手间的胜负关系产生胜负序列: 该种方法是以过程中的胜负为标准从而产生胜负序列，当然，这种胜负序列很大的可能性是不唯一的，本程序按课程设计任务书的要求，仅求出其中的一个胜负序列关系。 二、 数据结构的选择和概要设计 (1)对于第一种情况，本实验选用的数据结构是类。将选手的编号、积分、以及胜负处理等等封装在类中。胜负序列的求解转化为了对所有选手的积分的排序问题。 (2)对于第二种情况，本实验采用的数据结构是有向图，每个选手视为一个点，每条边视为选手之间的胜负关系，箭头指向的一方为失败方。所以胜负序列的求解就转化为了图的深度遍历问题。为了便于深度遍历有向图，采用的存储结构为图的临街矩阵存储。 三、 详细设计和编码 (1)就第一种情况而言，较为简单，设计一个选手类Player，私有成员包括分数score和选手编号num。公有成员包括构造数Player()，设置编号void setnum(int num1)，获胜处理函数void win()，失败处理函数void fail()，返回编号函数int getnum()，返回积分函数int getscore()。类的定义如下: class player//选手类 { private: int score;//积分 int num;//参赛编号 public: player() {} void setnum(int num1)//设置编号 { num = num1; score = 0; } void win()//胜利 { score ++; } void fail()//失败 { score --; } int getscore()//获取分数 { return score; } int getnum()//获取编号 { return num; } }; 这些代码定义为头文件 score.h 在程序的初始化时根据输入的选手数量n，动态申请一个选手类的数组Player[n]。依次输入第一个选手和后面的n-1个选手的胜负关系，第二个选手和后面n-2个选手的胜负关系„„第n-1个选手和第n个选手的胜负关系。W(w)示胜利，F(f)表示失败。 在选手的胜负关系输入完毕后通过getscore()返回各个选手的积分对各个选手的积分进行排序，从而得到选手的胜负序列关系。 (2)就第二种情况而言，较为复杂，使用的图，即将比赛过程中的各个选手间的胜负关系转化为一个有向图且是连同的完全有向图。 模型表示 :由于仅涉及到 n 个选手，并且这些选手之间的关系仅是胜负关系，因此可用图来表示，用顶点表示选手， 用弧表示选手之间的胜负关系:当且仅当 P i 胜 P j 时，有从顶点 i 到 j 的一条弧。 在这种表示下，本题问题变成了如下的问题: 在有向图中求解出一条包含所有顶点的简单路径的问题。 下图所示为一个有 8 个选手的问题的一个示例。其中的一个解为 1,2,3,4,8,6,5,7 。 算法设计 :设计本题算法的构思如下: 为搜索出符合条件的简单路径，需按深度优先搜索方式进行遍历。因此求解算法应 是深度遍历算法的变形形式 ，也应是递归形式的算法。 由于要求遍历序列中的各结点按次序构成一条简单路径，因此算法与深度遍历算法有明显的不同:并非任意选择的起点和访问次序都能得到解。而这些又是事先难以确定的。这就要求在求解过程中进行试探: 试探起点以及访问次序 。 既然要在求解过程中进行试探，则 需要记录试探的中间状态 :某顶点是否在当前试探的路径中，已经试探的各顶点的次序，当前正在试探的顶点等。将所用到的变量及有关参数设置如下: 设置MAX_POINT_NUM 100为最大选手数量。路径结构WAY，包含路径上选手在序列数组中的小标k和选手序列way[MAX_POINT_NUM]，都是整型。设置结构体Graph为图的存储结构，包含选手的人数n和存储矩阵edges[MAX_POINT_NUM][MAX_POINT_NUM]，为邻接存储矩阵，即本程序采用临街矩阵作为图的存储结构。 设图为 g ，设当前试探路径中最后的顶点号为 i ， i 在试探路径中的序号为 k，用整型数组 visited[n] 表示各顶点是否在当前试探的路径中(初值为全0 )，用路径w中的 way[MAX_POINT_NUM] 存储当前路径中的各顶点(在前 k 个元素中，事实上应是栈)。 既然是试探型求解，则需对当前顶点i的每个邻接点 ( 不妨用j 表示 ) 进行试探，试探由 i 经 j 往下是否可以得到解。每个 i 都可能有成功(指现在可以将该顶点放在路径上，这包括暂时的和最终的)与失败(指此路不通)两种情况，对此应分别作不同的处理: a. 若试探成功，则应将j 放入路径中，并置相应的状态值。然后再由j 往下求解。 b. 若不成功，则应恢复 j 的有关信息，以使j在试探其它路径时成为可选顶点。 为了能求出解以及所有可能的解，需要作如下两方面的工作: a. 选择起点:应以每个顶点为起点进行搜索。 b. 搜索路径:在从 i 往下搜索时，应依次选择 i 的所有不在当前试探路径中的邻接点往下搜索。 为此，需要有这方面的保证:应在试探某顶点 j 后并在换下一个试探顶点前恢复 j 的有关状态，以使其仍为可选择的顶点。 由上述讨论得本算法的基本思想: a. 若 k=n-1 ，则说明已经求得一解，因此可输出结果，并结束本次调用。 b. 若 kn = g->e = n; for(i = 0;i < n;i ++) { for(j = 0;j edges[i][j] = 0; } for(i = 0;i < n;i ++)//输入选手之间的胜负关系 { cout<<"请输入第"<>tem; if(tem == 'w'||tem == 'W')//胜，则将胜负关系插入现有的邻接表中 g->edges[i][j] = 1; else if(tem == 'f'||tem == 'F')//负,存储相应的胜负关系 g->edges[j][i] = 1; else { cout<<"错误输入,请重新输入其后的胜负关系"<edges[i][j]<<" "; cout<edges[i][j] == 1) flag = 1; if(!flag) Pop(i); return flag; } void Search(Graph *g,int i,int n)//深度搜索函数 { if(w.k == n - 1)//已经搜索完毕 return; int j; for(j = 0;j < n;j ++)//i为当前节点，j为i的邻接结点,一次搜索i的各个合 适的邻接结点 { if(g->edges[i][j] == 1 && visited[j] == 0)//找到合适的路径 { if(Test(g,j,n))//试探成功，则递归搜索 Search(g,j,n); else continue;//试探失败，则从i的下一个邻接点试探 } } } void Init() { w.k = 0; for(int i = 0;i < MAX_POINT_NUM;i ++) { w.way[i] = -1; visited[i] = 0; } } void Process()//主函数 { int n; cout<<"请输入参赛人数:"; cin>>n; Graph *g = Creat_Graph(n); Print_Graph(g,n); cout<<"胜负序列如下:"<n = g->e = n; for(i = 0;i < n;i ++) { for(j = 0;j edges[i][j] = 0; } for(i = 0;i < n;i ++)//输入选手之间的胜负关系 { cout<<"请输入第"<>tem; if(tem == 'w'||tem == 'W')//胜，则将胜负关系插入现有的邻接表中 g->edges[i][j] = 1; else if(tem == 'f'||tem == 'F')//负,存储相应的胜负关系 g->edges[j][i] = 1; else { cout<<"错误输入,请重新输入其后的胜负关系"<edges[i][j]<<" "; cout<edges[i][j] == 1) flag = 1; if(!flag) Pop(i); return flag; } void Search(Graph *g,int i,int n)//深度搜索函数 { if(w.k == n - 1)//已经搜索完毕 return; int j; for(j = 0;j < n;j ++)//i为当前节点，j为i的邻接结点,一次搜索i的各个合适的 邻接结点 { if(g->edges[i][j] == 1 && visited[j] == 0)//找到合适的路径 { if(Test(g,j,n))//试探成功，则递归搜索 Search(g,j,n); else continue;//试探失败，则从i的下一个邻接点试探 } } } void Init() { w.k = 0; for(int i = 0;i < MAX_POINT_NUM;i ++) { w.way[i] = -1; visited[i] = 0; } } void Process()//主函数 { int n; cout<<"请输入参赛人数:"; cin>>n; Graph *g = Creat_Graph(n); Print_Graph(g,n); cout<<"胜负序列如下:"<>n; player *pl = new player[n],temp; for(i = 0;i < n;i ++) { pl[i].setnum(i); } for(i = 0;i < n-1;i ++) { cout<<"请输入第"<>tem; if(tem == 'w'||tem == 'W') { pl[i].win(); pl[j].fail(); } else if(tem == 'f'||tem == 'F') { pl[i].win(); pl[j].fail(); } else { cout<<"错误输入,请重新输入其后的胜负关系"< "; } cout<<"\n分数:"; for(i = 0;i < n;i ++) { cout< "; } cout<