大一下-數(shù)算sessdsa-04recursion數(shù)據(jù)結(jié)構(gòu)與算法Python04遞歸

據(jù) 〉本章目據(jù)結(jié)與 〉什么是遞與算（ 〉實現(xiàn)遞（〉）〉〉動態(tài)規(guī)劃Dynamic地球與空間科學(xué)學(xué)院/陳斌本章目據(jù) 據(jù)結(jié)與 與算（ （〉）〉〉地球與空間科學(xué)學(xué)院/陳斌什么是遞歸構(gòu)數(shù) 〉 遞歸是一種解決問題的方，其精髓是將問題分解為規(guī)模更小的據(jù) ，持續(xù)分直到問題規(guī)小到可以用非常簡單直接方式結(jié) 。構(gòu)與 遞歸的問題分解方式非常獨特，其算法方面的明顯特征就是：在（ 法流程中調(diào)用自身（ 遞歸為我們提供了一種對復(fù)雜問題的優(yōu)雅解決方案，精妙的遞歸 法常會出奇簡單，令人贊地球與空間科學(xué)學(xué)院/陳斌初識遞歸 我們先從一個不太復(fù)雜的問題開據(jù)構(gòu) 問題：給定一個列表，返回列表中所有數(shù)的構(gòu) 算（ 程序很簡單，但假如沒有循環(huán)語句（ 還能對不確定長度〉 我們認識到求和實際上最終是由一次次的加法實現(xiàn)的，而加法函恰有兩個參數(shù)，這個是確定的。 看看怎么想辦法，將問題規(guī)模較大的列表求和，分解為規(guī)模較小且固定的兩個數(shù)求和（加法地球與空間科學(xué)學(xué)院/陳斌初識遞歸 我們換一個方式來表達數(shù)列求和：全括號表達 結(jié)與 當然，由于加法可交換，寫成下面的方式可能更方便些與法 法（〉 上面這個式子，最內(nèi)層的括號(7+9，這是無需循即可計算的，實際上整個求和的過程是這樣：） 觀察上述過程中所包含的重復(fù)模式，可以把求和問題歸納成這樣問

相同問題，規(guī)地球與空間科學(xué)學(xué)院/陳斌初識遞歸 上面的遞歸算法變成程與 與算 （

） 上面程序的要點地球與空間科學(xué)學(xué)院/陳斌遞歸程序如何被執(zhí)行 遞歸函數(shù)調(diào)用和返回過程的鏈據(jù)地球與空間科學(xué)學(xué)院/陳斌遞歸“三定律 為了向阿西莫夫的“機器人三定律”致敬，遞歸算法也總結(jié)出“ 定律 構(gòu) 法 法（ 數(shù)列求和的遞歸算法首先具備了基本結(jié)束條件：當列表長度為1的候，直接輸出所包含的唯一數(shù)，使遞歸算法具備了最終 是什么〉數(shù)列求和處理的數(shù)據(jù)對象是一個列表，而基本結(jié)束條件是長度為1的〉 調(diào)用自身是遞歸算法中最難理解的部分實際上我們理解為“分解成了規(guī)模更小的相同問題”就可以了，在數(shù)列求和算法中，就是“數(shù)列的求和問。地球與空間科學(xué)學(xué)院/陳斌隨堂作業(yè)4- 用listsum計算數(shù)列求和[2,4,6,8,10]要進行多少次遞歸調(diào)用 A)6B)5C)4算 寫出計算階乘的遞歸程算 （def chbpku和課 具有提地球與空間科學(xué)學(xué)院/陳斌整數(shù)轉(zhuǎn)換為任 這個在數(shù)據(jù)結(jié)構(gòu)棧里討論過的算法，又回來了結(jié) 結(jié)構(gòu) 如果上次你被“入?！薄俺鰲！备愕猛灪醯脑?，這次遞歸算法法 定會讓你感到清法 我們用最熟悉的十進制分析下這個問十進制有十個不同符號：convString= 地球與空間科學(xué)學(xué)院/陳斌整數(shù)轉(zhuǎn)換為任 我們用整數(shù)除，和求余數(shù)兩個計算來將整數(shù)一步步拆結(jié) 結(jié)構(gòu) 問題就分解為算 （整數(shù)商成為“更小規(guī)?！眴栴}，通過遞歸調(diào)用自身）地球與空間科學(xué)學(xué)院/整數(shù)轉(zhuǎn)換為任意進制：代 下面就是遞歸算法的代構(gòu)算算）地球與空間科學(xué)學(xué)院/陳斌遞歸調(diào)用的實 當一個函數(shù)被調(diào)用的時候，系統(tǒng)會把調(diào)用時的現(xiàn)場（包括所有的 部變量，以及返回地址）壓入到調(diào)用棧Call結(jié) 每次調(diào)用，壓入棧的現(xiàn)場數(shù)據(jù)稱為StackFrame棧與法 當函數(shù)執(zhí)行完成，返回時，要從調(diào)用棧的棧頂取得返回地址，把法 回值放到棧頂，恢復(fù)現(xiàn)場，彈出棧幀，按地址返回 返回 返回 地球與空間科學(xué)學(xué)院/陳斌遞歸的故 一個古老 ：有始無終的無盡遞結(jié) 結(jié) 與 法 前目的地）: : 游輪 地球與空間科學(xué)學(xué)院/陳斌隨堂作業(yè)4- 編寫將字符串反轉(zhuǎn)的遞歸函 def算 編寫回文詞判斷的遞歸函算 def（ chbpku和課 具有提）地球與空間科學(xué)學(xué)院/陳斌遞歸可視化：圖 前面的種種遞歸算法展現(xiàn)了其簡單而強大的一面，但還是難有個 觀的概念，下面我們通過遞歸作圖來展現(xiàn)遞歸調(diào)用的視覺影結(jié) Python的海龜作圖系統(tǒng)turtle算 算 （爬行：forward(n轉(zhuǎn)向：left(a 筆觸：penup(pendown(pensize( 使用方importturtletturtle.Turtlew=turtle.Screen()#獲取屏幕對象，用于最后的點擊自動關(guān)閉窗口 地球與空間科學(xué)學(xué)院/陳斌海龜作 畫正方據(jù)構(gòu) 畫五邊構(gòu)與 畫六邊法 畫五角）地球與空間科學(xué)學(xué)院/陳斌一個遞歸作圖的例子：螺（最小規(guī)模，0直接退 減小規(guī)模，邊長減陳斌陳分形樹：自相似遞歸圖 分形Fractal，是1975年由Mandelbrot開創(chuàng)的新學(xué)據(jù)與法結(jié) 〉 通常被定義為“一個粗糙或零碎的幾何形可以分成個部分構(gòu) 且每一部分都（至少近似地）是整體縮小后的形狀”，即具有自相算 。與法（ 自然界中能找到眾多具有分形性質(zhì)的物） 地球與空間科學(xué)學(xué)院/陳斌yy0分形樹：自相似遞歸圖0 自然現(xiàn)象中所具備的分形特性，使得計算機可以通過分形算法生 非 真的自然場景，下面我們以樹為例做一個粗糙的近結(jié)與（構(gòu) 〉 分形是在不同尺度上都具有相似性的事將這種觀點在對算 觀察上，我們就能看，一棵樹的每個分叉和每條樹枝，實際上都法 征的）與（ 這樣，我們可以把樹分解為三個部分：樹干、左邊伸出的小樹、 邊伸出的小大大空分形樹：代算

（法最小規(guī)模，0（右傾20）減小規(guī)模，樹干減回右傾20度，即回

地球與空間科學(xué)學(xué)院/陳斌分形樹：運 注意海龜作圖的次結(jié) 結(jié)畫樹，樹干長度 分形構(gòu)造，平面稱謝爾賓斯基三角形，立體稱謝爾賓斯基金字 結(jié) 與 （ （）謝爾賓斯基三角形：作圖 首先，根據(jù)自相似特性，謝爾賓斯基三角形是由3個相同的謝爾賓 基三角形按照品字形拼疊而成 由于我們無法真正做出謝爾賓斯基三角形（degree->∞），只能法 degree有限的近似圖形法（ 在degree有限的情況下，degree=n的三角形，是由3個degree=n-的三角形按照品字形拼疊而成，同時，這3個degree=n-1的三 邊長均為degree=n的三角形的一半（規(guī)模減?。?地球與空間科學(xué)學(xué)院/陳斌

謝爾賓斯基三角形：代等邊三角形（左上右頂點次序算與最小規(guī)模，0算法 ）地球與空間科學(xué)學(xué)院/陳斌謝爾賓斯基三角形：代據(jù) 畫指定頂點的等邊三角據(jù) 指定填充顏 算 2，落筆開始填算 3，到上頂 5，回到左頂點閉 畫degree=3的三角地球與空間科學(xué)學(xué)畫degree=3的三角謝爾賓斯基三角形：遞歸調(diào)用過（）3210地球與空間科學(xué)學(xué)院/陳斌復(fù)雜遞歸問題：河內(nèi)塔Towerof 河內(nèi)塔問題是由法國數(shù)學(xué)家EdouardLucas于1883年，根據(jù)一個 與 在一 教寺廟里，有3根柱子，其中一根套著64個由小到與 的黃金盤片，僧侶們的任務(wù)就是要把這一疊黃金盤從一根柱子搬（ 另一根，但有兩個規(guī)則（ 神的旨意是說，一旦這64個盤子完成遷移 神的旨意是千真萬確的地球與空間科學(xué)學(xué)院/陳斌河內(nèi)塔（漢諾塔）問題：3盤片演構(gòu)（）構(gòu)（）地球與空間科學(xué)學(xué)院/陳斌河內(nèi)塔（漢諾塔）問題：4盤片演地球與空間科學(xué)學(xué)院/陳斌 雖然這些黃金盤片跟世 有著神秘的聯(lián)系，但我們卻不必太 心，據(jù)計算，要搬完這64個盤片結(jié) 與 法 問題如何分解為遞歸形式）地球與空間科學(xué)學(xué)院/陳斌河內(nèi)塔問題：分 我們還是從遞歸三定律來分析河內(nèi)塔問 結(jié) 假設(shè)我們有5個盤子，穿在1#柱，需要挪到3#算 算（ 把剩下的最大號盤子直接從1#柱挪到3#柱，再用同樣的辦法把2#柱上的（ 接下來的問題就是4個盤子怎么從1#挪到 一摞3個盤子的挪動也照此：分為上面一摞2個，和下面最大號盤 那么2個盤子怎么移動呢？（ （實在想不出，那么）最后是1個盤子的移動地球與空間科學(xué)學(xué)院/陳斌河內(nèi)塔問題：遞歸思 將盤片塔從開始柱，經(jīng)由中間柱，移動到目標柱結(jié) 結(jié) 與 法（ 基本結(jié)束條件，也就是最小規(guī)模問題是：1個盤片的移動問 上面的思路用Python寫出來，幾乎跟語言描述一樣地球與空間科學(xué)學(xué)院/陳斌 河內(nèi)塔問題：代 數(shù) 構(gòu) 減小規(guī)模法 法（） 古希臘克里特島米諾斯據(jù)構(gòu) 牛頭人身怪物米諾陶洛構(gòu) 算（ 公主，利劍，線（ 老國王投） 愛琴探索迷宮：圓明園的黃花 位于圓明園西洋樓景 海龜放在迷宮中間，看它如何能找到出（）地球與空間科學(xué)學(xué)院/陳斌迷宮的數(shù)據(jù)結(jié) 首先 整個迷宮的空間（矩形）分為行列整齊的方格，區(qū) 出墻壁和通道結(jié) 與法 考慮用矩陣方式來實現(xiàn)迷宮數(shù)據(jù)結(jié)法 采用不同字符來分別代表“墻壁”“通道”“海龜投放點 ?+：墻空格：通S：海地球與空間科學(xué)學(xué)院/陳斌迷宮的數(shù)據(jù)結(jié)構(gòu)：Maze MazeClass的成結(jié) 結(jié) 與 法（ 讀入數(shù)據(jù)文件成功）北探索迷宮 確定了迷宮的數(shù)據(jù)結(jié)構(gòu)之后，我們知道，對于海龜來說，其身處 個方格之構(gòu) 構(gòu)算 算法 這樣，探索迷宮并找到出口的遞歸算法思路如下）如果向南還找不到出口，那么將海龜從原位置向西如果向西還找不到出口，那么將海龜從原位置向東地球與空間科學(xué)學(xué)院/陳斌探索迷宮 上面這個思路看起來很完美，但有些細節(jié)是至關(guān)重要 結(jié) 與 （ （ 所以需要有個機制來記錄海龜所走過的路 地球與空間科學(xué)學(xué)院/陳斌探索迷宮 這樣，我們對遞歸調(diào)用的“基本結(jié)束條件”歸納如下 結(jié) 算 ） 為了讓海龜在迷宮圖里跑起來，我們給迷宮數(shù)據(jù)結(jié)構(gòu)MazeClass加一些成員和方updatePosition(rowcolval)：更新海龜?shù)奈恢?，并做標注isExit(row,col)：判斷是否“出口”地球與空間科學(xué)學(xué)院/陳斌探索迷宮

地球與空間科學(xué)學(xué)院/陳斌動態(tài)規(guī)劃Dynamic 計算機科學(xué)中許多程序都是為了找到某些問題的最優(yōu) 結(jié) 算 算法（ 〉 人們會采用各種策略來解決這些問題，我們這里介紹其中的一種略動態(tài)規(guī)劃 優(yōu)化問題的一個經(jīng)典的案例是為找零兌換最少個數(shù)的硬假設(shè)某次顧客投進 地球與空間科學(xué)學(xué)院/陳斌動態(tài)規(guī)劃 這種方法稱為“貪心法Greedy結(jié) 因為我們每次都試圖解決問題的盡量大的一部結(jié)與 對應(yīng)到兌換硬幣問題，就是每次以最多數(shù)量的最大面值硬幣來迅速減少找與算 “貪心法” 硬幣體系（quarter/dime/nikel/penny）下 現(xiàn)尚 但如果你 決定把自動售貨機出口到Elbonia（系列漫 Dilbert里杜撰的國家），事情就會有點復(fù)雜，因為這個古怪的國家除了上面3種面值之外，還有一種【?21】的硬 按照“貪心法”，在Elbonia，?63還是原來的6個硬 但實際上最優(yōu)解是3個面值?21的硬幣 “貪心法”失效了地球與空間科學(xué)學(xué)院/陳斌兌換硬幣 我們來找一種肯定能找到最優(yōu)解的方法，既然本章是介紹遞歸， 這個解法肯定是遞歸結(jié)與 首先是確定基本結(jié)束條件，兌換硬幣這個問題最簡單直接的情況與法 是，需要兌換的找零，其面值正好等于某種硬法 其次是減小問題的規(guī)模， 硬幣體系里，我們要嘗試4 兌換硬幣：遞歸解法代 法地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：遞歸解法分 遞歸解法雖然能解決問題，但其最大的問題是：極！其！低！效結(jié) 結(jié) 以26分兌換硬幣為例，看看遞歸調(diào)用過程（377次遞歸的一小部分（ 地球與 兌換硬幣：遞歸解法改 對這個遞歸解法進行改進的關(guān)鍵就在于消除重復(fù)計 結(jié) 與法 這個算法的中間結(jié)果就是部分找零的最優(yōu)解，在遞歸調(diào)用過程中法 經(jīng)得到的最優(yōu)解被記錄在遞歸調(diào)用之前，先查找表中是否已有部分找零 改進后的解法，極大減少了遞歸調(diào)用的次地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：遞歸解法改進（

）地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃解構(gòu)算數(shù) 〉 雖然上述的改進可以很好地解決兌換硬幣的問，但記錄中間結(jié)果據(jù) 的表不少未定義的“洞”實際上這種方法還不能稱為動態(tài)結(jié) 規(guī)劃，而是利用了一種叫做“mmoizaion（函數(shù)值緩存）”的技與 能或者一般稱“ahg（”構(gòu)算法 動態(tài)規(guī)劃算法采用了一種更有條理的方式來得到問題的 兌換硬幣的動態(tài)規(guī)劃算法從最簡單的“1分錢找零”的最優(yōu)解開始 逐步遞加上去，直到我們需要的找零錢 在找零遞加的過程中，設(shè)法保持每一分錢的遞加都是最優(yōu)解，一加到求解找零錢數(shù)，自然得到最 遞加的過程能保持最優(yōu)解的關(guān)鍵是，其依賴于更少錢數(shù)最優(yōu)解的單計算，而更少錢數(shù)的最優(yōu)解已經(jīng)得到地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃算 我們來看看如何采用動態(tài)規(guī)劃來解決11分錢的兌換問1 從分錢兌換開1結(jié)與 與 法 地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃解 計算11分錢的兌換法，我們做如下幾步結(jié) 結(jié) 與 法（ 這樣，第1、3步我們都可以得到11分錢的最優(yōu)解：2個硬 1 2 3 4 5 6 7 8 9 10地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃算法結(jié)從1算（）地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃算法構(gòu)數(shù) 〉 我們注意到動態(tài)規(guī)劃算法的daeage并不是遞歸函，雖然這據(jù) 始解決個更結(jié) 構(gòu) 算 （ 前面的算法已經(jīng)得到了最少硬幣的數(shù)量，但沒有返回硬幣如何組 地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃算法擴展代（）地球與空間科學(xué)學(xué)院/陳斌兌換硬幣：動態(tài)規(guī)劃算法擴展代（）北討論：博物館大盜問 大盜潛入博物館，面前有5件寶物，分別有重量和價值，大盜的背 僅能負重20公斤，請問如何選擇