《推荐-分酒问题-数据结构与算法课程设计报告》由会员分享，可在线阅读，更多相关《推荐-分酒问题-数据结构与算法课程设计报告（12页珍藏版）》请在金锄头文库上搜索。
1、题目：已知有3个容量分别为3kg，5kg和8kg且没有刻度的酒瓶3kg和5kg的瓶子均装满了酒。而8kg的瓶子为空。现要求仅用这3个酒瓶将这些酒均分为两个4kg，并分别装入5kg和8kg的瓶子中。一、问题分析和任务定义此程序需要完成如下要求：3个没有刻度的酒瓶，容量分别为3kg,5kg,和8kg,3kg和5kg的瓶子装满了酒，8 kg的瓶子为空。不借用其他工具，将这些酒分为两个4kg，并分别装入5kg和8kg的瓶子中。实现本程序需要解决一下几个问题：该问题对应的模型是什么模型建立好以后，采用什么样的存储结构怎样建立模型如何求解，即中心算法思想如何将结果输出本问题的关键在于建立模型，和中心算法思
2、想。模型的描述可以把3个酒杯现在的容量当做一组状态，在求解过程中涉及状态的转化，可以用图模型求解。把每次可分的状态抽象为一个图节点，利用图的相关知识去求解。中心算法思想图的初始状态为（053），最终状态为（440），本题的求解过程就是把（053）变成（440），也就是找到一条路径，路径的起始点为（053），终点为（440）。因此可以采用图的深度优先搜索遍历。但本题搜索的起点已经给定。二、概要设计和数据结构的选择 设计本题算法的构思如下： （1）为搜索除符合条件的简单路径，需要按深度优先搜索方式进行遍历。因此，求解算法应是深度遍历算法的变形形式，因而也是递归是形式的算法。 由于要求遍历序列中的各
3、结点按次序构成一条简单路径，因此，本算法与深度遍历算法有明显的不同:并非任意选择的起点和访问次序都能得到解。而本题的起点和终点是确定的。既然要在求解过程中进行试探，则需要记录试探的中间状态; 某顶点是否在当前试探路径中，已经试探的各顶点和当前试探顶点的信息。将所用的变量及有关参数设置如下： 用邻接链表存储所得图的结构，链表用两个结构体表示，(struct arc_node ，struct vex_node),其中每个链表的头保存在一个数组中。 用布尔数组visitedMAX_SIZE表示各状态顶点是否在当前路径中（初始状态全为false). 用数组A存储当前路径中的个顶点。 (4)既然是试探型
4、求解，则需要对当前顶点v0的每个邻接点进行试探（程序中用sv0.next表示),试探由v0经sv0.next往下是否可以得到解，每个sv0.next都有可能成功(指现在可以放在路径上，这包括暂时的和最终的)与失败的（指状态转化不能完成),，对此应分别做不同的处理： 若试探成功，则应将sv0.next放在路径中，。然后再由其往下求解。 若不成功，则应恢复sv0.next的用关信息，以使sv0.next在试探其他路径中成为可选的试探点。推荐精选 （5）为了能求出解以及所有可能的解，需要做如下的工作： 选择路径：本题中的起点已经限定，即start_vex=0 5 3 搜索路径：从v往下搜索时，应依次
5、选择v的所有不在当前路径中的邻接点往下搜索。 为此，需要有这方面的保证：应在试探某顶点之后并在换下一个试探顶点的前恢复该顶点的有关状态，以使其重新成为可选择的顶点。本题的模型已经抽象成了图，所以可以用邻接表来存储图。邻接表数据类型描述如下：typedef struct node /边节点 int adjvex;/邻接点的位置 node *next;/指向下一个节点 ARCNODE;/邻接表中的结点类型 typedef struct /顶点节点 int vexdataN; /各酒杯的存储状态 ARCNODE *next;/指向下一个邻接点 VEXNODE;/表头结点类型VEXNODE sMAX_
6、SIZES; /状态表除了邻接表外，本题还需要其他的辅助存储结构深度优先搜索是一个递归过程。需要一个visitedn数组来记录当前定点是否已访问过，若访问过，数组元素的值为“1”，若未访问过，数组元素的值“0”。因此可以定义：bool visitedn;每求出一个解要把当前路径输出，用数组Atop来记录遍历过程中顶点其他变量的设置：#define N 3#define MAX-SIZE 100int A;/存放路径int top=0;/数组A中的个数int fullN;/各酒杯的最大容量int partN;/各酒杯的当前容量int endN;/最终状态int sta;/状态表当前状态数int
7、sum=0;/所有解的个数int end_vex;/结束的状态点三、详细设计和编码首先初始化各酒杯的最大容量for(i=0;iN;i+) scanf(%d,&fulli);初始化起点状态for(i=0;iN;i+) scanf(%d,&s0.vexdatai);给出要求的终点推荐精选for(i=0;iN;i+) scanf(%d,&endi);下面对邻接表和状态表的建立进行分析和说明将顶点为number的值即snumber.vexdata的值赋给part，调用jisuan(number)函数，依次求出顶点0的邻接点，将求出的邻接点保存到状态表中，并加入到邻接表中。令number=number+
8、1,重复上面的步骤，求出所有顶点的邻接点，得到一个完整的状态表和邻接表。求顶点邻接点的过程如下：通过两个for循环来改变酒杯的下标和比较。 for(i=0;iN;i+) for(j=0;j=N为止。然后是i=i+1,重复上面步骤，直至i=N为止。这样就把顶点number所有的邻接点都求出来了，并且加入到了状态表和邻接表中。保存状态的过程如下：for(i=0;iadjvex将sv0.next放在数组A中,并置visitedsv0.next为true，然后以sv0.nex为起点往下搜索，直到搜索到终点4 4 0或者不满足循环条件为止 恢复：通过A-top将sv0.next恢复为不在当前的路径中，并
9、置visitedv0=false以使其在试探其他路径时可用。每求出一种解就调用prtf()函数，进行输出。输出过程如下： 路径存储在数组A中，A中存储的是路径中的各顶点，通过循环for(i=0;itop;i+)来控制输出，没执行一次for循环就输出路径中的一个顶点；令j=Ai,即用j记录顶点在路径中的位置，用来输出顶点Ai对应的状态。通过for(k=0;kN;k+)printf(%d,sj.vexdatak);来输出该状态，当把数组A中的路径输出完以后就得到了一种解。在dfs()函数中每求出一种解就调用一次prtf()函数，当遍历结束后，所有解也已全部求出并输出。程序完成。四、 上机调试1、 语法错误机修改：算法中定义了很多全局变
