数据结构大作业――分油问题

目录内容摘要………………………………………………………………………………………2设计任务与技术要求………………………………………………………………………３总体设计方案…………………………………………………………………………………3数据结构和算法的设计………………………………………………………………………3程序清单………………………………………………………………………………………4程序测试与调试………………………………………………………………………………8结论与体会……………………………………………………………………………………91内容摘要【内容摘要】有三个大小不等的，没有刻度的油桶，分别能装x，y，z公斤油。开始时，第一个油桶装满油，另外两个油桶为空，要求找出一种步骤最少的分油方法，在某一个油桶上分出targ公斤油。输入：三个油桶的装油量（例如分别是80、50、30公斤）和需要分出的油量targ公斤（例如为40公斤）；输出：分油过程和分油结果。【英文摘要】Therearethreedifferentsizes,thereisnocalibrationofthetank,respectively,canholdx,y,zkgofoil.Thebeginningofthefirstoildrumsfilledwithoil,theothertwoemptyoildrumstorequireatleastasteptoidentifythesub-oilmethod,inaseparatebarrelsofoiltargkg.Input:threeoftheinstalledfueltank(forexample,80,50,30kg,respectively)andtheneedtoseparatetheoiltargkg(forexample,40kg);Output:sub-processesandsub-oil-oilresults.2一、实验内容概述(设计任务与技术要求)本实验是常见的分油问题。有三个大小不等，没有刻度的油桶。让第一个装满油，另两个为空，要求找出一种步骤最少的方法，分出targ公斤油。通过while语句实现输入的数据满足题目所要求的条件。可以通过各个油桶的容量来分倒。二、实验目的概述(总体设计方案)1.掌握数组和switch，case语句的运用方法，以及它们的基本操作。2.掌握菜单驱动程序的运用，使程序变得更灵活。3.掌握一些基本的函数，以及它们在实际问题中的应用。三、解题思路的描述(数据结构和算法的设计)：每次拿起3个桶中任意一个时至多有2种倒法选择，可采用递归建树（3×2＝6叉）来解决，建完树，答案也就出来了。关于对建树过程中出现已有结点的处理，它可能出现在非最佳答案的尾部，也可能出现在最佳答案的头部所以任意释放可能导致最佳答案流失，但不释放又会导致陷入无限递归。释放原则：应该先判断当前结点跟已有结点哪个更佳，如果当前结点所在层级比已有结点层级低则向查询链表中插入新的结点，再删除原结点，因为插入时是在头部插入，而查找也是从头部开始，所以不需要刻意去删除原结点，保留着并无影响，可简化程序设计。3四、源程序清单（源程序中应该附有必要的注释）主要包括：（1）源程序如下：//最后显示的是每一步完成后各桶的油量#includestdio.h#includestring.h#includestdlib.htypedefstructs_you{intyou[3][2];//[3]表3个桶[2]中的0下标表现有量1下标表容量intn;//当前分的步骤数，从0开始intcg;//是否可行的标记1表成功structs_you*next;//用这个将所有结点串起来方便查询structs_you*zi[3][2];//[3]表以哪个桶为基向其他桶倒[2]中0倒往先目标1倒往后目标structs_you*mu;//用于逆向查询分油过程}s_you;voidSC(s_you*ShuChu);//递归逆向输出intCX(s_you*ChaXun,s_you*MuBiao);//查询链表中是否已经存在不存在返回-1存在则返回所在层级voidJianShu(s_you*Ding,s_you*ChaXun,intJieGuo);//递归建树voidmain(){//变量声明s_youDing;s_youChaXun;s_you*temp=NULL;s_you*temp2=NULL;intJieGuo=0;memset(&Ding,0,sizeof(s_you));memset(&ChaXun,0,sizeof(s_you));Ding.n=0;ChaXun.next=&Ding;ChaXun.n=-1;//用ChaXun指向的结构体的cg存储当前链表中成功所需的最小步数//输入#if04Ding.you[0][1]=Ding.you[0][0]=80;Ding.you[1][1]=50;Ding.you[2][1]=30;JieGuo=40;#elseprintf(3个桶容量及结果，第一桶视为满桶，其他视为空桶，用空格隔开，如80503040：\n);scanf(%d%d%d%d,&Ding.you[0][1],&Ding.you[1][1],&Ding.you[2][1],&JieGuo);Ding.you[0][0]=Ding.you[0][1];printf(\n);#endif//判断输入合法性偶就不写了//递归建树JianShu(&Ding,&ChaXun,JieGuo);//搜索可行方法，找出其中最短的，输出temp=ChaXun.next;while(temp){if(temp-n==ChaXun.n&&temp-cg){SC(temp);printf(\n);}temp=temp-next;}//释放内存temp=ChaXun.next;while(temp){temp2=temp;temp=temp-next;if(temp2!=&Ding)free(temp2);}if(ChaXun.n==-1)printf(没办法完成！\n\n);system(pause);}5voidSC(s_you*ShuChu)//递归逆向输出{if(ShuChu-mu==NULL)printf(%4d%4d%4d\n,ShuChu-you[0][0],ShuChu-you[1][0],ShuChu-you[2][0]);else{SC(ShuChu-mu);printf(%4d%4d%4d\n,ShuChu-you[0][0],ShuChu-you[1][0],ShuChu-you[2][0]);}}intCX(s_you*ChaXun,s_you*MuBiao)//查询链表中是否已经存在不存在返回-1存在则返回所在层级{s_you*temp=ChaXun-next;while(temp){if(temp-you[0][0]==MuBiao-you[0][0]&&temp-you[1][0]==MuBiao-you[1][0]&&temp-you[2][0]==MuBiao-you[2][0])returntemp-n;elsetemp=temp-next;}return-1;}voidJianShu(s_you*Ding,s_you*ChaXun,intJieGuo)//递归建树{if(Ding-you[0][0]==JieGuo||Ding-you[1][0]==JieGuo||Ding-you[2][0]==JieGuo){memset(Ding-zi,0,6*sizeof(s_you*));if(ChaXun-n==-1||Ding-nChaXun-n)ChaXun-n=Ding-n;Ding-cg=1;//成功标记return;}elseif(ChaXun-n!=-1&&Ding-n=ChaXun-n){memset(Ding-zi,0,6*sizeof(s_you*));return;6}else{inti=0,xian=0,hou=0,min=0;s_you*zi=NULL;s_you*CXTemp=ChaXun;intCXJieGuo=0;for(i=0;i3;i++){if(Ding-you[i][0]==0)continue;xian=(i==0);hou=2-(i==2);//倒往先目标zi=(s_you*)malloc(sizeof(s_you));memcpy(zi,Ding,sizeof(s_you));min=Ding-you[i][0]Ding-you[xian][1]-Ding-you[xian][0]?Ding-you[i][0]:Ding-you[xian][1]-Ding-you[xian][0];zi-you[i][0]-=min;zi-you[xian][0]+=min;zi-n++;CXJieGuo=CX(ChaXun,zi);if(CXJieGuo!=-1&&CXJieGuo=zi-n)free(zi);else{zi-next=ChaXun-next;ChaXun-next=zi;zi-mu=Ding;Ding-zi[i][0]=zi;//递归调用JianShu(zi,ChaXun,JieGuo);}//倒往后目标zi=(s_you*)malloc(sizeof(s_you));memcpy(zi,Ding,sizeof(s_you));7min=Ding-you[i][0]Ding-you[hou][1]-Ding-you[hou][0]?Ding-you[i][0]:Ding-you[hou][1]-Ding-you[hou][0];zi-you[i][0]-=min;zi-you[hou][0]+=min;zi-n++;CXJieGuo=CX(ChaXun,zi);if(CXJieGuo!=-1&&CXJieGuo=zi-n)free(zi);else{zi-next=ChaXun-next;ChaXun-next=zi;zi-mu=Ding;Ding-zi[i][1]=zi;//递归调用JianShu(zi,ChaXun,JieGuo);}}}}（2）算法的时间复杂度是n算法的空间复杂度是n。（3）这个问题就是用A、B、C三个数能倒出几种D。还是给个限制吧，假定ABCD都是大于零的整数,ABC。好了，下面就是和象棋问题一样了，让计算机进行所有可能的倒油操作。判断能否创造出D：定义函数T(intx,inty,intt)，从x中倒出tkg油到y，再把运算后三个油桶的新值与运算之前三个油桶曾经存在的值比较，如果存在相同则撤销本次操作，换其他操作，直到无法创造出新的三个唯一的值。（4）do{printf(*******************************\n);8printf(1、输入各个桶的容量\n);printf(2、输入目标容量\n);printf(3、输出分油过程和结果\n);printf(0、退出系统\n);printf(*******************************\n);printf(请选择0-3：);fflush(stdin);scanf(%c,&cmd);switch(cmd){case'1':.................//使用了菜单驱动程序，使页面简单明了。五、程序调试及测试结果主要包括：（1）当输入结果不符合要求时（2）当执行程序时9六、结论1、实验中，我经常得到编译错误的提示，仔细检查过过后才知道是一些细节问题。2、我觉得，在知道应该着么编译之后，还应该注意一些细节的问题，因为细节决定成败。比如说是哪里可以有空格，哪里不可以有空格。那里的末尾可以有分号，而