小孩分油问题python解决

1、1.问题描述原问题：两个小孩去打油，一个人带了一个一斤的空瓶，另一个带了一个七两一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，可是又没有其它工具，试仅用三个瓶子（一斤、七两、三两）精确地分成两个半斤油来。2.算法设计把三个油瓶中的油量作为一个状态，经过一个合法动作后得到下一个状态（合法动作是把A瓶中的油全部倒入B瓶 或者 把A瓶中的油部分倒入B瓶使B瓶充满油），递归搜索所有的可能状态，如果到达最终状态则递归停止。油瓶中油的变化规则：（S表示3两油瓶，T表示7两油瓶）序号规则解释1(S,T) and S (7,T)7两瓶不满时装满2(S,T) and T (S,3

2、)3两瓶不满时装满3(S,T) and S0 - (0,T)7两瓶不空时倒空4(S,T) and T0 - (S,0)3两瓶不空时倒空5(S,T) and S0 and S+T (0,S+T)7两瓶中的油全倒入3两瓶6(S,T) and T0 and S+T (S+T,0)3两瓶中的油全倒入7两瓶7(S,T) and S0 and S+T=3 - (S+T-3,3)7两瓶中的油倒满3两瓶8(S,T) and T0 and S+T=7 - (7,S+T-7)3两瓶中的油倒满7两瓶3.代码（穷搜索） 广度优先搜索：（文本输出）import osinitial_oil_state = 10,0,0

3、# 油瓶的初始状态oil_volume = 10,7,3 # 每个油瓶的对应容积from collections import deque # 导入collections标准库中的队列对象和方法# 利用python的deque队列记录状态转移情况，初始化时加入油瓶初始状态。deque是可以从头尾插入和删除的队列record = deque()record.append(initial_oil_state)# 删除文件，因为文件以追加模式打开if os.path.exists(oil_half_width_answer.txt): os.remove(oil_half_width_answer.

4、txt)def NextStateLegal(current_state,oil_volume): next_action = (from_,to_) # 列表推导 # 例如x*x for x in range(10) if x % 3 = 0得出10以内能被3整除的数的平方构成的列表 for from_ in range(3) for to_ in range(3) if from_ != to_ and current_statefrom_ 0 and current_stateto_ oil_volumeto_: next_statefrom_ -= (oil_volumeto_-cur

5、rent_stateto_) next_stateto_ = oil_volumeto_ else: next_statefrom_ = 0 next_stateto_ = current_stateto_ + current_statefrom_ yield next_state # 再由所有可能的合法动作得出所有的下一个状态，通过yield产生供其它函数调用# 记录调试的变量：num表示总共实现方法数，record_list记录所有实现路径num = 0record_list = def searchResult(record, oil_volume=10,7,3, final_state

6、=5,5,0): global num, record_list # 由record的末尾元素得到当前油瓶状态 current_state = record-1 # 得到关于当前状态的下一状态的可迭代生成器，供下一步循环使用 next_state = NextStateLegal(current_state, oil_volume) # 遍历所有可能的下一个状态 for state in next_state: # 保证当前状态没在之前出现过。如果状态已经出现还进行搜索就会形成状态环路，陷入死循环。 if state not in record: # 添加到新的状态到列表中 record.ap

7、pend(state) # 判断是否达到最终状态 if state = 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 += - # console打印可执行方案 print(str_record) # 连接字符串以便保存 queue_ = 第+ s_numm + 种方案 + str_record + nn # 文件存入方案，a表示文件以

8、追加模式打开 f = open(oil_half_width_answer.txt, a) f.write(queue_) f.close() #record_list.append(record)这样使用错误，导致加入列表的是record的引用 #应该使用下面的式子来进行深复制，得到一个新的队列再加入列表。 record_list.append(deque(record) num += 1 else: # 如不是最终状态则递归搜索 searchResult(record, oil_volume, final_state) # 去除当前循环中添加的状态，进入下一个循环，关键步！ record.

9、pop()if _name_ = _main_: # 开始 searchResult(record) # 保存方案数以及最短路径输出字符串 number = 用广度优先搜索共有%d种方案。 % num shortest = 路径最短的方案中状态总数为%d。 % min(len(i) for i in record_list) # 数字转换字符串，为了方便保存在文件中 s_num = str(num) s_min = str(min(len(i) for i in record_list) # 保存需要存放的字符串，将用于write函数中 ss_num = 用广度优先搜索共有 + s_num +

10、 种方案。n ss_min = 路径最短的方案中状态总数为 + s_min + 。n # 文件存入方案数以及最短路径 f = open(oil_half_width_answer.txt, a) f.write(ss_num) f.write(ss_min) f.close() # console打印所有方案的数量和最短路径 print(number) print(shortest)深度优先搜索（未加文本输出）：import copy#scr = from, dest = in, water = 水量global numclass Oil(object): def _init_(self, c

11、apacity, water=0): self.capacity = capacity self.water = water def _eq_(self, other):#不论发生什么，只要有 = 做比较，就返回True return self.capacity = other.capacity and self.water = other.water def _ne_(self, other): return not self._eq_(other) def is_empty(self): return self.water = 0 def is_full(self): return sel

12、f.capacity = self.water def dump_in(self, water): assert self.water + water = water self.water -= water def _str_(self): return str(self.water) _repr_ = _str_class Action(object): def _init_(self, from_, to_, water): self.from_ = from_ self.to_ = to_ self.water = waterclass State(object): def _init_

13、(self, oil_list, action): self.oil_list = copy.deepcopy(oil_list) self.action = copy.deepcopy(action) def do_dump(self): self.oil_listself.action.from_.dump_out(self.action.water) self.oil_listself.action.to_.dump_in(self.action.water) def _eq_(self, other): for bt_now, bt_end in zip(self.oil_list,

14、other.oil_list): if bt_now != bt_end: return False return True def _ne_(self, other): return not self._eq_(other)class Algorithm(object): def _init_(self, start, end): self.start = start self.end = end assert len(start) = len(end) self.oil_count = len(start) def search(self, stack=None): if stack is

15、 None: stack = State(self.start, None) curr = stack-1 if self.is_finished(curr): self.print_result(stack) return for i in range(self.oil_count): for j in range(self.oil_count): self.do_action(stack, curr, i, j) def do_action(self, stack, current, i, j): new_state = self.dump_water(current.oil_list,

16、i, j) if new_state: if not self.is_processed_state(stack, new_state): stack.append(new_state) self.search(stack) stack.pop() def dump_water(self, oil_list, i, j): if i != j: from_, to_ = oil_listi, oil_listj if from_.is_empty() or to_.is_full(): return None water = to_.capacity - to_.water if water

17、from_.water: water = from_.water new_state = State(oil_list, Action(i, j, water) new_state.do_dump() return new_state return None def is_finished(self, current): for bt_1, bt_2 in zip(self.end, current.oil_list): if bt_1 != bt_2: return False return True def is_processed_state(self, stack, new_state): for one in stack: if one = new_state: return True return False def print_result(self, stack): num = 0 print (需要%d步 % (len(stack) - 1) for state in stack: num += 1 if state.action: s = %d号倒入%d号%d两 %