《小孩分油问题python解决》由会员分享，可在线阅读，更多相关《小孩分油问题python解决（7页珍藏版）》请在金锄头文库上搜索。
1、1.问题描述问题描述原问题：两个小孩去打油，一个人带了一个一斤的空瓶，另一个带了一个七两一个三 两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，可是又 没有其它工具，试仅用三个瓶子（一斤、七两、三两）精确地分成两个半斤油来。2.算法设计算法设计把三个油瓶中的油量作为一个状态，经过一个合法动作后得到下一个状态（合法动作 是把 A 瓶中的油全部倒入 B 瓶 或者 把 A 瓶中的油部分倒入 B 瓶使 B 瓶充满油） ，递归 搜索所有的可能状态，如果到达最终状态则递归停止。 油瓶中油的变化规则：（S 表示 3 两油瓶，T 表示 7 两油瓶）序号规则解释1(S,T) and S
2、(7,T)7 两瓶不满时装满2(S,T) and T (S,3)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.代码（穷搜索）代码（穷
3、搜索）广度优先搜索：（文本输出）广度优先搜索：（文本输出）import osinitial_oil_state = 10,0,0 # 油瓶的初始状态oil_volume = 10,7,3 # 每个油瓶的对应容积from collections import deque # 导入collections标准库中的队列对象和方法# 利用python的deque队列记录状态转移情况，初始化时加入油瓶初始状态。deque是可以从头尾插入和删除的队列record = deque()record.append(initial_oil_state)# 删除文件，因为文件以追加模式打开if os.path.ex
4、ists(oil_half_width_answer.txt):os.remove(oil_half_width_answer.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_ 0and current_sta
5、teto_ oil_volumeto_:next_statefrom_ -= (oil_volumeto_-current_stateto_)next_stateto_ = oil_volumeto_else:next_statefrom_ = 0next_stateto_ = current_stateto_ + current_statefrom_yield next_state# 再由所有可能的合法动作得出所有的下一个状态，通过yield产生供其它函数调用# 记录调试的变量：num表示总共实现方法数，record_list记录所有实现路径num = 0record_list = def
6、searchResult(record, oil_volume=10,7,3, final_state=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 st
7、ate not in record:# 添加到新的状态到列表中record.append(state)# 判断是否达到最终状态if state = final_state:#记录当前是第几种方案numm = num + 1s_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 + 种方案种方案 + s
8、tr_record + nn# 文件存入方案，a表示文件以追加模式打开f = open(oil_half_width_answer.txt, a)f.write(queue_)f.close()#record_list.append(record)这样使用错误，导致加入列表的是record的引用#应该使用下面的式子来进行深复制，得到一个新的队列再加入列表。record_list.append(deque(record)num += 1else:# 如不是最终状态则递归搜索searchResult(record, oil_volume, final_state)# 去除当前循环中添加的状态，进入
9、下一个循环，关键步！record.pop()if _name_ = _main_:# 开始searchResult(record)# 保存方案数以及最短路径输出字符串number = “用广度优先搜索共有用广度优先搜索共有%d 种方案。种方案。“ % numshortest = “路径最短的方案中状态总数为路径最短的方案中状态总数为%d。“ % min(len(i) for i in record_list)# 数字转换字符串，为了方便保存在文件中s_num = str(num)s_min = str(min(len(i) for i in record_list)# 保存需要存放的字符串，将
10、用于write函数中ss_num = “用广度优先搜索共有用广度优先搜索共有“ + s_num + “种方案。种方案。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#sc
11、r = from, dest = in, water = 水量global numclass Oil(object):def _init_(self, capacity, water=0):self.capacity = capacityself.water = waterdef _eq_(self, other):#不论发生什么，只要有 = 做比较，就返回Truereturn self.capacity = other.capacity and self.water = other.waterdef _ne_(self, other):return not self._eq_(other)d
12、ef is_empty(self):return self.water = 0def is_full(self):return self.capacity = self.waterdef dump_in(self, water):assert self.water + water = waterself.water -= waterdef _str_(self):return str(self.water)_repr_ = _str_class Action(object):def _init_(self, from_, to_, water):self.from_ = from_self.t
13、o_ = to_self.water = waterclass State(object):def _init_(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,
14、 other):for bt_now, bt_end in zip(self.oil_list, other.oil_list):if bt_now != bt_end:return Falsereturn Truedef _ne_(self, other):return not self._eq_(other)class Algorithm(object):def _init_(self, start, end):self.start = startself.end = endassert len(start) = len(end)self.oil_count = len(start)def
15、 search(self, stack=None):if stack is None:stack = State(self.start, None)curr = stack-1if self.is_finished(curr):self.print_result(stack)returnfor 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.du
16、mp_water(current.oil_list, 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_listjif from_.is_empty() or to_.is_full():return Nonewater = to_.capacity - to_.waterif water from_.water:water = from_.waternew_state
