C++程序设计例解(06)
06.设有大小不等的X，Y，Z三个无刻度的油桶，分别能够盛满油X，Y，Z(例如，X=80，Y=50，Z=30)，并约定X>Y>Z。初始时，仅X油桶盛满油，Y和Z油桶为空。要求程序寻找一种最少的分油步聚，在某个油桶中分出T升油(例如T=40)。
解：
令三个油桶的盛油情况为倒油过程的状态，则倒油过程就是状态变化的过程。为了记录倒油过程，程序引入倒油状态队列，将倒油过程中产生的状态存储在队列中。队列的每个元素记录每次分油后各个油桶的分油后各个油桶的盛油量和倒油轨迹等有关信息。程序反复从队列中取出第一个还未检查过的状态，对该状态下的每个油桶判断其是否可以倒出油，及是否可以倒进油。由于油桶没有刻度，分油时只能将某个油桶倒满或倒空。程序分别按倒空或倒满两种可能的倒油动作执行不同的处理，产生新的倒油状态，为避免某个倒油状态在队列中重复出现，程序只将未曾出现过的新状态及其倒油轨迹信息存入队列中，假定程序检查了相当多的状态后，或能找到解，或能确定问题无解。
倒油程序算法如下：
算法---无刻度油桶分油
{
输入各桶容量和目标容量；
将初始状态存入倒油状态队列；
设置其它初始值；
do
{
对状态队列中第一个还未检查的元素
在还未检查完每个倒出的桶且还未找到解且还未确定无解情况下循环
if(倒出桶有油)
在还未检查完每个桶且还未找到解且还未确定无解情况下循环
if(当前桶不是倒出桶且桶还有空)
{
确定本次倒油量；
在队列中检查倒油后的结果状态是否在队列中出现；
if(结果状态不在队列中出现)
{
将结果状态和轨迹信息存入队列；
if(有桶中的油达到目标容量)
设置找到解标志；
}
}
if(还未找到解)
{
修正队列第一个还未检查过的元素指针；
if(队列中的元素都已检查过)
设置无解标志；
}
}while(还未找到解且还未确定无解)；
if(找到解)
{
根据倒油步聚的轨迹信息，形成倒油步聚序列；
输出倒油步聚序列；
}
}
倒油队列中的元素应包含下列信息：各桶的盛油量，该状态是从哪一个桶(源桶)倒向哪一个桶(目标桶)而形成的，形成该状态的元素在队列中的位置。根据以上算法编写如下程序。
程序代码如下：
#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");
}