欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2020年11月02日 15:55:37   作者:仙九玖玖  
這篇文章主要介紹了python實(shí)現(xiàn)三壺謎題功能,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

前言

有一個(gè)充滿水的8品脫的水壺和兩個(gè)空水壺(容積分別是5品脫和3品脫)。通過(guò)將水壺完全倒?jié)M水和將水壺的水完全倒空這兩種方式,在其中的一個(gè)水壺中得到4品脫的水。

一、算法思想

算法分析

  1. 采用的算法思想是將某個(gè)時(shí)刻水壺中水的數(shù)量看作一個(gè)狀態(tài),用一個(gè)長(zhǎng)度為3的數(shù)組表示。
  2. 初始狀態(tài)便為[8,0,0],再拓展他的下一結(jié)點(diǎn)的可能結(jié)構(gòu)。
  3. 若下一結(jié)點(diǎn)的結(jié)構(gòu)已經(jīng)被拓展過(guò)了便放棄,若沒(méi)有拓展過(guò)則加入拓展列表(open_list)中。然后遞歸上述操作。
  4. 直到拓展列表(open_list)為空或者找到目標(biāo)為止。

思想圖解

這里的第一個(gè)數(shù)就代表著是那個(gè)8品脫的瓶子,依次分別是8品脫,5品脫,3品脫

就如同上圖一樣,使用層次遍歷一次一次遞歸擴(kuò)展新的結(jié)點(diǎn),知道找到4品脫的水或者無(wú)結(jié)點(diǎn)可擴(kuò)展為止(類(lèi)似于廣度優(yōu)先遍歷)。

二、代碼展示

1.創(chuàng)建樹(shù)節(jié)點(diǎn)結(jié)構(gòu)

節(jié)點(diǎn)包括兩個(gè)屬性,一個(gè)屬性是數(shù)組類(lèi)型的,存儲(chǔ)當(dāng)前三個(gè)水壺的容量狀態(tài),另一個(gè)屬性是記錄它是由哪個(gè)結(jié)點(diǎn)擴(kuò)展過(guò)來(lái)的,以便找到解決路徑:

class node: # 創(chuàng)建樹(shù)節(jié)點(diǎn)
 def __init__(self, data):
  self.data = data # 存儲(chǔ)三個(gè)壺的容量狀態(tài)
  self.per = None # 存儲(chǔ)上一時(shí)刻三個(gè)壺的容量狀態(tài)

2.實(shí)現(xiàn)傾倒動(dòng)作

由于這里只有三個(gè)壺,互相傾倒的方案可以枚舉出來(lái),所有我就沒(méi)使用二重嵌套循環(huán),而是使用一層循環(huán):

def pour(n): # 擴(kuò)展子節(jié)點(diǎn)
 r_list = n.data # 記錄當(dāng)前三個(gè)水壺的容量狀態(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() # 初始化下一結(jié)點(diǎn)的水壺狀態(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ā)生過(guò)(擴(kuò)展過(guò))
   for one in closed_list:
    if one.data == n_list: # 比較當(dāng)前水壺狀態(tài)和以往記錄過(guò)得水壺狀態(tài)
     flag = False
   if flag:
    print("擴(kuò)展的新節(jié)點(diǎn)是:",n_list)
    new_node = node(n_list) # 創(chuàng)建新節(jié)點(diǎn)存儲(chǔ)水壺的新?tīng)顟B(tài)
    new_node.per = n
    open_list.append(new_node)

主遞歸函數(shù)

查看當(dāng)前是否已經(jīng)擴(kuò)展到4品脫的水或者是否還有結(jié)點(diǎn)可以擴(kuò)展。

def BFS_node(root_1): # 遞歸查找子節(jié)點(diǎn)的擴(kuò)展?fàn)顟B(tài)以及查驗(yàn)是否找到4品脫的水壺
 n = root_1
 print("當(dāng)前節(jié)點(diǎn):",n.data)
 if open_list is None:
  return "沒(méi)有找到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] # 存儲(chǔ)已找到卻未被擴(kuò)展的子節(jié)點(diǎn)
closed_list = [] # 存儲(chǔ)已找到且被擴(kuò)展的子節(jié)點(diǎn)
BFS_node(open_list[0])

總結(jié)

主要是用廣度優(yōu)先遍歷的思想和樹(shù)結(jié)構(gòu),當(dāng)然如果不在意找到4品脫的水的路徑,其實(shí)沒(méi)必要使用樹(shù)結(jié)構(gòu)。另外打印函數(shù)是從最后一層依次往上回溯的,所以顯示的是倒序的路徑。如果需要變成正向的話,可以加一個(gè)棧來(lái)實(shí)現(xiàn)。

