計算思維導(dǎo)論第3章課件

第三章11974年圖靈獎獲得者DonaldErvinKnuth:計算機(jī)科學(xué)就是算法的研究TheArtofComputerProgramming3.1算法的概念計算機(jī)輸入輸出算法問題算法與計算機(jī)之間的關(guān)系2一、算法的起源3.1算法的概念公元前300年：古希臘著名數(shù)學(xué)家歐幾里得提出求最大公約數(shù)的一種算法,即輾轉(zhuǎn)相除法又稱歐幾里得算法。公元263年：三國魏人劉徽注釋《九章算術(shù)》中不僅對原書的方法、公式和定理進(jìn)行一般的解釋和推導(dǎo)，而且在其論述中多有創(chuàng)造。如他運用割圓術(shù)得出圓周率的近似值3927/1250＝3.1416。公元825年：波斯數(shù)學(xué)家al-Khwarizmi撰寫了著名的PersianTextbook中概括了進(jìn)行四則算術(shù)運算的法則。Algorithm(算法)一詞就來源于這位數(shù)學(xué)家的名字。3二、算法的定義[算法3.1]歐幾里得算法。輸入：正整數(shù)m、n輸出：m、n的最大公約數(shù)①r＝mmodn②若r＝0，輸出最大公約數(shù)n③若r≠0，令m＝n，n＝r，轉(zhuǎn)①繼續(xù)

3.1算法的概念算法：是解決某一特定問題的一組有窮規(guī)則的集合。算法：對特定問題求解步驟的一種描述，是由若干條指令組成的有窮集合。4三、算法的特征確定性：算法中每一個步驟都是清晰的、無歧義有窮性：算法必須在有限步內(nèi)終止輸入：有零個或多個輸入，作為初始狀態(tài)輸出：有一個或多個輸出，作為計算結(jié)果可行性：算法中的操作可通過有限次基本運算來實現(xiàn)3.1算法的概念判斷一個算法的好壞主要依據(jù)如下標(biāo)準(zhǔn)：正確性：在合理輸入下能在有限時間內(nèi)得出正確結(jié)果可讀性：算法主要是為了人的閱讀與交流，其次執(zhí)行健壯性：算法應(yīng)具備檢查錯誤和對錯誤進(jìn)行處理能力效率：算法執(zhí)行時所需計算機(jī)資源的多少5算法的描述目的記錄算法思想方便他人理解算法3.2算法的描述算法的描述方法自然語言流程圖偽代碼程序設(shè)計語言6一、自然語言3.2算法的描述自然語言是人們?nèi)粘＿M(jìn)行交流的語言，如漢語、英語等優(yōu)點：通俗易懂，即使沒有學(xué)過算法也能看懂算法執(zhí)行缺點：不夠嚴(yán)謹(jǐn)，容易出現(xiàn)歧義和錯誤[例題]利用自然語言描述歐幾里得算法。①輸入m、n②判斷n是否為0，如果不為0，轉(zhuǎn)步驟③，否則轉(zhuǎn)④③m對n取余，其結(jié)果賦值給r，n賦給m，r賦給n，轉(zhuǎn)②④輸出m，算法結(jié)束7二、流程圖常用來描述算法的圖形工具有：流程圖或程序框圖、N-S圖和PAD圖。

優(yōu)點：直觀形象，簡潔明了。

缺點：畫起來費事，不易修改。3.2算法的描述常用的流程圖符號：8[例題]利用流程圖描述歐幾里得算法。3.2算法的描述9三、偽代碼3.2算法的描述偽代碼是由帶標(biāo)號的指令構(gòu)成，但是它不是C、C++、Java等通常使用的程序設(shè)計語言，而是算法步驟的描述。偽代碼介于自然語言和程序設(shè)計語言之間。偽代碼的具體表示：賦值語言：←分支語句：if…then…[else]循環(huán)語句：while,for,repeatuntil轉(zhuǎn)向語句：goto輸出語句：return調(diào)用：注釋：//…10[例題]利用偽代碼描述歐幾里得算法。3.2算法的描述輸入：正整數(shù)m、n輸出：m、n的最大公約數(shù)1repeat2r←mmodn3m←n4n←r5untilr=06returnm

