寫在開頭：

這個學期上了一門叫做Python入門的選修課，差不多算是系統的學習了一下Python這門編程語言，基本的入門應該可以是算的，下一步的學習當然也不能落下。去圖書館閑逛，看到了這本《python算法教程》（挪威 Magnus Lie Hetland 著 凌杰 陸禹淳 顧俊 譯），下一步先溫習一下以前的算法也是不錯的。本人小透明一枚，寫這些，權當是一種學習筆記，如果你無意中看到，并覺得對你的學習有所幫助，對我來說也是一種榮幸。

----------------------------------------------------------正文分割------------------------------------------------------------

前三章的內容，沒有什么特別難的，差不多都是一些基本概念的東西，這本書的第四章是叫做“歸納、遞歸與歸簡”，這是我們接觸的比較早的算法思想之一，先解釋一些這三種概念：

歸簡法是指將某一問題轉化成另一個問題，通常來講，我們傾向于把一個較難的未知問題轉化成一個較簡單的已知問題來進行解決。（把問題簡單化）

歸納法是用于證明某個語句讀某種大型對象類是否成立，我們要先證明在某一基本情況下成立，然后證明它可以通過一個對象傳達到“下一個”對象。（高中時接觸到的數學歸納法和高等數學中的歸納法和這種是差不多的）

遞歸法主要用于函數的自我調用。舉個例子，“世界上沒有比恐怖本身更恐怖的事情”，或者“大魚吃小魚，小魚吃蝦米”。

那下面就歸納法、歸簡法、遞歸法舉幾個算法的實例理解一下；

首先講一個歸簡法的例子。

-我們要從某個數字列表中找到兩個彼此最接近但不相同的數字（兩個數字絕對值差最小）。

最簡單的想法，我們可以用雙重循環，逐個數字進行減運算，然后取絕對值，每次與當前最小的進行比較，最后肯定可以找到我們想要的兩個數字，代碼如下：

def get_abs_normol(seq):???????????? ????????#我們假設數組已經定義好d = float("inf") ????????????????????????#正無窮for i in range(seq):?????????????????????#雙重循環for j in range(seq):if i == j:continued = abs(i-j)if d < dd:xx, yy, dd = i, j, dprint(xx)????????????????????????????????#輸出結果print(yy)print(dd)

我們可以分析一下這個問題，我們要找的絕對值相差最小的兩個數，在一維的數軸上一定是相鄰的兩個數，那我們只需對相鄰的兩個數進行減操作即可。

我們得到另一種解法：先對所需數組進行排序，然后順序進行減操作，代碼如下：

def get_abs_better(seq):dd = float("float")sel_sort(seq)for i in range(len(seq)-1):x, y = seq[i],seq[i+1]if x == y:continued = abs(x-y)if(d < dd):xx, yy, dd = x, y, d;print(xx)print(yy)print(dd)

這樣，我們再去看這個題的解法，就從雙重循環優化成單循環，新的算法更快了，這個簡單的例子就是歸簡法的一種應用，類似的還有許多例子，比如拓撲排序（之后如果寫圖論筆記應該會寫）。

遞歸法應用比較廣，記得上數據結構課程的時候，老師講過，有時候遞歸的算法，會要求用非遞歸的方法進行重寫，利用棧和循環，即可實現。還是舉兩個比較簡單的例子——排序；

我們來看選擇排序：

def sel_sort(seq): ????????????????????????????????????????#選擇排序for i in range(len(seq)-1,0,-1): max_j = i ????????????????????????????????????????#記錄"目前最大"的索引for j in range(i): ????????????????????????????????#尋找下一個更大的數if seq[j] > seq[max_j]: ???????????????????????#如果找到，就更新max_j = jseq[i], seq[max_j] = seq[max_j], seq[i] ???????????#把這個數放到它的位置上

選擇排序是一個非常經典，并且基礎的排序，那么它的遞歸算法怎么寫呢：

def sel_sort_res(seq, i): if(i == 0):returnmax_j = i;for j in range(len(seq)-1,0,-1):max_j = ifor j in range(i):if seq[j] > seq[max_j]:max_j = jseq[i], seq[max_j] = seq[max_j], seq[i]sel_sort_res(seq,i-1)????????????????????????????#把剩下的進行排序

遞歸算法有很多中理解方式，我的理解（拿排序來講），先排完當前的，再去調用本身，排列剩余的，也就是自己調用自己。

歸納法之前理解的是這樣的：

1+3+5+……+（2n-3）+(2n-1) = (n-1)^2 + (2n-1) = (n^2 - 2n+1) +(2n-1) = n^2

先假設對n-1成立，然后加上n試一下，若成立，則整個式子就成立。

歸納法我見得不是特別多，書上例舉了一個棋盤問題，有興趣的同學可以看下書。

歸納法和遞歸法還有許多其他的應用。這篇先到這里。

總結

以上是生活随笔為你收集整理的《python算法教程》个人学习心得之（一）：归纳、递归与归简的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。