分酒问题.doc

xx学院
《数据结构与算法》课程设计
报告书
课程设计题目分酒问题

院系名称计算机科学与技术系
专业(班级)
姓名(学号)
指导教师
完成时间
一、问题分析和任务定义
已知有3个容量分别为3kg ,5kg和8kg且没有刻度的酒瓶,3kg和5kg的瓶子均装满了酒,而8kg的瓶子为空。要求仅用这3个无刻度的瓶子,通过酒在3个瓶子之间的多次转移(添加或倒入其它瓶子中),将酒分成均等的两份。总起来说,就是将开始装在3kg 和5kg酒瓶中的一共8kg的酒(8kg瓶子中为空),最终实现3kg酒瓶为空,5kg和8kg的酒瓶中都装有4kg的酒。此既为该问题的任务。
具体实现时,首先输入的数据为三个瓶子的容量,此处即输入3,5,8;然后输入的数据为酒瓶中开始存放的酒的质量,也即酒瓶中酒的初值,在此题目也已给出确定值3,5,0(即初始状态);最后需要输入的就是我们最终要达到的状态,也就是要实现的结果,即为0,4,4(即最终状态)。每种状态可以看成是一个有向图的一个结点,而每次操作的过程便是一次寻找2个结点之间的路径,如果这2个结点之间有路径那么从起点出发到终点一定存在一条路径到达所以用DFS,关键路径,最短路径均可以解决这一问题。在次我们选择一个适用与更普遍的情况DFS,因为最短路径适用于求分酒次数最少的情况。
接下来的就是输出,因为在这个程序里我们所要经过的状态是由一个专门的函数来建立的,首先状态的建立要是能够实现的,所以要输出状态建立成功的标志,在这个程序里,输入的数据和最终要实现的结果是已给出的,且结果是可实现的,所以必然能产生结果。但当我们输入其它情况时,其中就有可能存在无法实现最终状态和其本身就是要实现的最终状态的情况,这时我们仍然输出其初值,且只输出初值,不再有其它状态和最终状态,就相当于图只有一个入度为零的结点。
二、概要设计和数据结构的选择
根据对问题的分析完成概要设计及数据结构的选择:
1、这个程序里要实现从初始状态到最终状态,中间要经过很多状态,且每个状态都指向下一个状态,我们把每个状态看作一个结点,这样所有的状态在一起也就组成了一个图的结构,我们用邻接表存储这个图,由于该分酒问题无需考虑所经状态所花费的时间或者经历,每种状态都是任意选择的,所以我们选择无权图作为基本的框架——这样做的好处在于不必定义权值域,只需定义一个邻接点域和一个链接邻接表中下一结点的指针域。结构体的具体定义如下:
typedef struct arc_node{ //定义边结点结构体类型
int adjvex; //邻接点域
struct arc_node *next; //链域
}arc_node;
2、图中的每个顶点结点代表着一个状态,所以还需定义一个结构体来存储顶点的信息,定义如下:
typedef struct vex_node{ //顶点结点结构体类型
int status[N]; //状态以数组形式存储
struct arc_node *next; //边结点类型的指针域
}vex_node;
3、对图进行遍历时,对每一个结点访问后,需要对结点进行存储,于是我们定义一个栈数组用于存储,同时需对每个已访问过的结点进行标记,此处我们设置一个标志量,当标志量为0时表示未被访问,为1时表示已访问,定