问题描述
标题：分红酒有4个红酒瓶子，它们的容量分别是：9升,7升,4升,2升开始的状态是[9,0,0,0]，也就是说：第一个瓶子满着，其它的都空着。允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。这样的一次倒酒动作称为1次操作。假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？本题就是要求你编程实现最小操作次数的计算。输入：最终状态（逗号分隔）输出：最小操作次数（如无法实现，则输出-1）例如：输入：9,0,0,0应该输出：0输入：6,0,0,3应该输出：-1输入：7,2,0,0应该输出：2所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意不要使用package语句。不要使用jdk1.6及以上版本的特性。
解决方案
解决方案二：
以前做过一个号称是微软面试题的分酒的题目，就是8，8，3升的三个容器中，两个8L的装满了酒，怎么平均分给四个人。当时的做法就是把酒尽可能的细化，分成尽可能小的部分，来判断是否可以完成。这题应该和那道题差不多吧，但是有点不一样就是怎么最少次数来实现。。这个我感觉应该先是判断是否多小的部分可以完成分酒任务来实现。明天再仔细想想。。
解决方案三：
搜一下蓝桥杯第三届的复试题，Java本科最后一题就是这个
解决方案四：
这题很明显得用BFS来解决，条件的控制什么的就比较麻烦了，仔细想想吧。
解决方案五：
#include<stdio.h>inttemp[4]={9,7,4,2};intmin=200;voidfun(intT[],intt[],inti,intcount){if(T[0]==t[0]&&T[1]==t[1]&&T[2]==t[2]&&T[3]==t[3]){if(count<min)min=count;}elseif(i==4){return;}else{for(intj=i;j<4+i;j++){if(!T[i]){fun(T,t,i+1,count);}else{intout;if(T[(j+1)%4]==temp[(j+1)%4]){continue;}if(T[i]>=temp[(j+1)%4]-T[(j+1)%4]){out=temp[(j+1)%4]-T[(j+1)%4];T[i]=T[i]-(temp[(j+1)%4]-T[(j+1)%4]);T[(j+1)%4]=temp[(j+1)%4];count++;}else{out=T[i];T[(j+1)%4]+=T[i];T[i]=0;count++;}fun(T,t,i+1,count);T[i]+=out;T[(j+1)%4]-=out;count--;}}}}intmain(){intt[4],T[4]={9,0,0,0};scanf("%d,%d,%d,%d",&t[0],&t[1],&t[2],&t[3]);for(inti=0;i<4;i++){if(t[i]>temp[i]){printf("-1n");return0;}}if(t[0]+t[1]+t[2]+t[3]!=9){printf("-1n");return0;}fun(T,t,0,0);printf("%dn",min);return0;}
这是我这个菜鸟写的，但一些测试数据能通过，一些则不能通过，可能少了一些条件，但想了好久还是没能改善，找不到错在哪。
解决方案六：
#include<stdio.h>#include<stdlib.h>typedefstructNode{inta,b,c,d;structNode*next;}*State;StateA[15];structNodetempS[1000];structNodenewState(inta,intb,intc,intd){structNodestate;state.a=a;state.b=b;state.c=c;state.d=d;state.next=NULL;returnstate;}voidinsertState(Statehead,Statestate){state->next=head->next;head->next=state;}intdiscover(inta,intb,intc,intd,intcnt){intcount;structNode*s=NULL;for(count=0;count<=cnt;count++)for(s=A[count]->next;s!=NULL;s=s->next)if(s->a==a&&s->b==b&&s->c==c&&s->d==d)returncnt;return-1;}voiditerative()//迭代{intcount;inta,b,c,d;int_a,_b,_c,_d;inti=0;structNode*s=NULL;for(count=0;count<10;count++)for(s=A[count]->next;s!=NULL;s=s->next){a=s->a;b=s->b;c=s->c;d=s->d;if(a!=0){if(b<7){if(a+b>=7){_b=7;_a=a+b-7;_c=c;_d=d;}else{_a=0;_b=a+b;_c=c;_d=d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(c<4){if(a+c>=4){_a=a+c-4;_b=b;_c=4;_d=d;}else{_a=0;_b=b;_c=a+c;_d=d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(d<2){if(a+d>=2){_a=a+d-2;_b=b;_c=c;_d=2;}else{_a=0;_b=b;_c=c;_d=a+d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}}if(b!=0){if(a<9){if(a+b>=9){_a=9;_b=a+b-9;_c=c;_d=d;}else{_a=a+b;_b=0;_c=c;_d=d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(c<4){if(b+c>=4){_a=a;_b=b+c-4;_c=4;_d=d;}else{_a=a;_b=0;_c=b+c;_d=d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(d<2){if(b+d>=2){_a=a;_b=b+d-2;_c=c;_d=2;}else{_a=a;_b=0;_c=c;_d=b+d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}}if(c!=0){if(a<9){if(a+c>=9){_b=b;_a=9;_c=a+c-9;_d=d;}else{_a=a+c;_b=b;_c=0;_d=d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(b<7){if(b+c>=7){_a=a;_b=7;_c=b+c-7;_d=d;}else{_a=a;_b=b+c;_c=0;_d=d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(d<2){if(b+d>=2){_a=a;_b=b;_c=c+d-2;_d=2;}else{_a=a;_b=b;_c=0;_d=c+d;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}}if(d!=0){if(a<9){if(a+b>=9){_b=b;_a=9;_c=c;_d=a+d-9;}else{_a=a+d;_b=b;_c=c;_d=0;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(c<4){if(d+c>=4){_a=a;_b=b;_c=4;_d=d+c-4;}else{_a=a;_b=b;_c=d+c;_d=0;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}if(b<7){if(b+d>=7){_a=a;_b=7;_c=c;_d=b+d-7;}else{_a=a;_b=b+d;_c=c;_d=0;}if(discover(_a,_b,_c,_d,count)==-1){tempS[i]=newState(_a,_b,_c,_d);insertState(A[count+1],&tempS[i]);i++;}}}}}intsearch(inta,intb,intc,intd){intcount;structNode*s=NULL;for(count=0;count<10;count++)for(s=A[count]->next;s!=NULL;s=s->next)if(s->a==a&&s->b==b&&s->c==c&&s->d==d)returncount;return-1;}intmain(){inta,b,c,d;structNodestart=newState(9,0,0,0);inti;for(i=0;i<15;i++){A[i]=(State)malloc(sizeof(structNode));A[i]->next=NULL;}A[0]->next=&start;iterative();while(scanf("%d%d%d%d",&a,&b,&c,&d)==4){printf("%dn",search(a,b,c,d));}return0;}
解决方案七：
这是我这个菜鸟写的，测试数据都通过了不过方法有点笨用的是迭代
解决方案八：
#include<stdio.h>inttemp[4]={9,7,4,2};intmin=200;voidfun(intT[],intt[],inti,intcount){if(T[0]==t[0]&&T[1]==t[1]&&T[2]==t[2]&&T[3]==t[3]){if(count<min)min=count;}elseif(i==4){return;}else{for(intj=i;j<3+i;j++){if(!T[i]){fun(T,t,i+1,count);}else{intout;if(T[(j+1)%4]==temp[(j+1)%4]){continue;}if(T[i]>=temp[(j+1)%4]-T[(j+1)%4]){out=temp[(j+1)%4]-T[(j+1)%4];T[i]=T[i]-(temp[(j+1)%4]-T[(j+1)%4]);T[(j+1)%4]=temp[(j+1)%4];count++;fun(T,t,i,count);}else{out=T[i];T[(j+1)%4]+=T[i];T[i]=0;count++;fun(T,t,i+1,count);}T[i]+=out;T[(j+1)%4]-=out;count--;//printf("!");}}}}intmain(){intt[4],T[4]={9,0,0,0};scanf("%d,%d,%d,%d",&t[0],&t[1],&t[2],&t[3]);for(inti=0;i<4;i++){if(t[i]>temp[i]){printf("-1n");return0;}}if(t[0]+t[1]+t[2]+t[3]!=9){printf("-1n");return0;}fun(T,t,0,0);printf("%dn",min);return0;}
这是我修改的四楼的代码，应该已经解决了四楼的问题
解决方案九：
引用4楼Sharing_Li的回复:
#include<stdio.h>inttemp[4]={9,7,4,2};intmin=200;voidfun(intT[],intt[],inti,intcount){if(T[0]==t[0]&&T[1]==t[1]&&T[2]==t[2]&&T[3]==t[3]){if(count<min)min=count;}elseif(i==4){return;}else{for(intj=i;j<4+i;j++){if(!T[i]){fun(T,t,i+1,count);}else{intout;if(T[(j+1)%4]==temp[(j+1)%4]){continue;}if(T[i]>=temp[(j+1)%4]-T[(j+1)%4]){out=temp[(j+1)%4]-T[(j+1)%4];T[i]=T[i]-(temp[(j+1)%4]-T[(j+1)%4]);T[(j+1)%4]=temp[(j+1)%4];count++;}else{out=T[i];T[(j+1)%4]+=T[i];T[i]=0;count++;}fun(T,t,i+1,count);T[i]+=out;T[(j+1)%4]-=out;count--;}}}}intmain(){intt[4],T[4]={9,0,0,0};scanf("%d,%d,%d,%d",&t[0],&t[1],&t[2],&t[3]);for(inti=0;i<4;i++){if(t[i]>temp[i]){printf("-1n");return0;}}if(t[0]+t[1]+t[2]+t[3]!=9){printf("-1n");return0;}fun(T,t,0,0);printf("%dn",min);return0;}这是我这个菜鸟写的，但一些测试数据能通过，一些则不能通过，可能少了一些条件，但想了好久还是没能改善，找不到错在哪。
四楼代码问题出现在：1for循环中j不可为i+3，否则j+1即本身，会出错2：fun(T,t,i+1,count);这个不合适，因为如果没倒空，那么应该还可以继续倒到别的瓶子里，所以应该分条件fun(T,t,i+1,count);和fun(T,t,i,count);
解决方案十：
题目有点意思啊，思考中...
解决方案十一：
想了好久还是不会
解决方案十二：
引用6楼fanhualuojin1992的回复:
这是我这个菜鸟写的，测试数据都通过了不过方法有点笨用的是迭代
为什么我运行的时候用6003最后的结果是5呢
解决方案十三：
引用6楼fanhualuojin1992的回复:
这是我这个菜鸟写的，测试数据都通过了不过方法有点笨用的是迭代
刚刚找到错误了，150行if(c+d>=2){_a=a;_b=b;_c=c+d-2;_d=2;}有个小错误