//分酒 /*有四个人喝酒，有两个八两装满酒的瓶， 只有一个三两的杯子。他们要平分这些酒， 但是不能借用其它的工具，你觉得应该怎么做？ */ #include<iostream.h> int position[6354][8];//状态集 long ptop=0; //后来实验的结果是，在求解的过程中可能出现6354种状态 int object[7]={8,8,0,0,0,0,0};//0,1瓶,2杯,3~6人，写在一起只是为了便于搜索 int solution[60][3];//保存解过程：a,b,n a->b(n) int cmin=100;//最少步数 int scount=0; int pour(int a,int b) //从a编号对象往b编号对象转移时，反回可行转移的酒量,返回0表示非法 {     int empty;     if(object[a]==0)return 0;     if(a==b)return 0;     //if(a>2)return 0;//不能从人往容器转移     if(b<3)//容器往容器     {         empty=b<2?8-object[b]:3-object[b];         if(object[a]<empty)return object[a];         return empty;     }     else//容器往人     {         empty=4-object[b];         if(object[a]>empty)return 0;         return object[a];     } } inline void move(int a,int b,int n)//转移 {     object[a]-=n;     object[b]+=n; } bool oldposition(int c)//判断是否是曾经出现过的状态 {     int i,j;     for(i=0;i<ptop;++i)     {         for(j=0;j<7;++j)             if(object[j]!=position[i][j])                 break;         if(j==7)         {             if(c<position[i][7])             {                 position[i][7]=c;                 return false;             }             else                 return true;         }     }     for(i=0;i<7;++i)         position[ptop][i]=object[i];     position[ptop][7]=c;     ++ptop;     return false; } void resolve(int c) {     if(object[0]==0&&object[1]==0&&object[2]==0)     //得到一个解，输出     {         if(c<cmin)cmin=c;         cout<<"第"<<(++scount)<<"个解，共"<<c<<"步实现:"<<endl;         for(int i=0;i<c;++i)             cout<<solution[i][0]<<"->"<<solution[i][1]<<":"<<solution[i][2]<<endl;         cout<<"-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"<<endl;         return;     }     if(oldposition(c))return;//好汉不走回头路     int a,b,n;     for(a=0;a<3;++a)         for(b=0;b<7;++b)             if((n=pour(a,b))>0)             {                 solution[c][0]=a;                 solution[c][1]=b;                 solution[c][2]=n;                 move(a,b,n);                 resolve(c+1);//下一步搜索                 move(b,a,n);             } } void main() {     resolve(0);     cout<<"完成需要的最少步数是:"<<cmin<<endl; } 值得解释一下的，程序中object[0]和[1]是两瓶酒，object[2]是那个杯子，object[3]到[6]是那四个人的肚子，程序没什么新鲜玩艺简单的搜索。 运行时间比较长，输出结果用重定向到文件：cpp1>solution.txt 拿出其中一种解： 第816个解，共24步实现: start:    8800000 0->2:3 5830000 2->4:3 5800300 0->2:3 2830300 0->5:2 0830320 2->0:3 3800320 1->2:3 3530320 2->0:3 6500320 1->2:3 6230320 2->0:2 8210320 2->4:1 8200420 0->2:3 5230420 1->0:2 7030420 2->1:3 7300420 0->2:3 4330420 2->1:3 4600420 0->2:3 1630420 2->1:2 1810420 2->6:1 1800421 1->2:3 1530421 2->0:3 4500421 1->2:3 4230421 1->5:2 4030441 2->6:3 4000444 0->3:4 0004444 验证是正确的。

评论