fenyou.cpp

利用数据结构中的队列结构实现分油问题

#include<stdio.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"); 
} 
} 
else printf("Unable!\n"); 
}