单循环赛赛程安排

单循环赛赛程安排单循环赛赛程安排：在有 n 个选手 P 1 ,P 2 ,P 3 ,… ,P n 参加的单循环赛中，每对选手之间非胜即负。现要求求出一个选手序列 P 1 ' ,P 2 ' ,P 3 ' ,… ,P n ', 使其满足 P i ' 胜 P i+ 1 ' (i=1,… ,n-1) 。编写合理的算法尽量合理的安排赛程。能够满足题目中最后一个条件。：（ 1 ）模型表示：由于仅涉及到 n 个选手，并且这些选手之间的关系仅是胜负关系，因此可用图来表示，由于是赛程安排问题，所以又可用到深度优先遍历的思想。为搜...

单循环赛赛程安排：在有 n 个选手 P 1 ,P 2 ,P 3 ,… ,P n 参加的单循环赛中，每对选手之间非胜即负。现要求求出一个选手序列 P 1 ' ,P 2 ' ,P 3 ' ,… ,P n ', 使其满足 P i ' 胜 P i+ 1 ' (i=1,… ,n-1) 。编写合理的算法尽量合理的安排赛程。能够满足题目中最后一个条件。：（ 1 ）模型表示：由于仅涉及到 n 个选手，并且这些选手之间的关系仅是胜负关系，因此可用图来表示，由于是赛程安排问题，所以又可用到深度优先遍历的思想。为搜索出符合条件的简单路径，需按深度优先搜索方式进行遍历。因此求解算法应是深度遍历算法的变形形式，也应是递归形式的算法。用顶点表示选手。用弧表示选手之间的胜负关系：当且仅当 P i 胜 P j 时，有从顶点 i 到 j 的一条弧。在这种表示下，本题问题变成了如下的问题：在有向图中求解出一条包含所有顶点的简单路径的问题。下图所示为一个有 8 个选手的问题的一个示例。其中的一个解为 1,2,3,4,8,6,5,7 。图1。构思：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。当初始了位置后，将利用递归的思想按照类似的遍历对棋盘进行遍历，既然要在求解过程中进行试探，则需要记录试探的中间状态：某顶点是否在当前试探的路径中，已经试探的各顶点的次序，当前正在试探的顶点等。既然是试探型求解，则需对当前顶点 v 的每个邻接点 ( 不妨用 w 表示 ) 进行试探，试探由 v 经 w 往下是否可以得到解。每个 w 都可能有成功（指现在可以将该顶点放在路径上，这包括暂时的和最终的）与失败（指此路不通）两种情况。 . （1）：设计本题算法的构思如下：为搜索出符合条件的简单路径，需按深度优先搜索方式进行遍历。因此求解算法应是深度遍历算法的变形形式，也应是递归形式的算法。由于要求遍历序列中的各结点按次序构成一条简单路径，因此算法与深度遍历算法有明显的不同：并非任意选择的起点和访问次序都能得到解。由教科书可知，图的存储结构可有多种，其中最常用的是邻接矩阵和邻接表两种，两者各有其特点。具体采用什么结构取决于问题本身的要求。而这些又是事先难以确定的。这就要求在求解过程中进行试探：试探起点以及访问次序。既然要在求解过程中进行试探，则需要记录试探的中间状态：（2）某顶点是否在当前试探的路径中，已经试探的各顶点的次序，当前正在试探的顶点等。将所用到的变量及有关参数设置如下：设图为 g ；设当前试探路径中最后的顶点号为 v ； v 在试探路径中的序号为 k ；用布尔型数组 visited[n+1] 表示各顶点是否在当前试探的路径中（初值为全 FALSE ）；用数组 B[n+1] 存储当前路径中的各顶点（在前 k 个元素中，事实上应是栈）。既然是试探型求解，则需对当前顶点 v 的每个邻接点 ( 不妨用 w 表示 ) 进行试探，试探由 v 经 w 往下是否可以得到解。每个 w 都可能有成功（指现在可以将该顶点放在路径上，这包括暂时的和最终的）与失败（指此路不通）两种情况，对此应分别作不同的处理： a. 若试探成功，则应将 w 放入路径中，并置相应的状态值。然后再由 w 往下求解。 b. 若不成功，则应恢复 w 的有关信息，以使 w 在试探其它路径时成为可选顶点。为了能求出解以及所有可能的解，需要作如下两方面的工作： a. 选择起点：应以每个顶点为起点进行搜索。 b. 搜索路径：在从 v 往下搜索时，应依次选择 v 的所有不在当前试探路径中的邻接点往下搜索。 . 为此，需要有这方面的保证：应在试探某顶点 w 后并在换下一个试探顶点前恢复 w 的有关状态，以使其仍为可选择的顶点。（1）首先定义几个结构体来记录相关数据和其它东西： struct ArcNode { int adjvex; //该弧所在的顶点位置 ArcNode *nextarc; //指向下一条弧 }; /* 表头结点定义*/ struct VNode { VertexType data; //顶点信息 ArcNode *firstarc; //指向第一条弧 }; typedef VNode AdjList[MAX_VERTEX_NUM]; /*图定义*/ struct ALGraph { AdjList vertices; int vexnum,arcnum; }; ALGraph G; （2）由上述讨论得本算法的基本思想： a. 若 k=n ，则说明已经求得一解，因此可输出结果，并结束本次调用。 b. 若 k>G.vexnum; //选手数N cout<<"边数:"<>G.arcnum; //选手比赛次数,由于是单循环肯定是N*(N-1)*/2盘比赛 /* 初始化 */ for(i=1;i<=G.vexnum;i++) { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; } for(k=0;k>i>>j; p=new ArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } } void Disp(ALGraph G) { int i; ArcNode *p; cout<<"输出图为:"<adjvex<<")"; p=p->nextarc; } cout<adjvex]) dfs(p->adjvex); p=p->nextarc; } if(count==G.vexnum) return true; } void main() { int visited[20]; int v; char flag;//是否继续搜索 bool isshow=true;//判断是否满足要求 CreateDG(G); Disp(G); for(int i=1;i>v;cout<>flag; if(flag=='N') { break; } } cout<<"程序结束!"< #include typedef int VertexType ; //顶点数据类型 #define MAX_VERTEX_NUM 20 //最大顶点数 #define MAX_EDGE_NUM 40 //最大边数 int visited[MAX_VERTEX_NUM]; //访问标志数组 /*结点类型*/ struct ArcNode { int adjvex; //该弧所在的顶点位置 ArcNode *nextarc; //指向下一条弧 }; /* 表头结点定义*/ struct VNode { VertexType data; //顶点信息 ArcNode *firstarc; //指向第一条弧 }; typedef VNode AdjList[MAX_VERTEX_NUM]; /*图定义*/ struct ALGraph { AdjList vertices; int vexnum,arcnum; }; ALGraph G; void CreateDG(ALGraph &G) { int i,j,k; ArcNode *p; cout<<"创建一个有向图:"<>G.vexnum; //选手数N cout<<"边数:"<>G.arcnum; //选手比赛次数,由于是单循环肯定是N*(N-1)*/2盘比赛 /* 初始化 */ for(i=1;i<=G.vexnum;i++) { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; } for(k=0;k>i>>j; p=new ArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } } void Disp(ALGraph G) { int i; ArcNode *p; cout<<"输出图为:"<adjvex<<")"; p=p->nextarc; } cout<adjvex]) dfs(p->adjvex); p=p->nextarc; } if(count==G.vexnum) return true; } void main() { int visited[20]; int v; char flag;//是否继续搜索 bool isshow=true;//判断是否满足要求 CreateDG(G); Disp(G); for(int i=1;i>v;cout<>flag; if(flag=='N') { break; } } cout<<"程序结束!"< 报告的质量（30%）和课程设计过程中的工作态度（20%）等综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。优秀者人数一般不超过总人数的20%，成绩不及格者需重新补做课程设计。课程设计报告文档统一为A4纸打印，页边距上下2.54cm、左右3.17cm，正文为宋体小四，行距为固定值18 磅，各小节标题字体加粗；文档中的图应有图号、表应有表名。

                    本文档为【单循环赛赛程安排】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

单循环赛赛程安排

你可能还喜欢