分油问题C语言

《分油问题C语言》由会员分享，可在线阅读，更多相关《分油问题C语言（6页珍藏版）》请在装配图网上搜索。

1、设有大小不等的 X，Y，Z 三个无刻度的油桶，分别能够盛满油 X， Y，Z(例如， X=8 ，Y=5 ， Z=3)，并约定 X YZ 。初始时，仅 X 油桶盛满油， Y 和 Z 油桶为空。要求程序寻找一种最少的分油步聚，在某个油桶中分出 T 升油 (例如 T=4) 。解：令三个油桶的盛油情况为倒油过程的状态， 则倒油过程就是状态变化的过程。 为了记录倒油过程，程序引入倒油状态队列 ,将倒油过程中产生的状态存储在队列中。 队列的每个元素记录每次分油后各个油桶的分油后各个油桶的盛油量和倒油轨迹等有关信息。程序反复从队列中取出第一个还未检查过的状态， 对该状态下的每个油桶判断其是否可以倒出油，及是否

2、可以倒进油。由于油桶没有刻度，分油时只能将某个油桶倒满或倒空。 程序分别按倒空或倒满两种可能的倒油动作执行不同的处理，产生新的倒油状态，为避免某个倒油状态在队列中重复出现， 程序只将未曾出现过的新状态及其倒油轨迹信息存入队列中，假定程序检查了相当多的状态后，或能找到解，或能确定问题无解。倒油程序算法如下：算法 - 无刻度油桶分油输入各桶容量和目标容量；将初始状态存入倒油状态队列；设置其它初始值；do对状态队列中第一个还未检查的元素在还未检查完每个倒出的桶且还未找到解且还未确定无解情况下循环 if( 倒出桶有油 )在还未检查完每个桶且还未找到解且还未确定无解情况下循环 if( 当前桶不是倒出桶且

3、桶还有空 ) 确定本次倒油量；在队列中检查倒油后的结果状态是否在队列中出现； if( 结果状态不在队列中出现 )将结果状态和轨迹信息存入队列；if(有桶中的油达到目标容量)设置找到解标志；if(还未找到解 )修正队列第一个还未检查过的元素指针；if(队列中的元素都已检查过)设置无解标志；while(还未找到解且还未确定无解) ；if(找到解 )根据倒油步聚的轨迹信息，形成倒油步聚序列；输出倒油步聚序列；倒油队列中的元素应包含下列信息：各桶的盛油量， 该状态是从哪一个桶 ( 源桶 )倒向哪一个桶 ( 目标桶 ) 而形成的，形成该状态的元素在队列中的位置。根据以上算法编写如下程序。程序代码如下：#

4、include#define N 100#define BUCKETS 3struct eleint stateBUCKETS; /*各桶盛油量 */int sbucket; /*源桶 */int obucket; /*目标桶 */int last; /*轨迹元素在队列中的下标*/qN; /*队列 */int fullBUCKETS;int i,j,k,found,unable,wi,wj,v,targ;int head,tail;void main()/* 输入各桶容量和目标容量*/printf(Enter volume of buckets. );for(i=0;ifull1full2,相

5、应代码在此*/printf(Enter volume of targ. );scanf(%d,&targ); /*检查targ=full0的代码在此*/* 设置将初始状态存入倒油状态队列等初值*/q0.state0=full0;for(i=1;iBUCKETS;i+)q0.statei=0;q0.sbucket=0;q0.obucket=0;q0.last=0;found=unable=0;head=tail=0;do/* 对状态队列中第一个还未检查过的元素在还未检查完每个倒出的桶且还未找到解且还未确定无解情况下循环*/for(i=0;i0) /*倒出桶有油 */* 在还未检查完每个油桶且还未

6、找到解且还未确定无解情况下循环*/for(j=0;jBUCKETS&!found&!unable;j+)if(j!=i&qhead.statejfullj-qhead.statej) v=fullj-qhead.statej;else v=qhead.statei; wi=qhead.statei-v; wj=qhead.statej+v;/* 在队列中检查倒油后的结果状态是否在队列中出现 */ for(k=0;ktail) /*结果状态不在队列中出现 */* 将结果状态和轨迹信息存入队列 */tail+;qtail.statei=wi;qtail.statej=wj;qtail.state3

7、-i-j=qhead.state3-i-j;qtail.sbucket=i+1;qtail.obucket=j+1;qtail.last=head;/* 如有桶达到目标盛油量，则设置找到解标志*/if(wi=targ|wj=targ)found=1;if(!found) /*还未找到解 */head+; /*修正队列第一个还未检查过元素指针*/if(headtail) /*队列中的元素都已检查过*/unable=1; /*设置无解标志 */while(!found&!unable); /*还未找到解且还未确定无解*/if(found) /*找到解 */* 根据倒油步聚的轨迹信息，形成倒油步聚序

8、列 */ i=tail;j=-1;do /* 原倒油步聚逆向链接，现改为正向链接*/k=qi.last;qi.last=j;j=i;i=k;while(j);/* 输出倒油步聚序列 */for(k=qk.last;k=0;k=qk.last)printf(%5d to %2d:,qk.sbucket,qk.obucket);for(i=0;ib-c-a并且必须符合如下规则：1.b(5斤桶 ) 倒空后才能从 a(8 斤桶 ) 中取油。2 c(3 斤桶 ) 盛满后才能向a(8 斤捅 ) 中倒油。我们设从 a 中往 b 倒油 x 次，从 c 往 a 倒油 y 次，那么最后 a 中剩下的油应该为 8-

9、5x+3y 斤，按照题意，我们得到如下方程，8-5x+3y=4 ：我们为了得到这个方程的解，应按照上述的倒油规则不断的倒下去，直到 a 中或 b 中油的重量为 4 斤为止，另外也可以改变倒油的规则， 看能否找到最好的倒油步聚。代码：#includeint i;main()int a,y,z;printf(Input Full a ,Empty b,c,Get i:);/* 读入 3 个容器的容量和最后需要的数量 */scanf(%d%d%d,&a,&y,&z,&i);getti(a,y,z);getti(int a,int y,int z)int b=0,c=0;/*b,c为二个容器的实际重量

10、 */printf(a%d b%d c%d %4d%4d%4d ,a,y,z,a,b,c);while(a!=i|b!=i)/* 如果满足要求退出循环if(!b)/* 如果 b 为空，从a-=y;b=y;*/a 往b 倒油 */else if(c=z)a+=z;c=0/*如果c 已满，从c 往a 倒油 */else if(bz-c)b-=(z-c);c=z;/*如果b 的重量大于c 的剩余重量，倒满 c*/elsec+=b;b=0;/* 否则将 b 中的油全部倒入 c*/printf(%4d%4d%4d ,a,b,c);运行结果：Input Full a, Empty b,c,Get i: 8 5 3 4volume:a=8b=5 c=3start:800350323620602152143440