分酒问题-数据结构与算法课程设计报告.doc

题目：已知有3个容量分别为3kg，5kg和8kg且没有刻度的酒瓶3kg和5kg的瓶子均装满了酒。而8kg的瓶子为空。现要求仅用这3个酒瓶将这些酒均分为两个4kg，并分别装入5kg和8kg的瓶子中。一、问题分析和任务定义此程序需要完成如下要求：3个没有刻度的酒瓶，容量分别为3kg,5kg,和8kg,3kg和5kg的瓶子装满了酒，8 kg的瓶子为空。不借用其他工具，将这些酒分为两个4kg，并分别装入5kg和8kg的瓶子中。实现本程序需要解决一下几个问题：该问题对应的模型是什么模型建立好以后，采用什么样的存储结构怎样建立模型如何求解，即中心算法思想如何将结果输出本问题的关键在于建立模型，和中心算法思想。模型的描述可以把3个酒杯现在的容量当做一组状态，在求解过程中涉及状态的转化，可以用图模型求解。把每次可分的状态抽象为一个图节点，利用图的相关知识去求解。中心算法思想图的初始状态为（053），最终状态为（440），本题的求解过程就是把（053）变成（440），也就是找到一条路径，路径的起始点为（053），终点为（440）。因此可以采用图的深度优先搜索遍历。但本题搜索的起点已经给定。二、概要设计和数据结构的选择 设计本题算法的构思如下： （1）为搜索除符合条件的简单路径，需要按深度优先搜索方式进行遍历。因此，求解算法应是深度遍历算法的变形形式，因而也是递归是形式的算法。 由于要求遍历序列中的各结点按次序构成一条简单路径，因此，本算法与深度遍历算法有明显的不同:并非任意选择的起点和访问次序都能得到解。而本题的起点和终点是确定的。既然要在求解过程中进行试探，则需要记录试探的中间状态; 某顶点是否在当前试探路径中，已经试探的各顶点和当前试探顶点的信息。将所用的变量及有关参数设置如下： 用邻接链表存储所得图的结构，链表用两个结构体表示，(struct arc_node ，struct vex_node),其中每个链表的头保存在一个数组中。 用布尔数组visitedMAX_SIZE表示各状态顶点是否在当前路径中（初始状态全为false). 用数组A存储当前路径中的个顶点。 (4)既然是试探型求解，则需要对当前顶点v0的每个邻接点进行试探（程序中用sv0.next表示),试探由v0经sv0.next往下是否可以得到解，每个sv0.next都有可能成功(指现在可以放在路径上，这包括暂时的和最终的)与失败的（指状态转化不能完成),，对此应分别做不同的处理： 若试探成功，则应将sv0.next放在路径中，。然后再由其往下求解。 若不成功，则应恢复sv0.next的用关信息，以使sv0.next在试探其他路径中成为可选的试探点。 （5）为了能求出解以及所有可能的解，需要做如下的工作： 选择路径：本题中的起点已经限定，即start_vex=0 5 3 搜索路径：从v往下搜索时，应依次选择v的所有不在当前路径中的邻接点往下搜索。 为此，需要有这方面的保证：应在试探某顶点之后并在换下一个试探顶点的前恢复该顶点的有关状态，以使其重新成为可选择的顶点。本题的模型已经抽象成了图，所以可以用邻接表来存储图。邻接表数据类型描述如下：typedef struct node /边节点 int adjvex;/邻接点的位置 node *next;/指向下一个节点 ARCNODE;/邻接表中的结点类型 typedef struct /顶点节点 int vexdataN; /各酒杯的存储状态 ARCNODE *next;/指向下一个邻接点 VEXNODE;/表头结点类型VEXNODE sMAX_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 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+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恢复为不在当前的路径中，并置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、 语法错误机修改：算法中定义了很多全局变量，在完成本程序的过程中，有些全局变量忘了赋值，这样系统就赋给它一个随机值，影响程序的正确性，发现错误后及时给它赋值，例如，作为数组下标的top，刚一个开始没有赋值，在输出路径是，全部都是随机数，在定义是令top=0即可。语法的主要问题在于子函数定义，括号的配对，尤其是括号的配对，在有些地方使用的循环比较多，这样就会产生括号配对的错误，细心的检查，改错就行了。还有一些输入错误，相应的将其解决。2、 逻辑问题修改及调整：在jisuan函数中，通过两条for语句来控制酒杯的下标和比较，for(i=0;iN;i+)/编号为i的酒杯与其他酒杯交换 for(j=0;jN;j+) if(j=i) continue;/同一酒杯，无法变换没有if(j=i) continue 这条语句，造成了时间上的浪费。因为如果i=j的话，两者是同一个酒杯无需比较，在人工运行算法的过程中，发现了该问题，加上if语句即可。在jisuan()函数中每求出一种新的状态就调用save（）函数，若该状态存在就仅加入到邻接表；若该状态不存在，则不仅要加入到邻接表还要加入到状态表。在一开始的时候没有判断该状态是否已经存在的语句for(i=0;ista)/将该状态加入状态表 sta+;for(int j=0;jN;j+)ssta.vexdataj=partj; ssta.next=NULL; if(!compare(part,end) end_vex=sta;/该状态是最终状态，记住在状态表中的位置 不管该状态是否存在都会重新保存，这样就会造成时间上的浪费。加上上面的判断语句就行了。在深度优先搜索遍历函数中，首先是判断该节点是否已访问过，一开始是用while（!visitedv0），这样就会造成死循环，程序一直在执行dfs()函数，在屏幕上会看到不停的输出那15种解。这是由于对深度优先搜索遍历算法理解有问题，深度优先搜索遍历采用了递归的思想，虽然让程序简单了，但增加了理解的难度。将while（!visitedv0）改成if(!visitedv0)即可。3、 时间、空间性能分析：本算法定义了很多全局变量，而且是三个杯子，不管是全局变量中还是局部变量中都定义了许多数组，增加了空间复杂度，。由于本算法所有问题的求解都是围绕三个杯子之间的转换进行的，而且函数之间都是嵌套调用，全局变量的使用在一定程度上降低了空间复杂度。由于采用图的模型，图中顶点和顶点之间的关系比较复杂，要建立状态表建立存储所有的状态，还要建立邻接表，在遍历过程中要有记录路径的数组，这些都增加了空间复杂度。三个杯子之间的转化，不能借用其他工具，只能在它们之间进行变环，这样就增加了时间复杂度，要计算出三个杯子所有可能的状态，在计算过程中，要用到双重循环，每建立一种新的状态就要调用一次save（）函数，save（）函数中又调用了compare()函数，这样的嵌套调用再加上循环语句的大量使用，使算法的时间复杂度进一步增加。 在深度优先搜索遍历算法，用了递归的思想，大大增加了时间复杂度4、 经验和体会：刚一开始拿到题目确实有种无从下手的感觉，虽然在任务书中提示了用回溯和递归算法求解本问题，但不知道该采用什么样的模型。经过分析可知就是把053变成440就是找到从053到440的路径，这和图的深度优先搜索遍历很相像，而且回溯算法就是在图的遍历中讲到的，所以我就采用了图的模型，用邻接表存储，建立状态表，用图的深度优先搜索遍历求出所有解。在课程设计过程中，我发现我没看一次深度优先搜索遍历，我对这个算法的理解就加深一步，所以我觉得我现在只是把书上的表面知识学会了，这本书中蕴含的更深的东西还值得我花更多的时间去学习。独立思考很重要，跟别人交流也很重要。在我和别人交流的时候，开阔了我的思维空间，很多原先我没想到的东西一下子就蹦出来了，而且能填补我知识的空白。跟老师交流就更重要了，以老师的知识层面和对问题的见解，他的想法具有很强的针对性和可行性。五、 用户使用说明本程序运行过程中带有提示性语句，而且本程序的输入比较简单，就是固定的几个数：首先输入个酒杯的最大容量：8 5 3，然后输入个酒杯当前的状态：0 5 3，最后输入要求解的最终状态：4 4 0。按回车键，会输出状态表中的状态和所有解。六、测试结果数据说明：本题的数据都是固定的，首先输入各酒杯的最大容积：8 5 3，然后输入当前的容积：0 5 3，再输入要求解的最终状态：4 4 0。按回车键程序输出状态表中的所有状态和所有解。七、 附录#include stdio.h#include string.h#define N 3 /酒杯数#define MAX_SIZES 100 /状态表中的最大状态数 typedef struct node /边节点 int adjvex;/邻接点的位置 node *next;/指向下一个节点 ARCNODE;/邻接表中的结点类型 typedef struct /顶点节点 int vexdataN; /各酒杯的存储状态 ARCNODE *next;/指向下一个邻接点 VEXNODE;/表头结点类型 int AMAX_SIZES;/用于存储路径的数组 int top=0;/数组中的个数 int fullN;/各酒杯的最大容量 int partN;/各酒杯的当前容量 int endN;/最终状态 VEXNODE sMAX_SIZES; /状态表 int sta;/状态表当前状态数 int sum=0;/所有解的个数 int end_vex;/结束的状态点 bool visitedMAX_SIZES;/标记状态是否被访问 bool compare(int a,int b) /比较状态 int i; for(i=0;iN;i+) if(ai!=bi) return true;/两数组不相等，返回true return false;/相等，返回false void save(int number) /保存状态,如果状态存在则仅仅加入领接表,如果不存在则加入状态表，并加入邻接表 ARCNODE *p; int i; for(i=0;ista)/将该状态加入状态表 sta+;for(int j=0;jadjvex=i; p-next=snumber.next; snumber.next=p;/加入邻接表 void jisuan(int number)/求出某状态的所有邻接点 int i,j,I,J; for(i=0;iN;i+)/编号为i的酒杯与其他酒杯交换 for(j=0;jN;j+) if(j=i) continue;/同一酒杯，无法变换 I=parti;/保存i酒杯的当前的容量 J=fullj-partj;/j酒杯的空闲量 if(I=J)/若i酒杯的当前容量小于等于j酒杯的空闲量 parti=0; partj+=I;/将i酒杯的酒倒向j酒杯 save(number);/调用save()函数，保存当前的状态 parti=I; partj-=I;/恢复各酒杯的原始状态 else/若i酒杯的当前容量大于j酒杯的空闲量 parti-=J; partj=fullj;/把j酒杯加满 save(number);/调用save()函数，保存当前的状态 parti+=J; partj-=J;/恢复各酒杯的原始状态 void create()/建立状态的函数 int number,i;printf(输入各个酒杯的容积:); for(i=0;iN;i+) scanf(%d,&fulli);printf(输入对应酒杯的起始状态:); for(i=0;iN;i+) scanf(%d,&s0.vexdatai);/初始状态即状态表中的s0 printf(输入对应酒杯的最终状态:); for(i=0;iN;i+) scanf(%d,&endi);/所求的状态 number=