单循环赛赛程安排

单循环赛赛程安排 ：在有 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<<"程序结束!"<