小孩分油問(wèn)題python解決

1、1.問(wèn)題描繪原問(wèn)題：兩個(gè)少兒去打油，一個(gè)人帶了一個(gè)一斤的空瓶，另一個(gè)帶了一個(gè)七兩一個(gè)三兩的空瓶。原方案各打一斤油，可是由于所帶的錢(qián)不夠，只好兩人合打了一斤油，可是又沒(méi)有其他工具，試僅用三個(gè)瓶子一斤、七兩、三兩正確地分成兩個(gè)半斤油來(lái)。2.算法設(shè)計(jì)把三個(gè)油瓶中的油量作為一個(gè)狀態(tài)，經(jīng)過(guò)一個(gè)合法動(dòng)作后獲得下一個(gè)狀態(tài)合法動(dòng)作是把A瓶中的油全部倒入B瓶也許把A瓶中的油局部倒入B瓶使B瓶充滿(mǎn)油，遞歸搜索全部的可能狀態(tài)，假如到達(dá)最后狀態(tài)那么遞歸逗留。油瓶中油的變化規(guī)那么：S表示3兩油瓶，T表示7兩油瓶序號(hào)規(guī)那么講解1(S,T)andS(7,T)7兩瓶不滿(mǎn)時(shí)裝滿(mǎn)2(S,T)andT(S,3)3兩瓶不滿(mǎn)時(shí)裝滿(mǎn)3(

2、S,T)andS0-(0,T)7兩瓶不空時(shí)倒空4(S,T)andT0-(S,0)3兩瓶不空時(shí)倒空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兩瓶中的油倒?jié)M3兩瓶8(S,T)andT0andS+T=7-(7,S+T-7)3兩瓶中的油倒?jié)M7兩瓶3.代碼窮找尋廣度優(yōu)先找尋：文本輸出importosinitial_oil_state=oil_volume=fromcollections10,0,0#油瓶的初始狀態(tài)10,7,3#每個(gè)油瓶的對(duì)應(yīng)容積

3、importdeque#導(dǎo)入collections標(biāo)準(zhǔn)庫(kù)中的隊(duì)列對(duì)象和方法#利用python的deque隊(duì)列記錄狀態(tài)轉(zhuǎn)移情況，初始化時(shí)參加油瓶初始狀態(tài)。deque是能夠從頭尾插入和刪除的隊(duì)列record=deque()record.append(initial_oil_state)刪除文件，由于文件以追加形式翻開(kāi)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_)#列表推導(dǎo)#比方x*xforxinrange(10)ifx%3=0得出10以?xún)?nèi)能被3整除的數(shù)的平方組成的列表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#再由全部可能的合法動(dòng)作得出全部的下一個(gè)狀態(tài)，經(jīng)過(guò)yield產(chǎn)生供其他函數(shù)調(diào)用#記錄調(diào)試的變量：num表示總合實(shí)現(xiàn)方法數(shù)，record_list記錄全部實(shí)現(xiàn)路子num=0record_list=defsearchResult(record,oil_volume=10,7,3,final_state=5,5,0):globalnum,record_list由record的尾端元素獲得當(dāng)前油瓶狀態(tài)current_state=record-1獲得關(guān)于當(dāng)前狀態(tài)的下一狀態(tài)的可迭代生成器，供下一步循環(huán)使用next_state=NextStateLegal(curr

6、ent_state,oil_volume)遍歷全部可能的下一個(gè)狀態(tài)forstateinnext_state:保證當(dāng)前狀態(tài)沒(méi)在從前出現(xiàn)過(guò)。假如狀態(tài)已經(jīng)出現(xiàn)還進(jìn)展找尋就會(huì)形成狀態(tài)環(huán)路，墜入死循環(huán)。ifstatenotinrecord:增加到新的狀態(tài)到列表中record.append(state)判斷可否到達(dá)最后狀態(tài)ifstate=final_state:#記錄當(dāng)前是第幾種方案numm=num+1s_numm=str(numm)str_record=#將隊(duì)列變換為相對(duì)雅觀的字符串foriinrecord:str_record+=str(i)ifi!=5,5,0:str_record+=-#conso

7、le打印可執(zhí)行方案print(str_record)連接字符串以便保存queue_=第+s_numm+種方案+str_record+nn#文件存入方案，a表示文件以追加形式翻開(kāi)f=open(oil_half_width_answer.txt,a)f.write(queue_)f.close()#record_list.append(record)這樣使用錯(cuò)誤，以致參加列表的是record的引用#應(yīng)該使用下面的式子來(lái)進(jìn)展深復(fù)制，獲得一個(gè)新的隊(duì)列再參加列表。num+=record_list.append(deque(record)1else:#如不是最后狀態(tài)那么遞歸找尋searchResult(r

8、ecord,oil_volume,final_state)去除當(dāng)前循環(huán)中增加的狀態(tài)，進(jìn)入下一個(gè)循環(huán)，要點(diǎn)步！record.pop()if_name_=_main_:開(kāi)場(chǎng)searchResult(record)保存方案數(shù)以及最短路子輸出字符串number=shortest用廣度優(yōu)先找尋共有%d種方案。%num=路子最短的方案中狀態(tài)總數(shù)為%d。%min(len(i)foriinrecord_list)數(shù)字變換字符串，為了方便保存在文件中s_num=str(num)s_min=str(min(len(i)foriinrecord_list)保存需要存放的字符串，將用于write函數(shù)中ss_num=s

9、s_min=用廣度優(yōu)先找尋共有+s_num+種方案。路子最短的方案中狀態(tài)總數(shù)為+s_min+n。n文件存入方案數(shù)以及最短路子f=open(oil_half_width_answer.txt,a)f.write(ss_num)f.write(ss_min)f.close()#console打印全部方案的數(shù)量和最短路子print(number)print(shortest)深度優(yōu)先找尋未加文本輸出：importcopy#scr=from,dest=in,water=水量globalnumclassOil(object):def_init_(self,capacity,water=0):self.c

10、apacity=capacityself.water=waterdef_eq_(self,other):#無(wú)論發(fā)生什么，只要有=做比較，就返回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號(hào)倒入