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號倒入