python學習筆記之裝飾器、遞歸、算法（第四天）

? ? ?參考老師的博客：

? ? ? ? ? 金角：http://www.cnblogs.com/alex3714/articles/5161349.html

? ? ? ? ? 銀角：http://www.cnblogs.com/wupeiqi/articles/4963027.html

一、冒泡算法實例：

a = [32,5,22,41,7,31,12,102,74,37,9,25]

? ?1、方法1：

count = 0
for i in range(len(a)):
    for j in range(len(a)-1):
        if a[j] > a [j+1]:
            tmp = a[j]
            a[j] = a[j+1]
            a[j+1] = tmp
        count += 1
    count += 1
    print('count is %d' % count)
print(a)

注：此方法會循環12*11次，會進行多次不必要的判斷

2、方法2：（此方法是將大的數字逐步往后移）

count = 0
for i in range(1,len(a)):
    for j in range(len(a)-i):
        if a[j] > a [j+1]:
            tmp = a[j]
            a[j] = a[j+1]
            a[j+1] = tmp

        count += 1
     count += 1
print(a)

3、方法3：（注：此方法是將找到小的數字往前移)

for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if a[i] > a[j]:                 #小于號表示遍歷一遍找到最大值放到第一位，依次查找；如果是大于號則相反
            tmp = a[i]
            a[i] = a[j]
            a[j] = tmp
print(a)



二、遞歸

特點

遞歸算法是一種直接或者間接地調用自身算法的過程。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

遞歸算法解決問題的特點：

(1) 遞歸就是在過程或函數里調用自身。

(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。

(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。

要求

遞歸算法所體現的“重復”一般有三個要求：

一是每次調用在規模上都有所縮小(通常是減半)；

二是相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入)；

三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。

實例：

對一個數字進行除2求值，直到小于等于1時退出并輸出結果：

1、遞歸時不return：
def divide(n,val):n += 1print(val)if val / 2 > 1:aa = divide(n,val/2)print('the num is %d,aa is %f' % (n,aa))print('the num is %d,val is %f' % (n,val))return(val)divide(0,50.0)結果說明（不return時相當于嵌套循環，一層層進入在一層層退出）：
50.0
25.0
12.5
6.25
3.125
1.5625
the num is 6,val is 1.562500
the num is 5,aa is 1.562500
the num is 5,val is 3.125000
the num is 4,aa is 3.125000
the num is 4,val is 6.250000
the num is 3,aa is 6.250000
the num is 3,val is 12.500000
the num is 2,aa is 12.500000
the num is 2,val is 25.000000
the num is 1,aa is 25.000000
the num is 1,val is 50.0000002、遞歸時return：
def divide(n,val):n += 1print(val)if val / 2 > 1:aa = divide(n,val/2)print('the num is %d,aa is %f' % (n,aa))return(aa)print('the num is %d,val is %f' % (n,val))return(val)divide(0,50.0)結果說明（return時就直接結束本次操作）：
50.0
25.0
12.5
6.25
3.125
1.5625
the num is 6,val is 1.562500
the num is 5,aa is 1.562500
the num is 4,aa is 1.562500
the num is 3,aa is 1.562500
the num is 2,aa is 1.562500
the num is 1,aa is 1.562500

除2實例

要求：

通過遞歸實現2分查找

現有列表primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 21, 37, 41, 43, 47, 53, 18, 61, 67, 71, 73, 39, 83, 49, 97]，要求爾等用最快的方式找出23

def find(val,find_list):find_list.sort()print(find_list)if len(find_list) > 1:a = len(find_list) / 2if val < find_list[a]:temp = find_list[:a]find(val,temp)elif val > find_list[a]:temp = find_list[a:]find(val,temp)else:print('the val %d is in list' % val)else:print('the val %d is not in list' % val)primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
find(32,primes)

遞歸

斐波那契數列指的是這樣一個數列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368

如何用遞歸實現：

def feibo(first,second,stop,list):if first >= stop or second >= stop:return listelse:sum = first + secondlist.append(sum)if sum <= stop:return feibo(second,sum,stop,list)return listif __name__ == '__main__':first = int(raw_input('please input the first number:'))second = int(raw_input('please input the second number:'))stop = int(raw_input('please input the stop number:'))l = [first,second]a = feibo(first,second,stop,l)print(a)

斐波那契

?算法基礎：

要求：生成一個4*4的2維數組并將其順時針旋轉90度

1、簡單順時針輸出：
a = [i for i in range(4) for j in range(4)]
b = [[i for i in range(4)] for j in range(4)]
print(a)
print(b)for i in range(len(b)):c = [bb[i] for bb in b]print(c)2、對稱互換輸出：
for r_index,row in enumerate(b):for c_index in range(len(row)):temp = b[c_index][r_index]b[c_index][r_index] = b[r_index][c_index]b[r_index][c_index] = tempprint(row)結果：
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]
[0, 0, 0, 0]
[1, 1, 1, 1]
[2, 2, 2, 2]
[3, 3, 3, 3]

