C语言教程:Poisson的分酒问题

Poisson的分酒问题

我这有一个，大家看一下：
/*有四个人喝酒，有两个八两装满酒的瓶，
只有一个三两的杯子。他们要平分这些酒，
但是不能借用其它的工具，你觉得应该怎么做？
*/
#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©)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