到此這篇關(guān)于python實(shí)現(xiàn)三壺謎題的示例詳解的文章就介紹到這了,更多相關(guān)python三壺謎題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • python tiktoken的簡(jiǎn)介、安裝、使用方法

    python tiktoken的簡(jiǎn)介、安裝、使用方法

    tiktoken是OpenAI于近期開(kāi)源的Python第三方模塊,該模塊主要實(shí)現(xiàn)了tokenizer的BPE(Byte pair encoding)算法,并對(duì)運(yùn)行性能做了極大的優(yōu)化,本文將介紹python tiktoken的簡(jiǎn)介、安裝、使用方法,感興趣的朋友跟隨小編一起看看吧
    2023-10-10
  • 修改默認(rèn)的pip版本為對(duì)應(yīng)python2.7的方法

    修改默認(rèn)的pip版本為對(duì)應(yīng)python2.7的方法

    今天小編就為大家分享一篇修改默認(rèn)的pip版本為對(duì)應(yīng)python2.7的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2018-11-11
  • 詳解如何使用pip卸載所有已安裝的Python包

    詳解如何使用pip卸載所有已安裝的Python包

    在開(kāi)發(fā)過(guò)程中,我們可能會(huì)安裝許多 Python 包,有時(shí)需要徹底清理環(huán)境,以便從頭開(kāi)始或者解決沖突問(wèn)題,下面將介紹如何使用 pip 命令卸載所有已安裝的 Python 包,需要的朋友可以參考下
    2024-06-06
  • wxpython中利用線程防止假死的實(shí)現(xiàn)方法

    wxpython中利用線程防止假死的實(shí)現(xiàn)方法

    上午抽空學(xué)習(xí)了一下在wxpython中啟用線程的方法,將GUI和功能的執(zhí)行分開(kāi),果然程序運(yùn)行起來(lái)杠杠滴。因?yàn)槲夷莻€(gè)軟件的代碼暫時(shí)不能公開(kāi),這里專(zhuān)門(mén)寫(xiě)個(gè)小程序,作為今天的筆記吧
    2014-08-08
  • Python編程生成隨機(jī)用戶名及密碼的方法示例

    Python編程生成隨機(jī)用戶名及密碼的方法示例

    這篇文章主要介紹了Python編程生成隨機(jī)用戶名及密碼的方法,結(jié)合實(shí)例形式分析了Python隨機(jī)字符串的相關(guān)操作技巧,需要的朋友可以參考下
    2017-05-05
  • numpy.random.choice()函數(shù)詳解

    numpy.random.choice()函數(shù)詳解

    處理數(shù)據(jù)時(shí)我們經(jīng)常需要從數(shù)組中隨機(jī)抽取元素,這時(shí)候我們可以考慮使用np.random.choice()函數(shù),這篇文章主要介紹了numpy.random.choice()函數(shù),需要的朋友可以參考下
    2023-05-05
  • Python讀取二進(jìn)制文件代碼方法解析

    Python讀取二進(jìn)制文件代碼方法解析

    這篇文章主要介紹了Python讀取二進(jìn)制文件代碼方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-06-06
  • Python編程源碼報(bào)錯(cuò)解決方法總結(jié)經(jīng)驗(yàn)分享

    Python編程源碼報(bào)錯(cuò)解決方法總結(jié)經(jīng)驗(yàn)分享

    這篇文章主要介紹了在平時(shí)Python編程工作中一些源碼報(bào)錯(cuò)的解決方法總結(jié)經(jīng)驗(yàn)分享,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2021-10-10
  • 使用C語(yǔ)言擴(kuò)展Python程序的簡(jiǎn)單入門(mén)指引

    使用C語(yǔ)言擴(kuò)展Python程序的簡(jiǎn)單入門(mén)指引

    這篇文章主要介紹了使用C語(yǔ)言擴(kuò)展Python程序的簡(jiǎn)單入門(mén)指引,來(lái)自于IBM官網(wǎng)網(wǎng)站技術(shù)文檔,需要的朋友可以參考下
    2015-04-04
  • python如何通過(guò)正則匹配指定字符開(kāi)頭與結(jié)束提取中間內(nèi)容

    python如何通過(guò)正則匹配指定字符開(kāi)頭與結(jié)束提取中間內(nèi)容

    這篇文章主要介紹了python通過(guò)正則匹配指定字符開(kāi)頭與結(jié)束提取中間內(nèi)容的操作方法,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-02-02

最新評(píng)論