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

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

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

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

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

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

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

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

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