11四、程序設(shè)計語言程序設(shè)計語言是一個能完整、準(zhǔn)確和規(guī)則地表達(dá)人們的意圖，并用以指揮或控制計算機(jī)工作的符號系統(tǒng)，如C、C++、Java等程序設(shè)計語言可以描述算法。3.2算法的描述優(yōu)點：描述的算法能在計算機(jī)上直接執(zhí)行缺點：抽象性差、不易理解且有嚴(yán)格的語法限制等。12輸入：正整數(shù)m、n輸出：m、n的最大公約數(shù)int

gcd(intm,intn){int

r;do{r=m%n;m=n;n=r;}

while(r);returnm;}3.2算法的描述[例題]利用C語言描述歐幾里得算法。13算法是解決問題的方案，由于實際問題千奇百怪，因而制定出的解決方案也將千差萬別。3.3算法的設(shè)計

算法設(shè)計的一般步驟：①理解待求解問題解決問題是設(shè)計算法的最終目標(biāo)。除了需要分析問題的求解目標(biāo)、輸入數(shù)據(jù)和限制條件外，還要判斷清楚待求解問題的種類，是否有現(xiàn)成的算法可以直接應(yīng)用。②確定算法運行的環(huán)境了解算法的運行環(huán)境，才能設(shè)計出可行且高效的算法。比如在小型的嵌入式環(huán)境中只能運行需要較小內(nèi)存的算法，而對于并行分布式的運行環(huán)境，則要設(shè)計高效的并行算法。14③設(shè)計算法設(shè)計算法是將算法具體化，即設(shè)計出算法的詳細(xì)規(guī)格說明。也就是，首先確定算法所需要的數(shù)據(jù)結(jié)構(gòu)，然后結(jié)合具體問題的特性來選擇算法的設(shè)計策略，最后根據(jù)算法設(shè)計技術(shù)的原理描述算法的具體流程(流程圖、偽代碼和程序設(shè)計語言等)。④分析算法對所設(shè)計出的算法進(jìn)行復(fù)雜性分析，考察其在時間和空間方面的計算開銷。若算法在某些環(huán)節(jié)的計算開銷較大，可有針對性地改進(jìn)該環(huán)節(jié)，若整個算法的計算開銷太大，則需要返回第③步重新考慮采用新的算法設(shè)計技術(shù)來求解該問題。⑤編程實現(xiàn)采用某種程序設(shè)計語言將設(shè)計好的算法實現(xiàn)出來。3.3算法的設(shè)計15

算法分類：

①數(shù)值算法

求解線性方程組、數(shù)值積分等，有特定的計算步驟

數(shù)值計算方法課程

②非數(shù)值算法

求解判定問題、最優(yōu)化問題等，需要掌握算法設(shè)計技術(shù)

算法設(shè)計與分析課程

③軟計算方法

遺傳算法、粒子群算法、蟻群算法、人工神經(jīng)網(wǎng)絡(luò)等

計算智能課程3.3算法的設(shè)計16一、窮舉法(又稱蠻力算法)

窮舉法指在問題的解空間范圍內(nèi)逐一測試，找出問題的解。它是一種簡單而有效的算法設(shè)計策略同時也是一種很容易應(yīng)用的方法。

3.3算法的設(shè)計窮舉法的應(yīng)用

國王的婚姻中國王使用的算法

旅行商問題中逐條路線計算

密碼學(xué)中的暴力破解法

圖論中四色定理的證明

百錢買百雞問題

17[案例一]暴力破解法是一種用窮舉法實現(xiàn)的密碼破譯方法。3.3算法的設(shè)計最原始、最基本的攻擊方式，對密碼進(jìn)行逐一測試直到找到真正的密碼。原則上可以破譯所有密碼，但費時費力。密碼暴力破解軟件：89Winrar

QQ密碼暴力破解軟件18[案例二]四色定理(又稱四色問題或四色猜想)。3.3算法的設(shè)計四色問題描述：任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。數(shù)學(xué)語言表示：將平面任意地細(xì)分為不相重疊的區(qū)域，每一個區(qū)域總可以用1、2、3、4這四個數(shù)字之一來標(biāo)記，而不會使相鄰的有公共邊界的兩個區(qū)域得到相同的數(shù)字。證明四色定理(窮舉法)：①利用數(shù)學(xué)理論推出證明所有例子可以歸約到證明有限個特例上；②利用計算機(jī)程序產(chǎn)生了所有特例(大約1700個例子)，通過窮舉發(fā)現(xiàn)所有特例都是四著色的。19[案例三]百錢買百雞問題

