wine_dividing.cpp

分酒问题：已知有3个容量分别为3kg,5kg和8kg且没有刻度的酒瓶,3kg和5kg的酒瓶均装满了酒,而8kg的瓶子为空.现要求仅用这3个瓶子将这些酒分为两个4kg,并分别装入5kg和8kg的瓶子中.

#include <iostream.h>
const int Eight=8;
const int Five=5;
const int Three=3;
const int n=100;
int  X[n], S[n][4];

int min(int a, int b)
{
	if(a<=b)
		return a;
	else
		return b;
}

bool move(int k)
{//此算法主要完成三个工作：
	//1、根据X(k)值计算从上一状态倒酒后各酒瓶中的酒量；
	// 1     2     3     4     5     6
	//8->5  8->3  5->8  5->3  3->8  3->5
	//2、判断显式约束条件，即各酒瓶中酒量是否在容量之内；
	//3、判断隐式约束条件，即判是否有重复状态。
	//
	int t;
	switch(X[k])
	{
	case 1: 
		t=min(S[k-1][1], 5-S[k-1][2]);   //8->5//
		S[k][1]=S[k-1][1]-t;
		S[k][2]=S[k-1][2]+t;
		S[k][3]=S[k-1][3];
		break;
	case 2:
		t=min(S[k-1][1], 3-S[k-1][3]);   //8->3//
		S[k][1]=S[k-1][1]-t;
		S[k][2]=S[k-1][2];
		S[k][3]=S[k-1][3]+t;
		break;
	case 3:  
		t=min(S[k-1][2], 8-S[k-1][1]);   //5->8//
		S[k][1]=S[k-1][1]+t;
		S[k][2]=S[k-1][2]-t;
		S[k][3]=S[k-1][3];
		break;
	case 4:
		t=min(S[k-1][2], 3-S[k-1][3]);   //5->3//
		S[k][1]=S[k-1][1];
		S[k][2]=S[k-1][2]-t;
		S[k][3]=S[k-1][3]+t;
		break;
	case 5:  
		t=min(S[k-1][3], 8-S[k-1][1]);   //3->8//
		S[k][1]=S[k-1][1]+t;
		S[k][2]=S[k-1][2];
		S[k][3]=S[k-1][3]-t;
		break;
	case 6:  
		t=min(S[k-1][3], 5-S[k-1][2]);   //3->5//
		S[k][1]=S[k-1][1];
		S[k][2]=S[k-1][2]+t;
		S[k][3]=S[k-1][3]-t;
		break;
	default:     
		S[k][1]=S[k-1][1];
		S[k][2]=S[k-1][2];
		S[k][3]=S[k-1][3];
		break;
	}
	if(S[k][1]>8 || S[k][2]>5 || S[k][3]>3 || S[k][1]<0 || S[k][2]<0 || S[k][3]<0)  
		return false;
	for(int i=k-1; i>=0 ; i--)
	{
		if(S[i][1]==S[k][1] && S[i][2]==S[k][2] && S[i][3]==S[k][3])
			return false;
	}
	return true;
}


void divide(void)
{// 采用回溯法求解，在各酒瓶的每一个状态，倒酒动作可能是以下6个之一。
	//1      2     3     4     5     6
	//8->5  8->3  5->8  5->3  3->8  3->5
	//算法DIVIDE是回溯主控部分，MOVE采用有副作用的方式，给出下一个可能的倒酒动作。
	int  k,m;
	S[0][1]=Eight;
	S[0][2]=0;
	S[0][3]=0;
	X[1]=0;
	k=1;
	m=6;
	while(k>0)
	{
		X[k]=X[k]+1;
		while(X[k]<=m && !move(k))
		{
			X[k]=X[k]+1;
		}
		if(X[k]<=m)
		{
			if(S[k][1]==4 && S[k][2]==4 && S[k][3]==0)
			{
				cout<<"倒酒步骤如下:"<<endl;
				int i=1;
				while(X[i])
				{
					switch(X[i])
					{
					case 1:
						cout<<"第"<<i<<"步:8->5"<<endl;
						break;
					case 2:
						cout<<"第"<<i<<"步:8->3"<<endl;
						break;
					case 3:
						cout<<"第"<<i<<"步:5->8"<<endl;
						break;
					case 4:
						cout<<"第"<<i<<"步:5->3"<<endl;
						break;
					case 5:
						cout<<"第"<<i<<"步:3->8"<<endl;
						break;
					case 6:
						cout<<"第"<<i<<"步:3->5"<<endl;
						break;
					}
					i++;
				}
				return;
			}
			else
			{
				k=k+1; //此处未判是否越界，即栈溢出。//
				X[k]=0;
			} 
		}
		else
			k=k-1;
	}
}

int main()
{
	divide();
	return 1;
}