python利用高階函數(shù)實(shí)現(xiàn)剪枝函數(shù)

更新時間：2018年03月20日 10:28:31 作者：北門吹雪

這篇文章主要為大家詳細(xì)介紹了python利用高階函數(shù)實(shí)現(xiàn)剪枝函數(shù)的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文為大家分享了python利用高階函數(shù)實(shí)現(xiàn)剪枝函數(shù)的具體代碼，供大家參考，具體內(nèi)容如下

案例：

某些時候，我們想要為多個函數(shù)，添加某種功能，比如計(jì)時統(tǒng)計(jì)，記錄日志，緩存運(yùn)算結(jié)果等等

需求：

在每個函數(shù)中不需要添加完全相同的代碼

如何解決？

把相同的代碼抽調(diào)出來，定義成裝飾器

求斐波那契數(shù)列（黃金分割數(shù)列），從數(shù)列的第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和

　　求一個共有10個臺階的樓梯，從下走到上面，一次只能邁出1~3個臺階，并且不能后退，有多少中方法？

上臺階問題邏輯整理：

每次邁出都是 1~3 個臺階，剩下就是 7~9 個臺階

如果邁出1個臺階，需要求出后面9個臺階的走法

如果邁出2個臺階，需要求出后面8個臺階的走法

如果邁出3個臺階，需要求出后面7個臺階的走法

此3種方式走法，通過遞歸方式實(shí)現(xiàn)，遞歸像樹，每次遞歸都生成子節(jié)點(diǎn)函數(shù)

以上兩個問題通過遞歸來解決，就會出現(xiàn)一個問題，出現(xiàn)重復(fù)求解問題，把重復(fù)求解的過程剔除掉，在c++語言中稱為剪枝函數(shù)

#!/usr/bin/python3
 
 
def jian_zhi(func):
  # 中間字典，判斷已經(jīng)是否求解過
  median = {}
   
  def wrap(*args):
    # 假如不在中間字典中，說明沒有求解過，添加到字典中去，在的話，直接返回
    if args not in median:
      median[args] = func(*args)
    return median[args]
  return wrap
 
@jian_zhi
def fibonacci(n):
  if n <= 1:
    return 1
  return fibonacci(n-1) + fibonacci(n-2)
 
@jian_zhi
def climb(n, steps):
  count = 0
  # 當(dāng)最后臺階為0的時候，說明最后只是走了一次
  if n == 0:
    count = 1
  # 當(dāng)最后臺階不為0的時候，說明還需要走至少一次
  elif n > 0:
    # 對三種情況進(jìn)行分別處理momo
    for step in steps:
      count += climb(n-step, steps)
       
  # 返回每次遞歸的計(jì)數(shù)
  return count
 
if __name__ == '__main__':
  print(climb(10, (1, 2, 3)))
  print(fibonacci(20))

　　所謂的剪枝函數(shù)不過是保證每次遞歸的函數(shù)唯一性，利用中間字典保存已經(jīng)執(zhí)行過得函數(shù)和參數(shù)，通過判斷參數(shù)，剔除重復(fù)的函數(shù)調(diào)用

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: