pouroil.cpp

小孩分油实验

/*分油问题 
  三个瓶子 初始油量 10 0 0
           目标油量  5 5 0
                           */

#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>

#define NOACTION   0
#define POUR_AtoB  1
#define POUR_AtoC  2
#define POUR_BtoA  3
#define POUR_CtoA  4
#define POUR_BtoC  5
#define POUR_CtoB  6

#define VOLUME_A  10
#define VOLUME_B   7
#define VOLUME_C   3

#define TABLESIZE  0x1000
#define QUEUESIZE  10000

short initState=0x0a00;
short desState =0x0550;

//************循环队列***************
class myQueue{
public:
	myQueue(){};
	~myQueue(){};

	void init();
	void enmyQueue(short v);
	void pop();
	void demyQueue();
	short getFront();
	bool empty();
	bool full();
private:
	short value;
	short front;
	short rear;
	short *base;
};

void myQueue::init()
{
	base=(short*)malloc(QUEUESIZE*sizeof(short));
	front =rear =0;
}

void myQueue::enmyQueue(short v)
{
	init();
	if(!full())
	{
		base[rear]=v;
		rear =(rear +1)%QUEUESIZE;
	}
}

void myQueue::pop()
{
	if(!full())
		front =(front +1)%QUEUESIZE;
}

void myQueue::demyQueue()
{
	free(base) ;
}

bool myQueue::empty()
{
	if(front ==rear )
		return true;
	else
		return false;
}

short myQueue::getFront()
{
	return base[front];
}

bool myQueue::full()
{
	if((rear+1)%QUEUESIZE==front)
		return true;
	else 
		return false;
}
//********************************

//*****定义hash表，将各油瓶的状态转化为一个整数，方便查找****
bool hashTable[TABLESIZE];

myQueue q;

//*****定义状态转移信息列表
struct ifo{
	short action;
	short pre_state;
};

struct ifo changeIfo[TABLESIZE];

//*****将油瓶各油量转化为一整数
short hashValue(short bottleA,short bottleB,short bottleC)
{
	return((bottleA<<8) | (bottleB<<4) | bottleC);
}

//*****初始化
void initValue()
{
	short i;
	for(i=0;i<TABLESIZE;i++)
	{
		changeIfo[i].action = 0;
		changeIfo[i].pre_state = 0;
		hashTable[i]=false;
	}
}

//*****通过整数得到各油瓶油量
short bottle_A(short v)
{
	return (v & 0x0f00)>>8;
}
short bottle_B(short v)
{
	return (v & 0x00f0)>>4;
}
short bottle_C(short v)
{
	return (v & 0x000f);
}
//***************************

//*****状态转移函数
short changeState(short curState,short action)
{
	switch (action){
	case POUR_AtoB:
		return hashValue(bottle_A(curState)+bottle_B(curState)-VOLUME_B,VOLUME_B,bottle_C(curState));
		break;
	case POUR_AtoC:
		return hashValue(bottle_A(curState)+bottle_C(curState)-VOLUME_C,bottle_B(curState),VOLUME_C);
		break;
	case POUR_BtoA:
		return hashValue(bottle_A(curState)+bottle_B(curState),0,bottle_C(curState));
		break;
	case POUR_CtoA:
		return hashValue(bottle_A(curState)+bottle_C(curState),bottle_B(curState),0);
		break;
	case POUR_BtoC:
		if(bottle_B(curState)+bottle_C(curState)>VOLUME_C)
			return hashValue(bottle_A(curState),bottle_B(curState)+bottle_C(curState)-VOLUME_C,VOLUME_C);
		else
			return hashValue(bottle_A(curState),0,bottle_B(curState)+bottle_C(curState));
		    break;
	case POUR_CtoB:
		if(bottle_B(curState)+bottle_C(curState)>VOLUME_B)
			return hashValue(bottle_A(curState),VOLUME_B,bottle_B(curState)+bottle_C(curState)-VOLUME_B);
		else
			return hashValue(bottle_A(curState),bottle_B(curState)+bottle_C(curState),0);
			break;
	}
}

//*****状态扩展函数
void extendState(short curState)
{
	short i,nextState;
	for(i=1;i<=POUR_CtoB;i++){
		nextState=changeState(curState,i);
		if(!hashTable[nextState] && nextState != curState && !q.full()){
			q.enmyQueue(nextState);

			changeIfo[nextState].action =i;
			changeIfo[nextState].pre_state=curState;
		}
	}
}

//*****求解过程
void solution()
{
	short p;
	
	q.enmyQueue(hashValue(bottle_A(initState),bottle_B(initState),bottle_C(initState)));
	while(!q.empty()){
		p=q.getFront();
		q.pop();
		if(p == desState)
			break;
		else{
			extendState(p);		
			hashTable[p]=true;
		}
	}
}

//*****打印结果
void printResult(short e)
{
	if(changeIfo[e].action == NOACTION)
	{
		//cout<<"InitVolume :"<<VOLUME_A<<" "<<"0"<<" "<<"0"<<endl;
		return;
	}
	printResult(changeIfo[e].pre_state);
	switch (changeIfo[e].action){
	case POUR_AtoB:
		cout<<"pour A to B: ";
		break;
	case POUR_AtoC:
		cout<<"pour A to C: ";
		break;
	case POUR_BtoA:
		cout<<"pour B to B: ";
		break;
	case POUR_CtoA:
		cout<<"pour C to A: ";
		break;
	case POUR_BtoC:
		cout<<"pour B to C: ";
		break;
	case POUR_CtoB:
		cout<<"pour C to B: ";
		break;
	}
	cout<<((e & 0x0f00) >>8)<<" "<<((e & 0x00f0) >>4)<<" "<<(e & 0x000f)<<endl;
}

void main()
{
	initValue();
	solution();
	cout<<"InitState: 10 0 0 \ndestState:  5 5 0"<<endl<<endl;
	cout<<setw(10)<<"Action"<<setw(8)<<"State"<<endl;
	if(changeIfo[desState].action == NOACTION)
		cout<<"No solution."<<endl;
	else
		printResult(desState);
}