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

末蓝、 2022-05-09 09:40 126阅读 0赞

# 小孩分油问题 #

**题目：**

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

**算法设计**：

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

**程序流程**：

![1][]

<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>

![image-20181005201841463][]

**核心伪代码**：

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

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

![在这里插入图片描述][70]

**结论**：

由代码运行结果可知：整棵树一共有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)

[1]: /images/20220509/fb95bfee4ada4208a27ab74b96b83f50.png
[image-20181005201841463]: /images/20220509/470f4481ad9044aba7338f652e768ac8.png
[70]: /images/20220509/a626d66f12cb4897bfcbdacc2d0853bc.png