分油问题C语言.doc
《分油问题C语言.doc》由会员分享,可在线阅读,更多相关《分油问题C语言.doc(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、分油问题C语言设有大小不等的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(找到解)根据倒油步聚的轨迹信息,形成倒油步聚序列;输出倒油步聚序列;倒油队列中的元素应包含下列信息:各桶的盛油量,该状态是从哪一个桶(源桶)倒向哪一个桶(目标桶)而形成的,形成该状态的元素在队列中的位置。根据以上算法编写如下程序。程序代码如下:#include#define N 100#define BUCKETS 3struct
4、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,相应代码在此*/printf(Enter volume of targ. );scanf(%d,&t
5、arg); /*检查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) /*倒出桶有油*/*在还未检查完每个油桶且还未找到解且还未确定无解情况下循环*/for(j=0;jBUCKETS&!found&!unable;j+)i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 问题 语言
限制150内