计算机等级考试C语言程序设计例解(06)

计算机等级考试C语言程序设计例解(06),第1张

计算机等级考试C语言程序设计例解(06),第2张

06.有三个大小不同的油桶,X,Y,Z,分别可以装油X,Y,Z(例如X=80,Y=50,Z=30),约定X>Y>Z Y > Z,开始只有X油桶装油,Y,Z油桶空。程序需要找到一个最小的油分离步骤,并在某个油桶中分离T升油(例如,T=40)。
解决方法:
如果三个油桶的油量处于倒油过程的状态,则倒油过程就是状态变化过程。为了记录注油过程,程序引入了注油状态队列,并将注油过程中产生的状态存储在队列中。队列的每个元素记录了每次分油后每个油桶的油量和倒油轨迹等信息。程序反复从队列中取出第一个未检状态,判断是否可以倒油,以及在这个状态下是否可以往每个油桶里倒油。由于油桶没有刻度,因此在配油时只能对某一油桶进行加油或倒油空。程序根据两种可能的倒油动作分别执行不同的处理:倒空或加注,产生新的倒油状态。为了避免队列中某个倒油状态的重复出现,程序只在队列中存储从未出现过的新状态及其倒油轨迹信息,假设程序在检查了相当数量的状态后能找到解或确定问题无解。

倒油程序的算法如下:
算法——无刻度油桶分油
{
输入每个油桶的容量和目标容量;
将初始状态存入倒油状态队列;
设置其他初始值;
do
{
状态队列中第一个未检查的元素
循环
if(倒桶有油)
当每个桶都没有检查完,解决方案还没有找到,仍然
检查队列中是否出现倒油后的结果状态;
if(结果状态不出现在队列中)
{
将结果状态和轨迹信息存储在队列中;
如果(桶中的油达到目标容量)
设置查找解决方案标志;
}
}
if(尚未找到解决方案)
{
修复队列中尚未检查的第一个元素的指针;
if(已经检查了队列中的所有元素)
设置无解标志;
}
}while(还没有找到解决方案,也没有确定解决方案);
if(求解)
{
根据倒油步聚合的轨迹信息,形成倒油步聚合序列;
输出倒油顺序;
}
}
倒油队列中的元素应该包含以下信息:每个桶的含油量,哪个桶(源桶)倒向哪个桶(目标桶)形成这种状态,以及形成这种状态的元素在队列中的位置。根据上面的算法写下面的程序。

位律师回复
DABAN RP主题是一个优秀的主题,极致后台体验,无插件,集成会员系统
白度搜_经验知识百科全书 » 计算机等级考试C语言程序设计例解(06)

0条评论

发表评论

提供最优质的资源集合

立即查看 了解详情