【精品】分酒问题-数据结构与算法课程设计报告.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),其中每个链表的头保存在一个数组中。
用布尔数组visited[MAX_SIZE]表示各状态顶点是否在当前路径中(初始状态全为false).
用数组A存储当前路径中的个顶点。
(4)既然是试探型求解,则需要对当前顶点v0的每个邻接点进行试探(程序中用s[v0].next表示),试探由v0经s[v0].next往下是否可以得到解,每个s[v0].next都有可能成功(指现在可以放在路径上,这包括暂时的和最终的)与失败的(指状态转化不能完成),,对此应分别做不同的处理:
若试探成功,则应将s[v0].next放在路径中,。然后再由其往下求解。
‚若不成功,则应恢复s[v0].next的用关信息,以使s[v0].next在试探其他路径中成为可选的试探点。
(5)为了能求出解以及所有可能的解,需要做如下的工作:
选择路径:本题中的起点已经限定,即start_vex={0 5 3}
‚搜索路径:从v往下搜索时,应依次选择v的所有不在当前路径中的邻接点往下搜索。
为此,需要有这方面的保证:应在试探某顶点之后并在换下一个试探顶点的前恢复该顶点的有关状态,以使其重新成为可选择的顶点。
本题的模型已经抽象成了图,所以可以用邻接表来存储图。
邻接表数据类型描述如下:
typedef struct node //边节点
{
int adjvex;//邻接点的位置
node *next;//指向下一个节点
}ODE;//邻接表中的结点类型
typedef struct //顶点节点
{
int vexdata[N]; //各酒杯的存储状态
ODE *next;//指向下一个邻接点
}VEXNODE;//表头结点类型
VEXNODE s[MAX_SIZES]; //状态表
除了邻接表外,本题还需要其他的辅助存储结构
深度优先搜索是一个递归过程。需要一个visited[n]数组来记录当前定点是否已访问过,若访问过,数组元素的值为“1”,若未访问过,数组元素的值“0”。因此可以定义:bool visited[n];
每求出一个解要把当前路径输出,用数组A[top]来记录遍历过程中顶点
其他变量的设置:
#define N 3
#define MAX-SIZE 100
int A[];//存放路径
int top=0;//数组A[]中的个数
int full[N];//各酒杯的最大容量
int part[N];//各酒杯的当前容量
int end[N];//最终状态
int sta;//状态表当前状态数
int sum=0;//所有解的个数
int end_vex;//结束的状态点
三、详细