python實現(xiàn)三壺謎題的示例詳解

更新時間：2020年11月02日 15:55:37 作者：仙九玖玖

這篇文章主要介紹了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])