fenyou.cpp

油瓶分油问题：有两个容量分别是8斤和6斤的空油瓶 和一个大油桶

#include<stdio.h>
#include <stdlib.h>
#define N 100
#define BUCKETS 3
struct ele{
	int state[BUCKETS]; /*各桶盛油量*/
	int sbucket; /*源桶*/
	int obucket; /*目标桶*/
	int last; /*轨迹元素在队列中的下标*/
}q[N]; /*队列*/
int full[BUCKETS];
int i,j,k,found,unable,wi,wj,v,targ;
int head,tail;
void main()
{
	/*输入各桶容量和目标容量*/
	printf("Enter volume of buckets.\n");
	for(i=0;i<BUCKETS;i++)
	scanf("%d",&full[i]);
	/*如要检查full[0]>full[1]>full[2],相应代码在此*/
	printf("Enter volume of targ.\n");
	scanf("%d",&targ); /*检查targ<=full[0]的代码在此*/
	/*设置将初始状态存入倒油状态队列等初值*/
	q[0].state[0]=full[0];
	for(i=1;i<BUCKETS;i++)
	q[0].state[i]=0;
	q[0].sbucket=0;
	q[0].obucket=0;
	q[0].last=0;
	found=unable=0;
	head=tail=0;
	do
	{
		/*对状态队列中第一个还未检查过的元素在还未检查完每个倒出的桶
		且还未找到解且还未确定无解情况下循环*/
		for(i=0;i<BUCKETS&&!found&&!unable;i++)
		if(q[head].state[i]>0) /*倒出桶有油*/
			/*在还未检查完每个油桶且还未找到解且还未确定无解情况下循环*/
			for(j=0;j<BUCKETS&&!found&&!unable;j++)
			if(j!=i&&q[head].state[j]<full[j])
				{ /*当前桶不是倒出桶且桶还有空*/
					/*确定本次倒油量*/
					if(q[head].state[i]>full[j]-q[head].state[j])
						v=full[j]-q[head].state[j];
						else v=q[head].state[i];
							wi=q[head].state[i]-v;
							wj=q[head].state[j]+v;
							/*在队列中检查倒油后的结果状态是否在队列中出现*/
							for(k=0;k<=tail;k++)
							if(q[k].state[i]==wi&&q[k].state[j]==wj) break;
								if(k>tail) /*结果状态不在队列中出现*/
									{
										/*将结果状态和轨迹信息存入队列*/
										tail++;
										q[tail].state[i]=wi;
										q[tail].state[j]=wj;
										q[tail].state[3-i-j]=q[head].state[3-i-j];
										q[tail].sbucket=i+1;
										q[tail].obucket=j+1;
										q[tail].last=head;
										/*如有桶达到目标盛油量，则设置找到解标志*/
										if(wi==targ||wj==targ)found=1;
										}
									}
		if(!found) /*还未找到解*/
			{
				head++; /*修正队列第一个还未检查过元素指针*/
				if(head>tail) /*队列中的元素都已检查过*/
					unable=1; /*设置无解标志*/
				}
	}while(!found&&!unable); /*还未找到解且还未确定无解*/
	if(found) /*找到解*/
		{
			/*根据倒油步聚的轨迹信息，形成倒油步聚序列*/
			i=tail;
			j=-1;
			do /*原倒油步聚逆向链接，现改为正向链接*/
			{
				k=q[i].last;
				q[i].last=j;
				j=i;
				i=k;
			}while(j);
			/*输出倒油步聚序列*/
			for(k=q[k].last;k>=0;k=q[k].last)
			{
				printf("%5d to %2d:",q[k].sbucket,q[k].obucket);
				for(i=0;i<BUCKETS;i++)
				printf("%4d",q[k].state[i]);
				printf("\n");
			}
			system("pause");
		}
		else printf("Unable!\n");
}