百錢買百雞：雞翁一，值錢五雞母一，值錢三雞雛三，值錢一問翁、母、雛各幾何？3.3算法的設(shè)計意思是：公雞每只5元、母雞每只3元、小雞3只1元，用100元錢買100只雞，求公雞、母雞、小雞的只數(shù)。20

設(shè)雞翁、雞母、雞雛的個數(shù)分別為x、y、z，根據(jù)題意可得如下方程組：

5x＋3y＋z/3＝100x＋y＋z＝1001≤x＜20,1≤y＜33,3≤z＜100,zmod3＝0測試集合：1≤x＜20,1≤y＜33，z=3,6,9,...,99測試條件：5x＋3y＋z/3＝100

x＋y＋z＝1003.3算法的設(shè)計21巧妙和高效的算法很少來自于窮舉法，但基于以下因素，窮舉法仍是一種重要的算法設(shè)計策略：①窮舉法幾乎可以通用于任何領(lǐng)域的問題求解，可能是唯一一種解決所有問題的一般性方法；②即使效率低下，仍可用窮舉法求解一些小規(guī)模的問題實例；③如果解決的問題實例不多，而窮舉法可用一種可接受的速度對問題求解，那么花時間去設(shè)計一個更高效地算法是得不償失的。

3.3算法的設(shè)計[思考題]舉例說明生活中的窮舉法應(yīng)用。22二、回溯法

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。在搜索過程中，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試，通過此種方式提高搜索效率，減少不必要的測試。3.3算法的設(shè)計回溯法的應(yīng)用迷宮問題搜索引擎中的網(wǎng)絡(luò)爬蟲八皇后問題23[案例一]老鼠走迷宮3.3算法的設(shè)計老鼠從迷宮入口出發(fā)，任選一條路線向前走，在到達(dá)一個岔路口時，任選一個路線走下去…，如此繼續(xù)，直到前面沒有路可走時，老鼠退回到上一個岔路口，重新在沒有走過的路線中任選一條路線往前走。按這種方式走下去，直到走出迷宮。

24[案例二]搜索引擎中的網(wǎng)絡(luò)爬蟲。3.3算法的設(shè)計

搜索引擎是指根據(jù)一定的策略、運用特定的計算機(jī)程序從互聯(lián)網(wǎng)上搜集信息，在對信息進(jìn)行組織和處理后，為用戶提供檢索服務(wù)，將用戶檢索相關(guān)的信息展示給用戶的系統(tǒng)。百度和谷歌等是搜索引擎的代表。

搜索引擎的組成：下載、索引和查詢。25網(wǎng)絡(luò)爬蟲：自動下載互聯(lián)網(wǎng)所有網(wǎng)頁。網(wǎng)絡(luò)爬蟲原理：圖的遍歷，從圖中某一頂點出發(fā)訪遍圖中所有頂點，且使每個頂點僅被訪問一次?；厮菟惴ǎ簣D的深度優(yōu)先遍歷（廣度優(yōu)先遍歷）。3.3算法的設(shè)計深度優(yōu)先遍歷順序：V1,V2,V4,V8,V5,V3,V6,V726[案例三]八皇后問題。在8×8格國際象棋的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上問有多少種擺法？3.3算法的設(shè)計27

回溯法解八皇后問題思路：逐行擺放皇后。初始第1行皇后放第1列；擺放第i行皇后時，從第1列開始，逐列判定是否與前i-1行皇后攻擊，直到找到一個不攻擊的位置，繼續(xù)第i+1行的擺放；若第i行無擺放位置，則拿掉該行皇后，回溯至第i-1行，第i-1行皇后從當(dāng)前位置的下一列開始判定，繼續(xù)搜索。當(dāng)?shù)?行皇后的擺放位置超出棋盤時，全部求解過程結(jié)束。(92種)3.3算法的設(shè)計28回溯法有通用解法之稱，當(dāng)一個問題沒有顯而易見的解法時，可嘗試使用回溯法求解，這實際是與窮舉法一致的，因其本質(zhì)仍是窮舉。需要注意，回溯和窮舉雖然能解很多問題，但其算法效率可能很低。3.3算法的設(shè)計

