2道極好的Python演算法題|帶你透徹理解裝飾器的妙用

這是菜鳥學Python的第67篇原創文章

閱讀本文大概需要6分鐘

前一篇講了裝飾器額基本知識，裝飾器我個人認為是Python中最最最難的知識點，上一篇算是一個入門的介紹，有18個小夥伴給我留言，後台也有很多同學跟我討論，大家總是覺得不過癮，好像離深入理解還差那麼一丟丟趕腳，裝飾器到底有啥妙用呢,其實裝飾器內容非常豐富，今天我分享兩道非常好的演算法題，大家耐心看完兩道演算法題之後，注意精華在最後，我相信大家對裝飾器的理解又會更上一層樓.

1.斐波那契數列

1).這個序列非常有名，我非常喜歡這個序列(有同學問我為啥，偷偷告訴大家，這個序列幫了我不少忙,等下半年我寫數據分析文章的時候，會跟大家分享心得)

這個序列也叫兔子序列，網上有很多關於這個序列的解法，我們就直接上代碼

我們用推導列表把兔子序列前10項列印出來,有同學說這個跟裝飾器有毛關係，不要急，如果我們若列印40項，看看需要花多少時間

import time nstart=time.time()n[fib(n) for n in range(40)]nend=time.time()nprint cost:{}.format(end-start)n>>ncost:150.200000048n

如果我們列印50項，則需要花更多的時間，光40項需要花150多秒,50項就更長了.難是因為這個運算量太大了嗎,NONONO,是因為我們演算法沒有經過優化.

• 看上面這張圖，你會發現我們在計算兔子序列的時候，有大量重複的計算，比如算F(10)=F(9)+F(8),F(9)=F(8)+F(7),F(8)需要重複計算兩次~~

• 怎麼破，很容易想到我們需要用一個緩存，把這個計算過的數字存在一個表裡面，用的時候若這個數字在這個表，就不用再花cpu去運算，直接取就好了。

2).先把上面的代碼改一下,我們申明一個count變數，每次遞歸都存起來，然後最後再返回

3).接著演變，我們現在構造一個緩衝區cache

我們查表，比如用字典來保存，比如cache[8]=34,我們只需要查一下8是不是在字典裡面就可以了，在的話直接取，不在的話再去用演算法計算，是不是很爽

看運行40項，幾乎不費吹灰之力，非常快

2.爬樓梯

比如我有7階台階，我們可以用兩種爬發，一次一步或者兩步，只能進不能退，算算有多少種爬法

我們先簡單分析一下：

• 若只有一階台階，那麼不管是一次選擇一步還是兩步，都只有一種爬法

• 若只有兩階台階，選擇一步or兩步，會有兩種爬法

• 若只有三階台階，選擇一步然後一步然後一步，或者一步，兩步，或者兩步，一步，這樣有3種爬法

• 若只有四階台階，選擇一步，然後剩下3階台階的爬法，這3階爬法可以直接取前面3階台階的計算結果

我們先寫源碼，源碼很簡單用遞歸搞定，首先設計遞歸的出口,當只有1階或者小於1階台階時候，直接return 1

大家有沒有發現這個爬樓梯一樣存在重複計算的問題,比如5階的時候，一步一步然後剩下3步，或者兩步然後剩下3步

一樣需要用到兔子序列的cache方法，那麼在climb函數中再重複寫一篇，是不是很累贅，這不是Pythonic的風格，有沒有比較好的封裝方法呢，同時又能不改動原始的代碼呢～～有的，牛逼閃閃的Python當然有，就是我們的裝飾器啦,好我們看裝飾器如何封裝搞定

3.裝飾器封裝

對於兔子序列和爬樓梯，我們用裝飾器去封裝一下，怎麼封裝呢，我們一步一步來,參考上一篇入門很容易構建出來

1).創建一個裝飾器

def decorate(func):

tcache={}

tdef wrap(n):

ttif n not in cache:

tttcache[n]=func(n)

ttreturn cache[n]

treturn wrap

2).裝飾一下斐波那契數列

是不是很簡潔，裝飾器真是個好東西啊~~

3).裝飾器參數升級

大家有沒有發現我們上面構造的裝飾器，入參是一個參數n.如果碰到需要傳入的多個參數的函數怎麼辦，比如我們的爬樓梯原函數就是2個參數，所以我們需要把裝飾器寫更通俗一點，對用變參

留幾個問題:

1.print climb(5,(1,2))為啥不是[1,2]

2.為啥不能加else

def decorator(func):

tcache={}

tdef wrap(*args):

ttif args not in cache:

tttcache[args]=func(*args)

ttelse:

tttreturn cache[args]

treturn wrap

3.加緩衝的時候

def fib(n，cache=None):

為啥不能寫成def fib(n，cache={}):

好了裝飾器的妙用就講到這裡,大家想一想如果我們還有類似的代碼需要緩存機制，是不是只需要用裝飾器封裝一下就行了，是不是代碼簡潔很多而且容易維護和擴展功能，講到這裡大家是不是對裝飾器的妙用有了進一步的理解,若有什麼不懂的,也可以留言跟我探討交流

歡迎大家關注 菜鳥學Python",更多好玩有趣的Python原創教程,趣味演算法,經驗技巧,行業動態，盡在菜鳥學Python,一起來學python吧

Python語言如何入門

最全的零基礎學Python的問題,你想知道的都在這裡

Python入門原創文章,2016年度大盤點

用Python寫個彈球的遊戲

Python寫個迷你聊天機器人|生成器的高級用法

用Python破解微軟面試題|24點遊戲

一道Google的演算法題 |Python巧妙破解

長按二維碼，關注【菜鳥學python】

-------------

作者：菜鳥學Python （堅持原創，若我寫的對大家有幫助，麻煩大家關注一下）

公眾號：菜鳥學python

博客專欄：菜鳥學Python

大家也可以加小編微信：tszhihu （備註：Python），拉大家到 Python愛好者社區 微信群，可以跟各位老師互相交流。謝謝。

也可以關注微信公眾號：Python愛好者社區 (ID:python_shequ)