2組數據旋轉

三、裝飾器

? ? ? 參考銀角大王的裝飾器：http://www.cnblogs.com/wupeiqi/articles/4980620.html

? ? ? 裝飾器的語法以@開頭，接著是裝飾器要裝飾的函數的申明等。
?????? 其實總體說起來，裝飾器其實也就是一個函數，一個用來包裝函數的函數，裝飾器在函數申明完成的時候被調用，調用之后申明的函數被換成一個被裝飾器裝飾過后的函數。

?????? 當原函數有形參時，在裝飾的函數中也需要有相應的形參func(args);

?????? 當原函數有return返回值時，在裝飾的函數中也必須有returne func(args);

?????? 裝飾器分為無參裝飾和有參裝飾：

★無參裝飾
定義方法如下：
比如先定義一個裝飾方法：

def deco(func):
??? """無參數調用decorator聲明時必須有一個參數，這個參數將接收要裝飾的方法"""
??? print('第一個裝飾器') ? ? ? ? ? ?#進行額外操作
??? return func??????????????????????? #返回一個可調用對象(此例還是返回作為輸入參數的方法),返回一個新函數時，新函數可以是一個全局方法或者decorator函數的內嵌函數，只要函數的簽名和被裝飾的函數相同

@deco
def MyFunc(args):? ? ? ? ? ? ? ?? #應用@deco修飾的方法
??? print('my first decorator',args)

????return('nihao',args)

MyFunc('wangkai')?? ? ? ? ? ? ? ? #調用被裝飾的函數
MyFunc('kevin')?

info = MyFunc('gonghui')
print(info)

??????? 注意：當使用上述方法定義一個decorator方法時，函數體內的額外操作只在被裝飾的函數首次調用時執行;

?????? 如果要保證額外操作在每次調用被裝飾的函數時都執行，需要換成如下的寫法：
def deco(func):
??? def replaceFunc(args):???? #定義一個內嵌函數，此函數包裝了被裝飾的函數，并提供額外操作的代碼
??????? print('第一個裝飾器')???? #進行額外操作
??????? return func(args)????????? #產生對被裝飾函數的調用
??? return replaceFunc?????????? #由于返回的是這個新的內嵌函數，所以確保額外操作每次調用得以運行

@deco
def MyFunc(args):???????????????? #應用@deco修飾的方法
??? print('my first decorator',args)
??? return('nihao',args)

MyFunc('wangkai') #調用被裝飾的函數
MyFunc('kevin')
info = MyFunc('gonghui')
print(info)

★有參裝飾:

def decoWithArgs(arg):
??? """由于有參數的decorator函數在調用時只會使用應用時的參數而不接收被裝飾的函數做為參數，
?????? 所以必須返回一個decorator函數，由它對被裝飾的函數進行封裝處理"""
??? def newDeco(func):????????????????????????? #定義一個新的decorator函數
??????? def replaceFunc(args):???????????????? #在decorator函數里面再定義一個內嵌函數，由它封裝具體的操作
??????????? print('第一個裝飾器')???????????????? #進行額外操作
??????????? aa = func(args)??????????????????????? #對被裝飾函數進行調用

????????????print('再見')?

????????????return aa
??????? return replaceFunc
??? return newDeco??????????????????????????????? #返回一個新的decorator函數

@decoWithArgs("demo")
def MyFunc(args):???????????????????????????????? #應用@decoWithArgs修飾的方法
??? print('my first decorator',args)? ?
??? return('nihao',args)

MyFunc('wangkai')??????????????????????????????? #調用被裝飾的函數
MyFunc('kevin')
info = MyFunc('gonghui')
print(info)

?????? 當我們對某個方法應用了裝飾方法后，其實就改變了被裝飾函數名稱所引用的函數代碼塊入口點，使其重新指向了由裝飾方法所返回的函數入口點。由此我們可以用decorator改變某個原有函數的功能，添加各種操作，或者完全改變原有實現。

★多參數函數的裝飾器：

def Before(request,kargs):
    print 'before:%s==%s' % (request,kargs)
    return(kargs)

def After(request,kargs):
    print 'after:%s==%s' % (request,kargs)
    return(kargs)


def Filter(before_func,after_func):
    def outer(main_func):
        def wrapper(request,kargs):
            before_result = before_func(request,kargs)
            main_result = main_func(request,kargs)
            after_result = after_func(request,kargs)
        return wrapper
    return outer

@Filter(Before, After)
def Index(request,kargs):
    print 'index:%s==%s' % (request,kargs)
    return(kargs)


Index('nihao','aaa')