回溯法的基本思想是能進(jìn)則進(jìn)，不能進(jìn)則退。為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或確定該問題無解?；厮莘ㄊ乔蠼鈱嶋H問題的一個重要算法，很多無法使用貪心算法和動態(tài)規(guī)劃算法進(jìn)行求解的問題，都可以使用回溯算法進(jìn)行求解，并且可以保證得到問題的最優(yōu)解。29三、遞歸算法

遞歸：直接或間接地調(diào)用自身的算法。遞歸思想就是用與自身問題相似但規(guī)模較小的問題來描述自己。3.3算法的設(shè)計遞歸算法的應(yīng)用盜夢空間(美國影片)歐幾里得算法德羅斯特效應(yīng)(DrosteEffect)斐波納契數(shù)列(Fibonacci數(shù)列)30[案例一]德羅斯特效應(yīng)。遞歸的一種視覺形式，它指一張圖片的某個部分與整張圖片相同，如此產(chǎn)生無限循環(huán)。3.3算法的設(shè)計31[案例二]1202年，意大利數(shù)學(xué)家斐波納契出版了他的算盤全書。他在書中提出了一個關(guān)于兔子繁殖問題：如果一對兔子每月能生一對小兔(一雄一雌)，而每對小兔在它們出生后的第三個月里，又能開始生一對小兔，假定在不發(fā)生死亡的情況下，由一對出生的小兔開始，50月后會有多少對兔子？分析：第一個月只有一對兔子，第二個月仍只有一對兔子，第三個月兔子對數(shù)為第二個月兔子對數(shù)加第一月兔子新生的對數(shù)。同理，第i個月兔子對數(shù)為第i-1月兔子對數(shù)加第i-2月兔子新生的對數(shù)。即從第一個月開始計算，每月兔子對數(shù)依次為：1,1,2,3,5,8,13,21,34,55,89,144,233,…。

3.3算法的設(shè)計32兔子繁殖的規(guī)律3.3算法的設(shè)計月數(shù)小兔子對數(shù)中兔子對數(shù)老兔子對數(shù)兔子總數(shù)110012010131012411135212563238753513┆┆┆┆┆33遞歸過程3.3算法的設(shè)計F5=F4+F3F4=F3+F2F3=F2+F1F2=1F1=1F3=1+1=2F4=2+1=3F5=3+2=5回溯階段遞推階段34Fibonacci數(shù)列遞歸算法的偽代碼描述：Fibonacci數(shù)列的遞歸算法輸入：正整數(shù)n輸出：Fibonacci數(shù)列的第n項Fib(n)1IFn≤22 THENRETURN13RETURNFib(n-1)+Fib(n-2)//調(diào)用自身3.3算法的設(shè)計35

遞歸算法的主要優(yōu)點：結(jié)構(gòu)清晰、可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來了很大方便。

遞歸算法的主要缺點：遞歸算法的運行效率相對較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。通常的解決方法是消除遞歸算法中的遞歸調(diào)用，使遞歸算法轉(zhuǎn)化為非遞歸算法。3.3算法的設(shè)計36四、分治法3.3算法的設(shè)計

分治算法：將一個難以直接解決的大問題，分解成一些規(guī)模較小的子問題，以便各個擊破，分而治之。如果子問題還比較大，可反復(fù)使用分治算法，直到最后的子問題可以直接得出它們的結(jié)果。由于分治算法的子問題類型常與原來的相同，因而很自然地使用遞歸算法。分治法的應(yīng)用國王的婚姻中宰相的策略Google的MapReduce技術(shù)二分查找用于組織管理和軍事等領(lǐng)域37[案例一]Google的MapReduce技術(shù)3.3算法的設(shè)計谷歌在全球有36個數(shù)據(jù)中心，服務(wù)器不計其數(shù)。它的三大核心技術(shù)是：

GFS(GoogleFileSystem)：專用文件系統(tǒng)；

BigTable：分布式數(shù)據(jù)庫系統(tǒng)；

MapReduce：并行計算編程模型。38

MapReduce模型中兩項核心操作：Map→映射；Reduce→化簡、歸約3.3算法的設(shè)計MapReduce處理大數(shù)據(jù)過程是由劃分、治理、合并三個步驟組成，是分治策略的完美應(yīng)用。

