1.问题描述

小孩分油问题

两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两、一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，在回家的路上，两人想平分这一斤油，可是又没有其它工具。试仅用三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。

2.算法设计

令状态R、E、S分别表示十两、七两和三两的瓶子中所装的油量。如问题所述，初始时有（R,E,S）=（10，0，0），问题要求即仅通过这三个瓶子，将油量状态转变为（R,E,S）=（5，5，0）。

该问题较为特殊，我们发现七两的瓶子和三两的瓶子所能装的油的总量恰好为十两。因此，我们可以将十两的瓶子等同于一个无穷大的油桶，任何时候七两和三两的瓶子都可以通过这个油桶装满或倒空油。在这个假设下，原问题即被简化为：初始状态（E、S）=（0，0），要求仅通过这两个瓶子，将状态转变为（E、S）=（5，0）。在这个目标状态下，十两的瓶子中自然装了五两油。

将两个瓶子的状态转变以及对应的规则列表如下：

规则号	规则	解释
1	(E,S) and E<7 → (7,S)	7两瓶不满时装满
2	(E,S) and S<3 → (E,3)	3两瓶不满时装满
3	(E,S) and E>0 → (0,S)	7两瓶不空时倒空
4	(E,S) and S>0 → (E,0)	3两瓶不空时倒空
5	(E,S) and E>0 and E+S≤3 → (0,E+S)	37两瓶中油全倒入3两瓶
6	(E,S) and S>0 and E+S≤7 → (E+S,0)	3两瓶中油全倒入7两瓶
7	(E,S) and S<3 and E+S≥3 → (E+S-3,3)	用7两瓶油装满3两瓶子
8	(E,S) and E<7 and E+S≥7 → (7,E+S-7)	用3两瓶油装满7两瓶子

在每个状态（E，S）下，我们均可以通过判断E、S的值来选择上述若干条规则进行状态转变。整个状态空间构成了一颗树，树根是初始状态（R，S）=（0，0）,目标状态（R，S）=（5，0）则可能位于某些节点中。

因为该问题的状态空间较小，最多不超过（7*3=21）种状态，因此在实验中我们采用深度搜索的方法对问题进行求解。此外，为了避免对已经搜索过的状态重复搜索，程序中定义了一个数组，用于存储已经搜索过的状态，仅有当当前状态没有在该数组中出现过时，算法才对其进行搜索，并将该状态放入数组中。

3.程序流程

 

4.核心伪代码

function isVisited(E, S): 状态(E, S)是否搜索过，没有则将其入栈并标记已搜索。

初始状态(E, S) = (0, 0)，并存入栈Stack

while 栈Stack不为空：

         取出栈顶元素(E, S)，并输出

         If (E, S) == (5, 0), then

                  分油成功，break;

         if E < 7, then:

                  (E, S) = (7, S), isVisited(E, S)

         if E < 3, then:

                   (E, S) = (E, 3), isVisited(E, S)

         if E > 0, then:

                   (E, S) = (0, S), isVisited(E, S)

         if S > 0, then:

                   (E, S) = (E, 0), isVisited(E, S)

         if E > 0 and E+S <= 3, then:

                   (E, S) = (0, E+S), isVisited(E, S)

         if S > 0 and E+S <= 7, then:

                   (E, S) = (E+S, 0), isVisited(E, S)

         if S < 3 and E+S >= 3, then:

                   (E, S) = (7, S), isVisited(E+S-3, 3)

         if E < 7 and E+S >= 7, then:

                   (E, S) = (7, S), isVisited(7, E+S-7)

end

5.代码运行及测试

算法运行结果如下所示，经过10次操作后，准确得将油划分为两个五两。

 

6.结论

本实验是对状态空间采用深搜的方法实现的。程序中设置了辅助数组用于保存已经搜索过的状态，且该问题的状态空间很小，因此深搜不会出现无穷解的情况。只要目标状态设置合理且存在，深搜一定能在有限的步骤里求得。但是在小孩分油问题中，深搜所得结果不一定为最优，广搜下得到的结果才是最优结果。但是由于深搜易于实现且速度快，因此实验中才选择深搜去实现。

本实验源码具有较强的扩展性，只要初始状态和目标状态设置合理，程序均可以成功将其状态转换过程输出。

7.源码

#include
     
      #include
      
       #include
       
        using namespace std;struct State {    int E; // 七两的瓶子     int S; // 三两的瓶子         State(int E, int S) {        this->E = E;        this->S = S;    }};//  深搜辅助栈stack
        
          Stack;// 存储已经出现过的状态 vector
         
           visited;// 查询状态s先前是否出现过 bool isVisited(State s) {    vector
          
           ::iterator it; for (it = visited.begin(); it != visited.end(); it++) { if (it->E == s.E && it->S == s.S) return true; } return false;}// 倒油行为，状态转变void move(State s) { // 查询当前状态先前是否访问过 if (!isVisited(s)) { visited.push_back(s); Stack.push(s); }}int main() { int E = 0, S = 0; int fE = 5, fS = 0; cout<<"Please input the initial oil of bottles："<
           
            >E>>S; cout<<"Please input the final oil of bottles："<
            
             >fE>>fS; Stack.push(State(E, S)); while(!Stack.empty()) { State cur = Stack.top(); Stack.pop(); E = cur.E; S = cur.S; cout<<10 - E - S<<" "<
             
              <<" "<
              <
               
                 0) move(State(0, S)); // 将三两的瓶子倒空 if (S > 0) move(State(E, 0)); // 将七两的瓶子全部装到三两的瓶子上 if (E > 0 && E + S <= 3) move(State(0, E + S)); // 将三两的瓶子全部装到七两的瓶子上 if (S > 0 && E + S <= 7) move(State(E + S, 0)); // 用七两的瓶子将三两的瓶子装满 if (S < 3 && E + S >= 3) move(State(E + S - 3, 3)); // 用三两的瓶子将七两的瓶子装满 if (E < 7 && E + S >= 7) move(State(7, E + S - 7)); } cout<<"Algorithm cannot find a solution!"<