考试网 >> IT认证 >> 等级 >> 二级考试 >> C程序设计例解(06)

发布时间：2006-06-28 00:05     点击：

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(当前桶不是倒出桶且桶还有空)

                {

                    确定本次倒油量；

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。