資源描述：
《算法基礎(chǔ)二Python遞歸算法解析ppt課件.pptx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、遞歸算法八大常用算法：枚舉遞歸二分算法分治算法動態(tài)規(guī)劃深度優(yōu)先搜索廣度優(yōu)先搜索貪心算法人理解迭代，神理解遞歸遞歸：指在函數(shù)的定義中使用函數(shù)自身的方法。”遞歸“表達了兩個意思：”遞“＋”歸“，基本思想是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實現(xiàn)時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會產(chǎn)生無限遞歸的情況了遞歸應(yīng)用三步法：1).明確遞歸終止條件例如：當N=0時，遞歸終止2).給出遞歸終止時的處理辦法例如：ifn=0:return1
2、3).提取重復的邏輯，遞歸的一般式，縮小問題規(guī)模例如：returnn*f（n-1）例1：應(yīng)用三步法解決實際問題：階乘問題1).明確遞歸終止條件當N=0時，遞歸終止2).給出遞歸終止時的處理辦法ifn=0:return13).提取重復的邏輯，縮小問題規(guī)模重復的邏輯是：returnn*f（n-1）defjiecheng(n):ifn==0:return1else:returnn*jiecheng(n-1)zzshu=int(input('輸入待求的階乘的正整數(shù)'))print(zzshu,'的階乘是',jiecheng(zzshu))例2：應(yīng)用三步法
3、解決實際問題：斐波那契數(shù)列1).明確遞歸終止條件當N=1,或n=2時，遞歸終止2).給出遞歸終止時的處理辦法ifn==1orn==2:return13).提取重復的邏輯，縮小問題規(guī)模*重復的邏輯是：f（n）=f(n-1)+f（n-2）deffbnqsl(n):ifn==1orn==2:return1else:returnfbnqsl(n-1)+fbnqsl(n-2)zzshu=int(input('輸入待求的斐波那切數(shù)列的個數(shù)為'))print(zzshu,'個斐波那切數(shù)列的是')foriinrange(1,zzshu+1):print(fbnq
4、sl(i))例3：應(yīng)用三步法解決實際問題：稍微復雜一點的例題：漢諾塔問題法國數(shù)學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。畫圖是分析問題的一
5、個好習慣1、先假設(shè)除最下面的盤子之外，我們已經(jīng)成功地將上面的63個盤子移到了b柱，此時只要將最下面的盤子由a移動到c即可。如圖：分解問題2、當最大的盤子由a移到c后，b上是余下的63個盤子，a為空。因此現(xiàn)在的目標就變成了將這63個盤子由b移到c。這個問題和原來的問題完全一樣，只是由a柱換為了b柱，規(guī)模由64變?yōu)榱?3。因此可以采用相同的方法，先將上面的62個盤子由b移到a，再將最下面的盤子移到c……3、要以B為輔助將A上64個盤子轉(zhuǎn)移到C上將c柱子作為輔助，把a上的63個圓盤移動到b上將a上最后一個圓盤移動到c這樣問題轉(zhuǎn)移成，接下來要以a為輔助，
6、將B上所有63盤子轉(zhuǎn)移到C上。defmove(n,a,b,c):#將A柱上N個盤子以B柱為輔助移動到C柱上ifn?==1:print(a,'--->',?c)#如果只有1個盤子，直接將A柱上的盤子移動到c柱上else:move(n-1,?a,?c,?b)#將N-1個盤子從A柱上以c柱為輔助移動到b柱上,這時a柱上只有當前最大一個盤子move(1,?a,?b,?c)#將a柱上剩下的這個最大的盤子從A柱上以b柱為輔助（實際用不上B柱）移動到c柱上,這時a柱為空move(n-1,?b,?a,?c)#將B柱上剩下的N-1個盤子以A柱為輔助，移動到C柱上m
7、ove(4,'A','B','C')遞歸習題1：八皇后問題：八重循環(huán)？體會遞歸之美！十九世紀著名的數(shù)學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。遞歸習題2：波蘭表達式波蘭表達式是一種把運算符前置的算術(shù)表達式，例如普通的表達式2+3的逆波蘭表示法為+23。逆波蘭表達式的優(yōu)點是運算符之間不必有優(yōu)先級關(guān)系，也不必用括號改變運算次序，例如(2+3)*4的逆波蘭表示法為*+234。本題求解逆波蘭表達式的值，其中運算符包括+-*/四個。輸入輸入為一行，其中運
8、算符和運算數(shù)之間都用空格分隔，運算數(shù)是浮點數(shù)輸出輸出為一行，表達式的值。遞歸習題3：表達式計算輸入為四則運算表達式，僅由整數(shù)、+、－、*