39[案例二]二分查找3.3算法的設(shè)計常用的二分查找是一個典型的分治算法。

二分查找基本原理：用于在n個元素的有序序列中查找指定元素e。將n個元素分成個數(shù)大致相同的兩半，取an/2與欲查找的e作比較，若e=an/2，則找到e，算法終止若e<an/2，則只需在數(shù)組a的前半部分繼續(xù)二分查找e若x>an/2，則只需在數(shù)組a的后半部分繼續(xù)二分查找e二分查找每次比較將數(shù)據(jù)減少一半，也稱折半查找。

40二分查找在列表中查找John的計算過程

3.3算法的設(shè)計41分治策略是解決工作、學(xué)習(xí)和生活中常見問題的一種思維方法，它在組織管理和軍事領(lǐng)域得到廣泛的應(yīng)用例如：某大企業(yè)的銷售公司，由于其許多產(chǎn)品優(yōu)質(zhì)而非常暢銷，總部會到各地建立分支機(jī)構(gòu)，這其中就蘊涵著分治思想。3.3算法的設(shè)計再如：中國革命戰(zhàn)爭時期經(jīng)常遇到敵軍強(qiáng)大，因此采用集中優(yōu)勢兵力，逐個擊破的分治策略往往能產(chǎn)生以弱勝強(qiáng)的優(yōu)異戰(zhàn)果又如：各種大型體育賽事通常分為初賽和決賽，世界杯足球賽要從報名參賽的200多支球隊中選出成績最好的32支球隊,難度很大，成本也高。因此通過分區(qū)預(yù)選賽選出成績最好的32支球隊進(jìn)入決賽圈，這種做法也包含分治思想并降低了難度和復(fù)雜度。42五、貪心法

1.問題的提出3.3算法的設(shè)計假設(shè)有3種硬幣，它們的面值分別是1元、5角、1角?，F(xiàn)在有一個小孩買了價值6元2角的東西，并給售貨員10元錢。當(dāng)售貨員找給小孩零錢時，希望她找給小孩的硬幣數(shù)目最少。33103822223210381318這種簡單地從具有最大面值的幣種開始，按遞減的順序考慮各種幣種的方法稱為貪心法，或啟發(fā)式搜索法。432.貪心算法3.3算法的設(shè)計

貪心法的基本思想：將待求解的問題分解成若干個子問題進(jìn)行分步求解，且每一步總是做出當(dāng)前最好的選擇，即得到局部最優(yōu)解，再將各個局部最優(yōu)解整合成問題的解。貪心法體現(xiàn)了一種快刀斬亂麻的思想，以當(dāng)前和局部利益最大化為導(dǎo)向的問題求解策略。

利用貪心法求解問題的過程：①分解：將原問題分解為若干個相互獨立的階段；②解決：對每個階段求局部的最優(yōu)解，即進(jìn)行貪心選擇③合并：把各個階段的解合并為原問題的一個可行解。44利用貪心法對問題進(jìn)行求解的過程3.3算法的設(shè)計453.貪心法的應(yīng)用3.3算法的設(shè)計

[案例一]田忌賽馬戰(zhàn)國時期，齊威王與大將田忌賽馬，齊威王和田忌各有三匹好馬：上馬、中馬與下馬。比賽分三次進(jìn)行，每次賽馬以千金作賭。由于兩者的馬力相差無幾，而齊威王的馬分別比田忌相應(yīng)等級的馬要好，所以大家都認(rèn)為田忌必輸無疑。田忌采納了門客孫臏的意見，用下馬對齊威王的上馬，用上馬對齊威王的中馬，用中馬對齊威王的下馬，結(jié)果田忌以２比１勝齊威王而得千金。46將齊王的馬、田忌的馬均按上、中、下馬順序排列，齊王依次出馬，孫臏的貪心選擇策略：①若剩下的最強(qiáng)的馬都贏不了齊王剩下的最強(qiáng)的馬，選擇用最差的一匹馬對陣齊王最強(qiáng)的馬；②若剩下的最強(qiáng)的馬可以贏齊王剩下的最強(qiáng)的馬，選擇用這匹馬去贏齊王剩下的最強(qiáng)的馬；③若剩下的最強(qiáng)的馬和齊

王剩下的最強(qiáng)的馬打平的話，

可以選擇打平或者用最差的馬

