小孩分油问题（附python代码）

港控/mmm° 2022-04-13 06:50 114阅读 0赞

# 小孩分油问题 #

**题目：**

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

**算法设计**：

设置三个油瓶分别为A, B, C，初始化三个油瓶的初始状态(10,0,0)，满油状态(10,7,3)，目标状态(5,5,0)。使用广度优先的搜索方法，对每一种可能情况进行遍历，最终取得结果。其中，对于每一种情况对应每一步操作，操作需要满足一定的约束条件：把A瓶中的油全部倒入B瓶或者把A瓶中的油部分倒入B瓶使B瓶满油。具体的约束条件见*程序流程*。本算法由python实现。

**程序流程**：

![14507538-174a52da347a212f.png][]

1.png

<table> 
 <thead> 
  <tr> 
   <th><strong>序号</strong></th> 
   <th><strong>规则</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>(B,C) and B&lt;7 -&gt; (7,C)</td> 
   <td>B瓶不满的时候装满</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>(B,C) and C&lt;3 -&gt; (B,3)</td> 
   <td>C瓶不满的时候装满</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>(B,C) and B&gt;0 -&gt; (0,C)</td> 
   <td>B瓶不满的时候装满</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>(B,C) and C&gt;0 -&gt; (B,0)</td> 
   <td>C瓶不满的时候装满</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>(B,C) and B&gt;0 and B+C&lt;=3 -&gt; (0,B+C)</td> 
   <td>B瓶的油全倒入C瓶</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>(B,C) and C&gt;0 and B+C&lt;=7 -&gt; (B+C,0)</td> 
   <td>C瓶的油全倒入B瓶</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>(B,C) and B&gt;0 and B+C&gt;=3 -&gt; (B+C-3,3)</td> 
   <td>B瓶的油全倒入C瓶</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>(B,C) and C&gt;0 and B+C&gt;=7 -&gt; (7,B+C-7)</td> 
   <td>C瓶的油全倒入B瓶</td> 
  </tr> 
 </tbody> 
</table>

![14507538-0d45c5dcb10118a1.png][]

1.png

**核心伪代码**：

Def 下一步：
    下一个操作 = [
            (倒出瓶标签, 倒入瓶标签)
            for 倒出瓶标签 range(3) for 倒入瓶标签 in range(3)
    if 倒入/出瓶标签不能相同 and 倒出的瓶不为空 and 已经满了的瓶不能再倒入    ]
    
        for 倒出瓶标签, 倒入瓶标签 in 下一步操作:
            if 倒出倒入瓶由量之后不超过倒入瓶最大容量
                倒出瓶油量 -= (倒入瓶最大容量-倒入瓶现有油量)
                倒入瓶油量 = 倒入瓶最大容量
            else:
                倒出瓶油量 = 0
                倒入瓶油量 = 倒入瓶现有油量 + 倒出瓶现有油量
            yield 下一步
    
    Def 搜索结果:
    for 操作in 下一步:
            if 没有试过该操作:
                将该操作加入队列
                if 当前结果== 目标结果:
                  输出结果
                else:
                    递归本函数‘搜索结果’
                删除队列最后一个

**代码运行及测试：**

![14507538-99c95a22b03ef573.png][]

·.png

**结论**：

由代码运行结果可知：整棵树一共有20种方法能够达到要求，其中最佳即路径最短的方法为第9种方法。

第9种方法:\[10, 0, 0\]->\[3, 7, 0\]->\[3, 4, 3\]->\[6, 4, 0\]->\[6, 1, 3\]->\[9, 1, 0\]->\[9, 0, 1\]->\[2, 7, 1\]->\[2, 5, 3\]->\[5, 5, 0\]

具体做法为：

0) 初始化-->\[10, 0, 0\]  
 1) A瓶倒满B瓶-->\[3, 7, 0\]  
 2) B瓶倒满C瓶-->\[3, 4, 3\]  
 3) C瓶倒满A瓶-->\[6, 4, 0\]  
 4) B瓶倒满C瓶-->\[6, 1, 3\]  
 5) C瓶倒满A瓶-->\[9, 1, 0\]  
 6) B瓶倒满C瓶-->\[9, 0, 1\]  
 7) A瓶倒满B瓶-->\[2, 7, 1\]  
 8) B瓶倒满C瓶-->\[2, 5, 3\]  
 9) C瓶倒满A瓶-->\[5, 5, 0\]

**源代码：**

'''
    @author: 嘿芝麻
    
    @software: garner
    @file: main_oil.py
    @time: 2018/10/5
    '''
    from collections import deque
    
    def nextStep(current_state, oil_volume):
        next_action = [
            (from_, to_)
            for from_ in range(3) for to_ in range(3)
            if from_ != to_ and current_state[from_] > 0 and current_state[to_] < oil_volume[to_]
        ]
    
        for from_, to_ in next_action:
            next_state = list(current_state)
            if current_state[from_] + current_state[to_] > oil_volume[to_]:
                next_state[from_] -= (oil_volume[to_] - current_state[to_])
                next_state[to_] = oil_volume[to_]
            else:
                next_state[from_] = 0
                next_state[to_] = current_state[to_] + current_state[from_]
            yield next_state
    
    
    def searchResult(record, oil_volume=[10, 7, 3], final_state=[5, 5, 0]):
        global num, record_list
        current_state = record[-1]
        next_stage = nextStep(current_state, oil_volume)
    
        for stage in next_stage:
            if stage not in record:
                record.append(stage)
                if stage == final_state:
                    numm = num + 1
                    s_numm = str(numm)
                    str_record = ''
                    for i in record:
                        str_record += str(i)
                        if i != [5, 5, 0]:
                            str_record += '->'
                    print("方法{}:{}".format(s_numm, str_record))
                    record_list.append(deque(record))
                    num += 1
                else:
                    searchResult(record, oil_volume, final_state)
                record.pop()
    
    
    if __name__ == '__main__':
        initial_oil_state = [10, 0, 0]
        oil_volume = [10, 7, 3]
        num = 0
        record_list = []
        record = deque()
        record.append(initial_oil_state)
        searchResult(record)
        number = "广度优先搜索共有{}种方法".format(num)
        shortest = "路径最短的方法中操作步总数为{}".format(min([len(i) for i in record_list]))
    
        print(number)
        print(shortest)

[14507538-174a52da347a212f.png]: /images/20220413/8fbde7673a48401e98f9182aa176d079.png
[14507538-0d45c5dcb10118a1.png]: /images/20220413/183dfa83ed64463cacbf23424791ffa1.png
[14507538-99c95a22b03ef573.png]: /images/20220413/7b0dd0b8e4114d0f85b6cc202519da3a.png