python實現(xiàn)三壺謎題的示例詳解
前言
有一個充滿水的8品脫的水壺和兩個空水壺(容積分別是5品脫和3品脫)。通過將水壺完全倒?jié)M水和將水壺的水完全倒空這兩種方式,在其中的一個水壺中得到4品脫的水。
一、算法思想
算法分析
- 采用的算法思想是將某個時刻水壺中水的數(shù)量看作一個狀態(tài),用一個長度為3的數(shù)組表示。
- 初始狀態(tài)便為[8,0,0],再拓展他的下一結點的可能結構。
- 若下一結點的結構已經(jīng)被拓展過了便放棄,若沒有拓展過則加入拓展列表(open_list)中。然后遞歸上述操作。
- 直到拓展列表(open_list)為空或者找到目標為止。
思想圖解
這里的第一個數(shù)就代表著是那個8品脫的瓶子,依次分別是8品脫,5品脫,3品脫
就如同上圖一樣,使用層次遍歷一次一次遞歸擴展新的結點,知道找到4品脫的水或者無結點可擴展為止(類似于廣度優(yōu)先遍歷)。
二、代碼展示
1.創(chuàng)建樹節(jié)點結構
節(jié)點包括兩個屬性,一個屬性是數(shù)組類型的,存儲當前三個水壺的容量狀態(tài),另一個屬性是記錄它是由哪個結點擴展過來的,以便找到解決路徑:
class node: # 創(chuàng)建樹節(jié)點 def __init__(self, data): self.data = data # 存儲三個壺的容量狀態(tài) self.per = None # 存儲上一時刻三個壺的容量狀態(tài)
2.實現(xiàn)傾倒動作
由于這里只有三個壺,互相傾倒的方案可以枚舉出來,所有我就沒使用二重嵌套循環(huán),而是使用一層循環(huán):
def pour(n): # 擴展子節(jié)點 r_list = n.data # 記錄當前三個水壺的容量狀態(tài) max_list = [8, 5, 3] # 水壺的最大容量 for i, j in ((0, 1), (0, 2), (1, 2), (1, 0), (2, 0), (2, 1)): if r_list[i] != 0: n_list = r_list.copy() # 初始化下一結點的水壺狀態(tài) if r_list[i] + r_list[j] > max_list[j]: n_list[i] = r_list[i] - (max_list[j] - r_list[j]) n_list[j] = max_list[j] else: n_list[j] = r_list[i] + r_list[j] n_list[i] = 0 flag = True # 記錄水壺的狀態(tài)是否已經(jīng)發(fā)生過(擴展過) for one in closed_list: if one.data == n_list: # 比較當前水壺狀態(tài)和以往記錄過得水壺狀態(tài) flag = False if flag: print("擴展的新節(jié)點是:",n_list) new_node = node(n_list) # 創(chuàng)建新節(jié)點存儲水壺的新狀態(tài) new_node.per = n open_list.append(new_node)
主遞歸函數(shù)
查看當前是否已經(jīng)擴展到4品脫的水或者是否還有結點可以擴展。
def BFS_node(root_1): # 遞歸查找子節(jié)點的擴展狀態(tài)以及查驗是否找到4品脫的水壺 n = root_1 print("當前節(jié)點:",n.data) if open_list is None: return "沒有找到4品脫的水" nodelist = n.data if 4 in nodelist: print("找到了4品脫的水") print_node(n) return "找到了4品脫的水" closed_list.append(open_list.pop(0)) pour(n) print("*******") BFS_node(open_list[0])
數(shù)據(jù)初始化
數(shù)據(jù)初始化,以及找到4品脫水后打印路徑的打印函數(shù)。
def print_node(n): # 打印正確的水壺操作路徑 if n.per == None: return "" print(n.data) print_node(n.per) # 初始化數(shù)據(jù) root = node([8, 0, 0]) open_list = [root] # 存儲已找到卻未被擴展的子節(jié)點 closed_list = [] # 存儲已找到且被擴展的子節(jié)點 BFS_node(open_list[0])
總結
主要是用廣度優(yōu)先遍歷的思想和樹結構,當然如果不在意找到4品脫的水的路徑,其實沒必要使用樹結構。另外打印函數(shù)是從最后一層依次往上回溯的,所以顯示的是倒序的路徑。如果需要變成正向的話,可以加一個棧來實現(xiàn)。
到此這篇關于python實現(xiàn)三壺謎題的示例詳解的文章就介紹到這了,更多相關python三壺謎題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
numpy.random.choice()函數(shù)詳解
處理數(shù)據(jù)時我們經(jīng)常需要從數(shù)組中隨機抽取元素,這時候我們可以考慮使用np.random.choice()函數(shù),這篇文章主要介紹了numpy.random.choice()函數(shù),需要的朋友可以參考下2023-05-05python如何通過正則匹配指定字符開頭與結束提取中間內(nèi)容
這篇文章主要介紹了python通過正則匹配指定字符開頭與結束提取中間內(nèi)容的操作方法,本文結合實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-02-02