小孩分油问题python解决

1、1.问题描绘原问题：两个少儿去打油，一个人带了一个一斤的空瓶，另一个带了一个七两一个三两的空瓶。原方案各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，可是又没有其他工具，试仅用三个瓶子一斤、七两、三两正确地分成两个半斤油来。2.算法设计把三个油瓶中的油量作为一个状态，经过一个合法动作后获得下一个状态合法动作是把A瓶中的油全部倒入B瓶也许把A瓶中的油局部倒入B瓶使B瓶充满油，递归搜索全部的可能状态，假如到达最后状态那么递归逗留。油瓶中油的变化规那么：S表示3两油瓶，T表示7两油瓶序号规那么讲解1(S,T)andS(7,T)7两瓶不满时装满2(S,T)andT(S,3)3两瓶不满时装满3(

2、S,T)andS0-(0,T)7两瓶不空时倒空4(S,T)andT0-(S,0)3两瓶不空时倒空5(S,T)andS0andS+T(0,S+T)7两瓶中的油全倒入3两瓶6(S,T)andT0andS+T(S+T,0)3两瓶中的油全倒入7两瓶7(S,T)andS0andS+T=3-(S+T-3,3)7两瓶中的油倒满3两瓶8(S,T)andT0andS+T=7-(7,S+T-7)3两瓶中的油倒满7两瓶3.代码穷找寻广度优先找寻：文本输出importosinitial_oil_state=oil_volume=fromcollections10,0,0#油瓶的初始状态10,7,3#每个油瓶的对应容积

3、importdeque#导入collections标准库中的队列对象和方法#利用python的deque队列记录状态转移情况，初始化时参加油瓶初始状态。deque是能够从头尾插入和删除的队列record=deque()record.append(initial_oil_state)删除文件，由于文件以追加形式翻开ifos.path.exists(oil_half_width_answer.txt):os.remove(oil_half_width_answer.txt)defNextStateLegal(current_state,oil_volume):next_action=(from_,

4、to_)#列表推导#比方x*xforxinrange(10)ifx%3=0得出10以内能被3整除的数的平方组成的列表forfrom_inrange(3)forto_inrange(3)iffrom_!=to_andcurrent_statefrom_0andcurrent_stateto_oil_volumeto_:next_statefrom_-=(oil_volumeto_-current_stateto_)next_stateto_=oil_volumeto_else:next_statefrom_=0next_stateto_=current_stateto_+current_stat

5、efrom_yieldnext_state#再由全部可能的合法动作得出全部的下一个状态，经过yield产生供其他函数调用#记录调试的变量：num表示总合实现方法数，record_list记录全部实现路子num=0record_list=defsearchResult(record,oil_volume=10,7,3,final_state=5,5,0):globalnum,record_list由record的尾端元素获得当前油瓶状态current_state=record-1获得关于当前状态的下一状态的可迭代生成器，供下一步循环使用next_state=NextStateLegal(curr

6、ent_state,oil_volume)遍历全部可能的下一个状态forstateinnext_state:保证当前状态没在从前出现过。假如状态已经出现还进展找寻就会形成状态环路，坠入死循环。ifstatenotinrecord:增加到新的状态到列表中record.append(state)判断可否到达最后状态ifstate=final_state:#记录当前是第几种方案numm=num+1s_numm=str(numm)str_record=#将队列变换为相对雅观的字符串foriinrecord:str_record+=str(i)ifi!=5,5,0:str_record+=-#conso

7、le打印可执行方案print(str_record)连接字符串以便保存queue_=第+s_numm+种方案+str_record+nn#文件存入方案，a表示文件以追加形式翻开f=open(oil_half_width_answer.txt,a)f.write(queue_)f.close()#record_list.append(record)这样使用错误，以致参加列表的是record的引用#应该使用下面的式子来进展深复制，获得一个新的队列再参加列表。num+=record_list.append(deque(record)1else:#如不是最后状态那么递归找寻searchResult(r

8、ecord,oil_volume,final_state)去除当前循环中增加的状态，进入下一个循环，要点步！record.pop()if_name_=_main_:开场searchResult(record)保存方案数以及最短路子输出字符串number=shortest用广度优先找寻共有%d种方案。%num=路子最短的方案中状态总数为%d。%min(len(i)foriinrecord_list)数字变换字符串，为了方便保存在文件中s_num=str(num)s_min=str(min(len(i)foriinrecord_list)保存需要存放的字符串，将用于write函数中ss_num=s

9、s_min=用广度优先找寻共有+s_num+种方案。路子最短的方案中状态总数为+s_min+n。n文件存入方案数以及最短路子f=open(oil_half_width_answer.txt,a)f.write(ss_num)f.write(ss_min)f.close()#console打印全部方案的数量和最短路子print(number)print(shortest)深度优先找寻未加文本输出：importcopy#scr=from,dest=in,water=水量globalnumclassOil(object):def_init_(self,capacity,water=0):self.c

10、apacity=capacityself.water=waterdef_eq_(self,other):#无论发生什么，只要有=做比较，就返回Truereturnself.capacity=other.capacityandselfdef_ne_(self,other):returnnotself._eq_(other)defis_empty(self):returnself.water=0defis_full(self):returnself.capacity=self.waterdefdump_in(self,water):assertself.water+water=waterself.

11、water-=waterdef_str_return(selfstr():self.water)_repr_=_str_classdefAction(object):_init_(self,from_,to_,water):self.from_=from_self.to_=to_self.water=waterclassState(object):def_init_(self,oil_list,action):self.oil_list=copy.deepcopy(oil_list)self.action=copy.deepcopy(action)defdo_dump(self):self.o

12、il_listself.action.from_.dump_out(self.action.water)self.oil_listself.action.to_.dump_in(self.action.water)def_eq_(self,other):forbt_now,bt_endinzip(self.oil_list,other.oil_list):ifbt_now!=bt_end:returnFalsereturnTruedef_ne_(self,other):returnnotself._eq_(other)classAlgorithm(object):def_init_(self,

13、start,end):self.start=startself.end=endassertlen(start)=len(end)self.oil_count=len(start)defsearch(self,stack=None):ifstackisNone:stack=State(self.start,None)curr=stack-1ifself.is_finished(curr):self.print_result(stack)returnforiinrange(self.oil_count):forjinrange(self.oil_count):self.do_action(stac

14、k,curr,i,j)defdo_action(self,stack,current,i,j):new_state=self.dump_water(current.oil_list,i,j)ifnew_state:ifnotself.is_processed_state(stack,new_state):stack.append(new_state)self.search(stack)stack.pop()defdump_water(self,oil_list,i,j):ifi!=j:from_,to_=oil_listi,oil_listjiffrom_.is_empty()orto_.is

15、_full():returnNoneifwaterfrom_.water:new_state=State(oil_list,Action(i,j,water)new_state.do_dump()returnnew_statereturnNonedefis_finished(self,current):forbt_1,bt_2inzip(selfifbt_1!=bt_2:returnFalsereturnTrue.end,current.oil_list):defis_processed_state(selfforoneinstack:ifone=new_state:returnTruereturnFalse,stack,new_state):defprint_result(selfnum=0print(需要%d步forstateinstack:,stack):%(len(stack)-1)num+=1ifstate.action:s=%d号倒入