winedistribution.cpp

解决了883分酒问题

/**
	@author:胡玮玮
	@time:2008-10-13
	*/

#include<iostream>
#include<fstream>
#include<ctime>
#include<iomanip>
using namespace std;

//定义一些标记
int flag[7]={8,8,0,0,0,0,0};   //某一状态表示
int solution[100][3];          //求解过程
bool gotItOrNot = false;       //标记是否有结果求解出来
int state[6354][8];            //状态集合，用来检验是否已经检查过该状态
int seq = 0;                   //状态集合的标记
int totalStep=100;             //记录步数
int resultState[100][7];       //记录状态序列
int resultSolution[100][3];    //最少步数

void tryToSolve(int);          //求解
int distribute(int ,int);      //计算a可以分给b多少酒
void moveIt(int ,int,int);     //实施分酒
bool checkIt(int);             //检验是否已经检查过该状态

double start = 0.0,end = 0.0;

int main()
{
	ofstream out("out.txt");
	cout<<"==================883分酒问题=================="<<endl;
	cout<<"求解中，请耐心等待……"<<endl;
	start = clock();
	tryToSolve(0);
	//for(int i=0;i<totalStep;++i)
	//	cout<<i+1<<"=:"<<"从"<<resultSolution[i][0]<<"移动"<<resultSolution[i][2]<<"升酒到"<<resultSolution[i][1]<<"中去"<<endl;
	resultState[0][0]=8;
	resultState[0][1]=8;
	resultState[0][2]=0;
	resultState[0][3]=0;
	resultState[0][4]=0;
	resultState[0][5]=0;
	resultState[0][6]=0;
	//for(int i=0;i<totalStep;++i)
	//	cout<<i+1<<"==="<<resultSolution[i][0]<<" "<<resultSolution[i][1]<<" "<<resultSolution[i][2]<<endl;
	for(int i=1;i<100;i++)
		for(int j=0;j<7;j++)
			resultState[i][j]=0;
	for(int i=0;i<totalStep+1;i++){
		//resultState[i+1][resultSolution[i][0]]=resultState[i][resultSolution[i][0]]-resultSolution[i][2];
		//resultState[i+1][resultSolution[i][1]]=resultState[i][resultSolution[i][0]]+resultSolution[i][2];
		for(int j=0;j<7;j++){
			if(j == resultSolution[i][0])
				resultState[i+1][j] = resultState[i][j] - resultSolution[i][2];
			else if(j == resultSolution[i][1])
				resultState[i+1][j] = resultState[i][j] + resultSolution[i][2];
			else
				resultState[i+1][j] = resultState[i][j];
		}
	}
	end = clock();
	cout<<"解决883分酒问题最少需要"<<totalStep<<"步，花费"<<end-start<<"ms."<<endl;
	cout<<"共有"<<totalStep+1<<"个状态如下："<<endl;
	cout<<"========================================="<<endl;
	for(int i=0;i<totalStep+1;i++){
		cout<<setw(3)<<i+1<<": (";
		for(int j=0;j<6;j++){
			cout<<resultState[i][j]<<",";
		}
		cout<<resultState[i][6]<<")"<<endl;
	}
	out<<"解决883分酒问题最少需要"<<totalStep<<"步，花费"<<end-start<<"ms."<<endl;
	out<<"共有"<<totalStep+1<<"个状态如下："<<endl;
	out<<"========================================="<<endl;
	for(int i=0;i<totalStep+1;i++){
		out<<setw(3)<<i+1<<": (";
		for(int j=0;j<6;j++){
			out<<resultState[i][j]<<",";
		}
		out<<resultState[i][6]<<")"<<endl;
	}
	out.close();
	return 0;
}


//计算a可以分给b多少酒
int distribute(int from,int to){
	if(flag[from] == 0||from == to)
		return 0;
	if(to>2){
		if(flag[from] > 4 - flag[to])
			return 0;
		return flag[from];
	}
	else{
		int temp = 0;
		if(to == 2){
			temp = 3 - flag[to];
		}
		else{
			temp = 8 - flag[to];
		}
		if(flag[from] < temp)
			return flag[from];
		return temp;
	}
}

//实施分酒
void moveIt(int from,int to,int sum){
	flag[from]-=sum;
	flag[to]+=sum;
}

//检验是否已经检查过该状态
bool checkIt(int step){
	int i=0,j=0;
	for(i=0;i<seq;++i){
		for(j=0;j<7;++j){
			if(flag[j]!=state[i][j])
				break;
		}
		if(j==7){
			if(step<state[i][7]){
				state[i][7]=step;
				return false;
			}
			else 
				return true;
		}
	}
	for(int m=0;m<7;++m)
		state[seq][m] = flag[m];
	state[seq][7] = step;
	++seq;
	return false;
}

//求解
void tryToSolve(int steps){
	if(flag[0]==0 && flag[1]==0 && flag[2]==0 && flag[3]==4 && flag[4]==4 && flag[5]==4 && flag[6]==4){
		if(steps < totalStep)
			totalStep = steps;
		for(int i=0;i<totalStep;++i)
			for(int j=0;j<3;j++)
				resultSolution[i][j]=solution[i][j];
		//gotItOrNot = true;
		//cout<<"======分酒序列如下======"<<endl;
		//for(int i=0;i<steps;++i)
		//	cout<<i+1<<"=:"<<"从"<<solution[i][0]<<"移动"<<solution[i][2]<<"升酒到"<<solution[i][1]<<"中去"<<endl;
		//totalStep = steps;
		return;
	}
	if(checkIt(steps))   //找到已有状态
		return;
	int from=0,to=0,n=0;
	for(from=0;from<3;++from)
		for(to=0;to<7;++to){
			if((n=distribute(from,to))>0){
				solution[steps][0]=from;
				solution[steps][1]=to;
				solution[steps][2]=n;
				moveIt(from,to,n);
				//if(!gotItOrNot)
					tryToSolve(steps+1);  //递归
				moveIt(to,from,n); //回溯
			}
		}
}