輸?shù)舯荣悺?.3算法的設(shè)計47[案例二]電纜鋪設(shè)假設(shè)要在n個城市之間鋪設(shè)光纜,鋪設(shè)光纜費用很高，且各個城市之間鋪設(shè)光纜的費用不同，問如何鋪設(shè),使得n個城市的任意兩個之間都可以通信，且使鋪設(shè)光纜的總費用最低？3.3算法的設(shè)計可用圖論中的最小生成樹求解求解最小生成樹算法是貪心法

48

利用貪心法求解最小生成樹，其中一種貪心選擇策略是：貪心選擇權(quán)值最小的邊，若與之前加入的邊構(gòu)成回路，則放棄；否則，加入最小生成樹。3.3算法的設(shè)計電纜鋪設(shè)的最小生成樹49貪心算法是最接近于人類日常思維的一種問題求解方法，它已在人類工作和生活的各個領(lǐng)域得到廣泛的應(yīng)用。例如：公司招聘新員工是從一批應(yīng)聘者中招收最能干的人。再如：學(xué)校招生是從眾多報考者中招收一批最好的學(xué)生。這種按照某種標(biāo)準(zhǔn)挑選最接近該標(biāo)準(zhǔn)的人或物的做法就是貪心算法。

3.3算法的設(shè)計50六、動態(tài)規(guī)劃

1.問題的提出3.3算法的設(shè)計動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種方法。[案例一]GPS中的最優(yōu)路徑。全球定位系統(tǒng)GPS(GlobalPositioningSystem)可以為我們計算出滿足各種不同要求的、從出發(fā)地到目的地最優(yōu)路徑，可能是花費時間最短，也可能是過路費最少。GPS尋找最優(yōu)路徑的算法就是動態(tài)規(guī)劃算法。51假設(shè)計算下圖中頂點0到頂點6的最短路徑。第0階段第1階段第2階段第3階段第4階段3.3算法的設(shè)計52定義cost[i]：從頂點0到頂點i的最短路徑。第0階段：cost[0]=0第1階段：cost[1]=cost[0]+4=4cost[2]=cost[0]+5=5第2階段：cost[3]=min{cost[0]+8,cost[1]+4,cost[2]+5}=8第3階段：cost[4]=min{cost[1]+6,cost[3]+8}=10

cost[5]=min{cost[2]+7,cost[3]+9}=12第4階段：cost[6]=min{cost[4]+5,cost[3]+9,cost[5]+4}=15根據(jù)計算，從頂點0到頂點6的最短路徑值為15。從頂點6向前回溯，最短路徑為0→1→4→6。3.3算法的設(shè)計53

2.動態(tài)規(guī)劃算法3.3算法的設(shè)計動態(tài)規(guī)劃是美國數(shù)學(xué)家R.Bellman等人于1951年在研究多階段決策過程的優(yōu)化問題時創(chuàng)立的一種解決問題的新方法。在現(xiàn)實生活中，有一類問題可以將其活動過程分解成若干個相互聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。這種將一個問題看作是一個前后相互關(guān)聯(lián)且具有鏈狀結(jié)構(gòu)的多階段過程稱為多階段決策過程將解決多階段決策的最優(yōu)化的過程稱為動態(tài)規(guī)劃算法。54

動態(tài)規(guī)劃法主要適用于最優(yōu)化問題的求解：這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最?。┲档慕?。若存在若干個最優(yōu)值的解的話，它只取其中的一個。3.3算法的設(shè)計

動態(tài)規(guī)劃問題求解的基本思想：將待求解的問題分解為若干個互相聯(lián)系的子問題，然后按自底向上的順序推導(dǎo)出原問題的解。通過存儲子問題的解，可以避免在求解過程中重復(fù)多次求解同一個子問題，從而可以提高該算法的求解效率。動態(tài)規(guī)劃算法實質(zhì)是分治思想和冗余解決方法的結(jié)合。

553.動態(tài)規(guī)劃的應(yīng)用3.3算法的設(shè)計

[案例二]Fibonacci數(shù)列。

F[1]=1,F[2]=1,F[i]=F[i-1]+F[i-2],計算F[n](n≥3)動態(tài)規(guī)劃求Fibonacci數(shù)列的偽代碼描述如下：輸入：正整數(shù)n輸出：Fibonacci數(shù)列的第n項Fib(n)1F[1]←