算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1、湖南工業(yè)大學(xué)計算機與通信學(xué)院湖南工業(yè)大學(xué)計算機與通信學(xué)院湖南工業(yè)大學(xué)計算機與通信學(xué)院湖南工業(yè)大學(xué)計算機與通信學(xué)院1、理解算法的基本概念及特性、理解算法的基本概念及特性2、掌握算法的三大結(jié)構(gòu)并了解其描述方法、掌握算法的三大結(jié)構(gòu)并了解其描述方法 3、結(jié)合實例理解算法設(shè)計方法：窮舉法、回溯法、遞歸法、結(jié)合實例理解算法設(shè)計方法：窮舉法、回溯法、遞歸法、分治法、貪心法以及動態(tài)規(guī)劃分治法、貪心法以及動態(tài)規(guī)劃4、認識數(shù)據(jù)結(jié)構(gòu)研究的三大內(nèi)容、認識數(shù)據(jù)結(jié)構(gòu)研究的三大內(nèi)容5、了解程序設(shè)計概念，了解程序設(shè)計語言的發(fā)展及分類、了解程序設(shè)計概念，了解程序設(shè)計語言的發(fā)展及分類 6.16.1算法的概念算法的概念6.2 6.

2、2 算法策略算法策略v 1974年圖靈獎獲得者年圖靈獎獲得者Donald Ervin Knuth: v 計算機科學(xué)就是算法的研究計算機科學(xué)就是算法的研究v The Art of Computer Programming6.1 6.1 算法的概念算法的概念算法算法（Algorithm）是一組有窮的規(guī)則，它們規(guī)定了解決某）是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運算，是對解題方案的準確與完一特定類型問題的一系列運算，是對解題方案的準確與完整的描述。整的描述。算法是一種解決問題的方法，是數(shù)學(xué)及其應(yīng)用的重要組成算法是一種解決問題的方法，是數(shù)學(xué)及其應(yīng)用的重要組成部分。部分。 6.1.2算

3、法的特性v算法的一般應(yīng)包含以下特性：算法的一般應(yīng)包含以下特性：v（1 1）有窮性。）有窮性。v（2 2）確定性。）確定性。v（3 3）可行性。）可行性。v（4 4） 輸入。輸入。v（5 5） 輸出輸出。6.1.36.1.3算法與計算機程序算法與計算機程序計算機計算機輸入輸入輸出輸出算法算法問題問題算法與計算機之間的關(guān)系算法與計算機之間的關(guān)系在計算機科學(xué)中，在計算機科學(xué)中，算法算法要用計算機算法語言要用計算機算法語言描述，描述，算法算法代表用計算機解一類問題的精確、代表用計算機解一類問題的精確、有效的方法。有效的方法。算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=計算機程序計算機程序6.1.4算法的控制結(jié)構(gòu)與描述

4、v1 1、算法的控制結(jié)構(gòu)、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序稱之為算法的算法中各操作之間的執(zhí)行順序稱之為算法的控制結(jié)構(gòu)?？刂平Y(jié)構(gòu)。算法一般都可以用算法一般都可以用順序結(jié)構(gòu)順序結(jié)構(gòu)、分支結(jié)構(gòu)分支結(jié)構(gòu)、循循環(huán)結(jié)構(gòu)環(huán)結(jié)構(gòu)三種基本控制結(jié)構(gòu)組合而成。三種基本控制結(jié)構(gòu)組合而成。（1 1）、自然語言）、自然語言自然語言自然語言是人們?nèi)粘＿M行交流的語言，如漢語、英語等是人們?nèi)粘＿M行交流的語言，如漢語、英語等優(yōu)點優(yōu)點：通俗易懂，即使沒有學(xué)過算法也能看懂算法執(zhí)行通俗易懂，即使沒有學(xué)過算法也能看懂算法執(zhí)行缺點缺點：不夠嚴謹，容易出現(xiàn)歧義和錯誤不夠嚴謹，容易出現(xiàn)歧義和錯誤2、算法的描述、算法的描述v（2 2）、

5、流程圖）、流程圖 用圖直觀地描述一個工作過程的具體步驟用圖直觀地描述一個工作過程的具體步驟 常用來描述算法的圖形工具有常用來描述算法的圖形工具有：流程圖或程序框圖、：流程圖或程序框圖、N-SN-S圖和圖和PADPAD圖。圖。 優(yōu)點優(yōu)點：直觀形象，簡潔明了。：直觀形象，簡潔明了。 缺點缺點：畫起來費事，不易修改。：畫起來費事，不易修改。常用的流程圖符號常用的流程圖符號：（3 3）偽代碼）偽代碼6.1.56.1.5算法的設(shè)計要求算法的設(shè)計要求 v1 1、正確性。、正確性。 v2 2、可讀性。、可讀性。 v3 3、高效率與低存儲量。、高效率與低存儲量。 6.2算法策略v6.2.1 6.2.1 窮舉法

6、窮舉法v問題問題1 1： 有一把鎖和一串鑰匙（共有有一把鎖和一串鑰匙（共有1010把鑰匙），怎樣把鑰匙），怎樣找出所有開這把鎖的鑰匙？找出所有開這把鎖的鑰匙？窮舉法窮舉法又稱列舉法、枚舉法，是蠻力策略的具體又稱列舉法、枚舉法，是蠻力策略的具體體現(xiàn)，是一種簡單而直接地解決問題的方法。其體現(xiàn)，是一種簡單而直接地解決問題的方法。其基本思想是逐一列舉問題所涉及的所有情形，并基本思想是逐一列舉問題所涉及的所有情形，并根據(jù)問題提出的條件檢驗?zāi)男┦菃栴}的解，哪些根據(jù)問題提出的條件檢驗?zāi)男┦菃栴}的解，哪些應(yīng)予排除。應(yīng)予排除。窮舉法窮舉法的的特點特點是算法設(shè)計比較簡單，解的可能為有是算法設(shè)計比較簡單，解的可能為

7、有限種，一一列舉問題所涉及的所有情形。限種，一一列舉問題所涉及的所有情形。例如：例如：在在QQQQ上，上，OicqPassOverOicqPassOver這個工具窮舉用戶的口這個工具窮舉用戶的口令，它根據(jù)機器性能最高可以每秒測試令，它根據(jù)機器性能最高可以每秒測試2000020000個口個口令，如果口令簡單，一分鐘內(nèi)，密碼就會遭到破譯令，如果口令簡單，一分鐘內(nèi)，密碼就會遭到破譯。 窮舉法運用于一些經(jīng)典問題窮舉法運用于一些經(jīng)典問題1 1、百錢百雞問題、百錢百雞問題中國古代算書張丘建的中國古代算書張丘建的算經(jīng)算經(jīng)中有一道著名的百雞問題：公中有一道著名的百雞問題：公雞每只值雞每只值5 5 文錢，母雞每

8、只值文錢，母雞每只值3 3 文錢，而文錢，而3 3 只小雞值只小雞值1 1 文錢?，F(xiàn)在文錢?，F(xiàn)在用用100 100 文錢買文錢買100 100 只雞，問：這只雞，問：這100 100 只雞中，公雞、母雞和小雞各只雞中，公雞、母雞和小雞各有多少只？有多少只？這個問題流傳很廣，解法很多，但從現(xiàn)代數(shù)學(xué)觀點來看，實際這個問題流傳很廣，解法很多，但從現(xiàn)代數(shù)學(xué)觀點來看，實際上是一個求不定方程整數(shù)解的問題。解法如下：設(shè)公雞、母雞、小上是一個求不定方程整數(shù)解的問題。解法如下：設(shè)公雞、母雞、小雞分別為雞分別為x x、y y、z z 只，由題意得：只，由題意得：用窮舉法求解，對每組求得滿足等式方程組的值，從而找到

9、百用窮舉法求解，對每組求得滿足等式方程組的值，從而找到百錢百雞的解。錢百雞的解。031003331201100335100 mod,/zzyxzyxzyxv 用用窮舉窮舉算法解決問題，通?？梢詮膬蓚€方面進行分析：算法解決問題，通?？梢詮膬蓚€方面進行分析：1 1、問題所涉及的情況：問題所涉及的情況有哪些，情況的、問題所涉及的情況：問題所涉及的情況有哪些，情況的種數(shù)可不可以確定。把它描述出來。種數(shù)可不可以確定。把它描述出來。2 2、答案需要滿足的條件：分析出來的這些情況，需要滿足、答案需要滿足的條件：分析出來的這些情況，需要滿足什么條件，才成為問題的答案，把這些條件描述出來。什么條件，才成為問題的

10、答案，把這些條件描述出來。v 由于由于窮舉法窮舉法窮舉的數(shù)據(jù)量過大，效率較低，對于小規(guī)模的問窮舉的數(shù)據(jù)量過大，效率較低，對于小規(guī)模的問題還是適用的，但是問題規(guī)模一旦擴大，窮舉法就沒有什么題還是適用的，但是問題規(guī)模一旦擴大，窮舉法就沒有什么可取性了。一般巧妙和高效算法很少來自窮舉法?？扇⌒粤?。一般巧妙和高效算法很少來自窮舉法。6.2.2 6.2.2 回溯法回溯法迷宮游戲迷宮游戲回溯算法回溯算法也叫試探法，是一種選優(yōu)搜索法，按選也叫試探法，是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標(biāo)。但當(dāng)探索到某一優(yōu)條件向前搜索，以達到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退步時，發(fā)現(xiàn)原

11、先選擇并不優(yōu)或達不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點回溯點”?；厮莘ɑ厮莘ǖ闹笇?dǎo)思想：走不通，就掉頭的指導(dǎo)思想：走不通，就掉頭回溯法回溯法在搜索過程中通過對約束條件的判定，排在搜索過程中通過對約束條件的判定，排除錯誤答案，提高了搜索效率。除錯誤答案，提高了搜索效率。網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲v 網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲是一個功能強大的自動提取是一個功能強大的自動提取網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)下載網(wǎng)頁，是搜索引擎的重要組成部

12、下載網(wǎng)頁，是搜索引擎的重要組成部分。它可以完全不依賴用戶干預(yù)實現(xiàn)分。它可以完全不依賴用戶干預(yù)實現(xiàn)網(wǎng)絡(luò)上的自動網(wǎng)絡(luò)上的自動“爬行爬行”和搜索。和搜索。v 網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲是通過網(wǎng)頁的鏈接地址來尋是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁在抓取網(wǎng)頁的時候，找網(wǎng)頁在抓取網(wǎng)頁的時候，網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲采用了采用了深度優(yōu)先深度優(yōu)先策略，策略，深度優(yōu)先深度優(yōu)先是指是指網(wǎng)絡(luò)爬蟲網(wǎng)絡(luò)爬蟲會從起始頁開始，一個鏈接會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路一個鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個起始頁，繼續(xù)跟蹤之后再轉(zhuǎn)入下一個起始頁，繼續(xù)跟蹤鏈接。這個方法有個優(yōu)點是網(wǎng)絡(luò)爬蟲鏈接。這個方法有個優(yōu)點是網(wǎng)絡(luò)爬蟲

13、在設(shè)計的時候比較容易。這是一種典在設(shè)計的時候比較容易。這是一種典型的回溯算法。型的回溯算法。v回溯法回溯法的本質(zhì)也是一種窮舉法，但與窮舉法相比，的本質(zhì)也是一種窮舉法，但與窮舉法相比，回溯法的回溯法的“聰明聰明”之處在于能適時之處在于能適時“回頭回頭”，若再，若再往前走不可能得到解，就回溯，退一步另找線路，往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。因此，回溯與窮舉相這樣可省去大量的無效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問題比，回溯更適宜于量比較大，候選解比較多的問題。6.2.3 遞歸法v人們都熟悉一個民間故事：從前有一座山，山上人們都熟悉

14、一個民間故事：從前有一座山，山上有一座廟，廟里有一個老和尚正在給小和尚講故有一座廟，廟里有一個老和尚正在給小和尚講故事，故事里說，從前有一座山，山上有一座廟，事，故事里說，從前有一座山，山上有一座廟，廟里有一個老和尚正在給小和尚講故事，故事里廟里有一個老和尚正在給小和尚講故事，故事里說說。 v所謂所謂遞歸遞歸就是一個函數(shù)或過程可以直接或間接地調(diào)就是一個函數(shù)或過程可以直接或間接地調(diào)用自己。用自己。v遞歸遞歸分為分為直接遞歸直接遞歸和和間接遞歸間接遞歸兩種方法。兩種方法。v如果一個算法直接調(diào)用自己，稱為如果一個算法直接調(diào)用自己，稱為直接遞歸調(diào)用直接遞歸調(diào)用；v如果一個算法如果一個算法A A調(diào)用另一

15、個算法調(diào)用另一個算法B B，而算法，而算法B B又調(diào)用又調(diào)用算法算法A A，則此種遞歸稱為，則此種遞歸稱為間接遞歸調(diào)用間接遞歸調(diào)用。德德羅羅斯斯特特效效應(yīng)應(yīng) 1 1、n n！問題！問題階乘可以這樣遞歸地定義成函數(shù)：階乘可以這樣遞歸地定義成函數(shù)：這樣，所有自然數(shù)的階乘就可以通過上面的兩句話表這樣，所有自然數(shù)的階乘就可以通過上面的兩句話表示了。示了。2 2的階乘就是的階乘就是1 12 2；3 3的階乘就是的階乘就是2 2的階乘乘的階乘乘3 3，即，即1 12 23 3不僅如此，人們還可以知道不僅如此，人們還可以知道0 0的階乘是多少，的階乘是多少，1 1的階乘應(yīng)該等于的階乘應(yīng)該等于0 0的階乘乘以

16、的階乘乘以1 1，顯然，顯然0 0的階乘必須是的階乘必須是1 1才才行。行。)0()0()!1(*1!nnnnn) 0() 0() 1(*1)(nnnfnnf2 2、漢諾塔（、漢諾塔（HanoiHanoi）問題）問題 相傳印度有座大寺廟，它曾被認為是宇宙的中心。神廟中放置相傳印度有座大寺廟，它曾被認為是宇宙的中心。神廟中放置了一塊上面插有三根長木釘?shù)哪景?，在其中的一根木釘上，由上至下了一塊上面插有三根長木釘?shù)哪景?，在其中的一根木釘上，由上至下放了放?464片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧侶們將侶們將6464片金屬片全

17、部移至另一根木釘上。移動規(guī)則只有兩個：片金屬片全部移至另一根木釘上。移動規(guī)則只有兩個：（1 1）在每次的移動中，只能移動一片金屬片；）在每次的移動中，只能移動一片金屬片；（2 2）過程中任意時刻必須保證金屬片小的在上，大的在下。）過程中任意時刻必須保證金屬片小的在上，大的在下。v使用使用遞歸遞歸時必須符合以下三個條件：時必須符合以下三個條件：（1 1）可將一個問題轉(zhuǎn)化為一個新的問題，而新問）可將一個問題轉(zhuǎn)化為一個新的問題，而新問題的解決方法仍與原問題的解法相同，只不過所處題的解決方法仍與原問題的解法相同，只不過所處理的對象有所不同而已，即它們只是有規(guī)律的遞增理的對象有所不同而已，即它們只是有規(guī)

18、律的遞增或遞減?；蜻f減。 （2 2）可以通過轉(zhuǎn)化過程使問題回到對原問題的求）可以通過轉(zhuǎn)化過程使問題回到對原問題的求解。解。 （3 3）必須要有一個明確的結(jié)束遞歸的條件，否則）必須要有一個明確的結(jié)束遞歸的條件，否則遞歸會無止境地進行下去。遞歸會無止境地進行下去。v遞歸遞歸對某些問題而言存在重復(fù)調(diào)用，導(dǎo)致算法效率對某些問題而言存在重復(fù)調(diào)用，導(dǎo)致算法效率不高。不高。6.2.4 分治法v 分治法分治法的設(shè)計思想是將一個難以直接解決的大問題，分割成的設(shè)計思想是將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。一些規(guī)模較小的相同問題，以便各個擊破，分而治之。v 分治法分治法

19、所能解決的問題一般具有以下幾個特征：所能解決的問題一般具有以下幾個特征：（1 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2 2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（3 3）利用該問題分解出的子問題的解可以合并為該問題的解；）利用該問題分解出的子問題的解可以合并為該問題的解；（4 4）該問題所分解出的各個子問題是相互獨立的，即子問題之）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。間不包含公共的子問題。 1

20、 1、找出偽幣、找出偽幣v 一個裝有一個裝有1 61 6枚硬幣的袋子，枚硬幣的袋子，1 61 6枚硬幣中有一個是偽造枚硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。你的任的，并且那個偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這枚偽造的硬幣。務(wù)是找出這枚偽造的硬幣。v 為了幫助你完成這一任務(wù)，將提供一臺可用來比較兩組為了幫助你完成這一任務(wù)，將提供一臺可用來比較兩組硬幣重量的儀器，比如天平。利用這臺儀器，可以知道硬幣重量的儀器，比如天平。利用這臺儀器，可以知道兩組硬幣的重量是否相同。兩組硬幣的重量是否相同。 方法方法1 1v 任意取任意取1 1枚硬幣，與其他硬幣進行比較，若發(fā)現(xiàn)輕者

21、，枚硬幣，與其他硬幣進行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。最多可能有這那枚為偽幣。最多可能有1515次比較。次比較。 方法方法2 2v 將硬幣分為將硬幣分為8 8組，每組組，每組2 2個，每組比較一次，若發(fā)現(xiàn)輕的，個，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。最多可能有則為偽幣。最多可能有8 8次比較。次比較。 方法方法3 3分析分析v上述三種方法上述三種方法, ,分別需要比較分別需要比較1818次次,8,8次次,4,4次次, ,那么那么形成比較次數(shù)差異的根據(jù)原因在哪里形成比較次數(shù)差異的根據(jù)原因在哪里? ?v方法方法1:1:每枚硬幣都至少進行了一次比較每枚硬幣都至少進行了一次比較, ,而有一枚而有一枚

22、硬幣進行了硬幣進行了1515次比較次比較v方法方法2:2:每一枚硬幣只進行了一次比較每一枚硬幣只進行了一次比較v方法方法3:3:將硬幣分為兩組后一次比較可以將硬幣的將硬幣分為兩組后一次比較可以將硬幣的范圍縮小到了原來的一半范圍縮小到了原來的一半, ,這樣充分地利用了只有這樣充分地利用了只有1 1枚偽幣的基本性質(zhì)。枚偽幣的基本性質(zhì)。v根據(jù)以上比較，第三種方法就是根據(jù)以上比較，第三種方法就是分治法分治法，可以得到，可以得到以下的采用以下的采用分治方法分治方法的結(jié)論：的結(jié)論：1 1、參與比較的硬幣數(shù)量越多，使用該方法來實現(xiàn)就越、參與比較的硬幣數(shù)量越多，使用該方法來實現(xiàn)就越快，而且投機性大大減少；快，

23、而且投機性大大減少；2 2、解決方法關(guān)鍵在于能將大問題分割成若干小問題；、解決方法關(guān)鍵在于能將大問題分割成若干小問題；3 3、小問題與原有問題是完全類似的。、小問題與原有問題是完全類似的。2 2、二分法、二分法v二分查找二分查找又稱為折半查找，是一種可在有序順序又稱為折半查找，是一種可在有序順序表上實現(xiàn)的效率比較高的查找算法。是一個典型表上實現(xiàn)的效率比較高的查找算法。是一個典型的的分治算法分治算法。n牛頓二分法牛頓二分法n二分法查找二分法查找v 分治法分治法所能解決的問題一般具有以下幾個特征：所能解決的問題一般具有以下幾個特征：（1 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；）該問題的

24、規(guī)?？s小到一定的程度就可以容易地解決；（2 2）該問題可以分解為若干個規(guī)模較小的相同問題，即該）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（3 3）利用該問題分解出的子問題的解可以合并為該問題的）利用該問題分解出的子問題的解可以合并為該問題的解；解；（4 4）該問題所分解出的各個子問題是相互獨立的，即子問）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。題之間不包含公共的子問題。思考：求解一元二次方程實根思考：求解一元二次方程實根6.2.5 貪心法v 貪心算法貪心算法（又稱貪婪算法）是指，（又稱貪婪算法）是指，在對問題

25、求解時，總是做出在當(dāng)前在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，所做出的從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的僅是在某種意義上的局部最優(yōu)解。局部最優(yōu)解。v 貪心算法貪心算法不是對所有問題都能得到不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題它能產(chǎn)生整體最優(yōu)解或者許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。是整體最優(yōu)解的近似解。v 只顧眼前利益，每次都選最好的只顧眼前利益，每次都選最好的1 1、商場找零、商場找零假設(shè)只有假設(shè)只有3 3種面額的幣值，它們的面值分別為種

26、面額的幣值，它們的面值分別為2020元、元、1010元、元、5 5元、和元、和1 1元?，F(xiàn)要找給某顧客元?，F(xiàn)要找給某顧客3737元，這時，售貨員元，這時，售貨員幾乎不假思索地拿出幾乎不假思索地拿出1 1個個2020元、元、1 1個個l0l0元、元、1 1個個5 5元和元和2 2個個1 1元元的錢幣交給顧客。人們不僅能很快決定要拿哪些錢幣，而的錢幣交給顧客。人們不僅能很快決定要拿哪些錢幣，而且與其它找法相比這時拿出的錢幣的個數(shù)肯定是最少的且與其它找法相比這時拿出的錢幣的個數(shù)肯定是最少的。在這里，收貨員實際使用了這樣的算法：首先選出一個。在這里，收貨員實際使用了這樣的算法：首先選出一個面值不超過面

27、值不超過3737元的最大面額錢幣（元的最大面額錢幣（2020元），然后從元），然后從3737元中元中減去減去2020元，剩下元，剩下1717元中再選出一個不超過元中再選出一個不超過1717元的最大面額元的最大面額錢幣（錢幣（1010元），如此做下去，直到找足元），如此做下去，直到找足3737元。這就是所謂元。這就是所謂的貪心法。的貪心法。2 2、最短距離、最短距離 DijkstraDijkstra算法又稱為單源最短算法又稱為單源最短路徑，所謂單源是在一個有向路徑，所謂單源是在一個有向圖中，從一個頂點出發(fā)，求該圖中，從一個頂點出發(fā)，求該頂點至所有可到達頂點的最短頂點至所有可到達頂點的最短路徑問題

28、。路徑問題。 DijstraDijstra算法是運用貪心算法是運用貪心的策略，從源點開始，不斷地的策略，從源點開始，不斷地通過相聯(lián)通的點找出到其他點通過相聯(lián)通的點找出到其他點的最短距離的最短距離基本思想是：基本思想是： 設(shè)置一個頂點的集合設(shè)置一個頂點的集合s s，并不斷地擴充這個集合，一個并不斷地擴充這個集合，一個頂點屬于集合頂點屬于集合s s當(dāng)且僅當(dāng)從源點當(dāng)且僅當(dāng)從源點到該點的路徑已求出。開始時到該點的路徑已求出。開始時s s中僅有源點，并且調(diào)整非中僅有源點，并且調(diào)整非s s中點中點的最短路徑長度，找當(dāng)前最短的最短路徑長度，找當(dāng)前最短路徑點，將其加入到集合路徑點，將其加入到集合s s，直，直

29、到終點在到終點在s s中。中。v貪心法貪心法主要有以下兩個特點：主要有以下兩個特點： （1 1）貪心選擇性質(zhì)貪心選擇性質(zhì)：算法中每一步選擇都是當(dāng)前看：算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的選擇，似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未作出的選擇。但不依賴于未作出的選擇。（2 2）最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)：算法中每一次都取得了最優(yōu)解（即局部最優(yōu)解），要保證最后的結(jié)果最優(yōu)，解（即局部最優(yōu)解），要保證最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。則必須滿足全局最優(yōu)解包含局部最優(yōu)解。6.2.6 動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃是運籌學(xué)的

30、一個分支，是求解決策過是運籌學(xué)的一個分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。程最優(yōu)化的數(shù)學(xué)方法。2020世紀世紀5050年代美國數(shù)學(xué)家貝爾曼（年代美國數(shù)學(xué)家貝爾曼（Rechard Rechard BellmanBellman）等人在研究多階段決策過程的優(yōu)化問題）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)性原理，把多階段決策過時，提出了著名的最優(yōu)性原理，把多階段決策過程轉(zhuǎn)化為一系列單階段問題逐個求解，創(chuàng)立了解程轉(zhuǎn)化為一系列單階段問題逐個求解，創(chuàng)立了解決多階段過程優(yōu)化問題的新方法決多階段過程優(yōu)化問題的新方法動態(tài)規(guī)劃動態(tài)規(guī)劃。v動態(tài)規(guī)劃動態(tài)規(guī)劃所處理的對象是所處理的對象是多階段決策問題多階

31、段決策問題。v多階段決策問題多階段決策問題，是指這樣的一類特殊的活動過，是指這樣的一類特殊的活動過程，問題可以分解成若干相互聯(lián)系的階段，在每程，問題可以分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，形成一個決策序列，該一個階段都要做出決策，形成一個決策序列，該決策序列也稱為一個策略。決策序列也稱為一個策略。1 1、最短距離、最短距離 DijkstraDijkstra算法又稱為單源最短算法又稱為單源最短路徑，所謂單源是在一個有向路徑，所謂單源是在一個有向圖中，從一個頂點出發(fā)，求該圖中，從一個頂點出發(fā)，求該頂點至所有可到達頂點的最短頂點至所有可到達頂點的最短路徑問題。路徑問題。 基本思想是：

32、基本思想是： 設(shè)置一個頂點的集合設(shè)置一個頂點的集合s s，并不斷地擴充這個集合，一個并不斷地擴充這個集合，一個頂點屬于集合頂點屬于集合s s當(dāng)且僅當(dāng)從源點當(dāng)且僅當(dāng)從源點到該點的路徑已求出。開始時到該點的路徑已求出。開始時s s中僅有源點，并且調(diào)整非中僅有源點，并且調(diào)整非s s中點中點的最短路徑長度，找當(dāng)前最短的最短路徑長度，找當(dāng)前最短路徑點，將其加入到集合路徑點，將其加入到集合s s，直，直到終點在到終點在s s中。中。2 2、背包問題、背包問題背包問題的一個例子：應(yīng)該選擇哪些盒背包問題的一個例子：應(yīng)該選擇哪些盒子，才能使價格盡可能地大，而保持重子，才能使價格盡可能地大，而保持重量小于或等于量

33、小于或等于15 kg？背包問題背包問題(Knapsack problem)可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。背包問題背包問題0-10-1背包問題的描述是：有背包問題的描述是：有N N件物品和一個容量件物品和一個容量為為V V的背包。第的背包。第i i件物品的容量是件物品的容量是cici，價值是，價值是wiwi。求解將哪些物品裝入背包可使價值總和。求解將哪些物品裝入背包可使價值總和最大。這是最基礎(chǔ)的背包問題，特點是：每種最大。這是最基礎(chǔ)的背包問題，特點是：每種物品

34、僅有一件，可以選擇放或不放。物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即用子問題定義狀態(tài)：即fivfiv表示前表示前i i件件物品恰放入一個容量為物品恰放入一個容量為v v的背包可以獲得的最的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：大價值。則其狀態(tài)轉(zhuǎn)移方程便是：fiv=maxfi-1v,fi-1v-ci+wi這個方程的含義是這個方程的含義是：“將前將前i i件物品放入容量為件物品放入容量為v v的背包中的背包中”這個子問題，若只考慮第這個子問題，若只考慮第i i件物品的策略（放或不放），那件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前么就可以轉(zhuǎn)化為一個只牽扯前i-1i-1

35、件物品的問題。件物品的問題。如果不放第如果不放第i i件物品，那么問題就轉(zhuǎn)化為件物品，那么問題就轉(zhuǎn)化為“前前i-1i-1件物品放件物品放入容量為入容量為v v的背包中的背包中”，價值為，價值為fi-1vfi-1v；如果放第；如果放第i i件物品件物品，那么問題就轉(zhuǎn)化為，那么問題就轉(zhuǎn)化為“前前i-1i-1件物品放入剩下的容量為件物品放入剩下的容量為v-civ-ci的背包中的背包中”，此時能獲得的最大價值就是，此時能獲得的最大價值就是fi-1v-cifi-1v-ci再加再加上通過放入第上通過放入第i i件物品獲得的價值件物品獲得的價值wiwi。fiv=maxfi-1v,fi-1v-ci+wiv多階

36、段決策問題的多階段決策問題的最優(yōu)化求解目標(biāo)最優(yōu)化求解目標(biāo)是獲取導(dǎo)致問是獲取導(dǎo)致問題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到最優(yōu)解最優(yōu)解。v動態(tài)規(guī)劃動態(tài)規(guī)劃思想實質(zhì)是思想實質(zhì)是分治思想分治思想和和冗余解決冗余解決方法的方法的結(jié)合。結(jié)合。v動態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又動態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，動態(tài)規(guī)劃三要素是的狀態(tài)中產(chǎn)生出來的，所以，動態(tài)規(guī)劃三要素是階段、狀態(tài)、決策。階段、狀態(tài)、決策。v動態(tài)規(guī)劃法動態(tài)規(guī)劃法多用來計算最

37、優(yōu)問題，動態(tài)規(guī)劃法與多用來計算最優(yōu)問題，動態(tài)規(guī)劃法與分治法的基本思想是一致的，但處理的手法不同分治法的基本思想是一致的，但處理的手法不同。動態(tài)規(guī)劃法在運用時，要先對問題的分治規(guī)律。動態(tài)規(guī)劃法在運用時，要先對問題的分治規(guī)律進行分析，找出終結(jié)子問題，以及子問題向父問進行分析，找出終結(jié)子問題，以及子問題向父問題歸納的規(guī)則，而算法則直接從終結(jié)子問題開始題歸納的規(guī)則，而算法則直接從終結(jié)子問題開始求解，逐層向上歸納，直到歸納出原問題的解。求解，逐層向上歸納，直到歸納出原問題的解。6.3 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計語言6.3.1 6.3.1 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述電話是通訊聯(lián)絡(luò)必不可少的工具。如何用計算機來實電話

38、是通訊聯(lián)絡(luò)必不可少的工具。如何用計算機來實現(xiàn)自動查詢電話號碼呢？要求對于給定的任意姓名，如果現(xiàn)自動查詢電話號碼呢？要求對于給定的任意姓名，如果該人有電話號碼，則迅速給出電話號碼，否則，給出查找該人有電話號碼，則迅速給出電話號碼，否則，給出查找不到該人電話號碼的信息。不到該人電話號碼的信息。為了提高查找效率，就必須了解待處理對象之間的關(guān)為了提高查找效率，就必須了解待處理對象之間的關(guān)系，以及如何存儲和表示這些數(shù)據(jù)。系，以及如何存儲和表示這些數(shù)據(jù)。 電話號碼經(jīng)過處理，按照拼音排好了順序，每個電話電話號碼經(jīng)過處理，按照拼音排好了順序，每個電話號碼之間的先后次序就是數(shù)據(jù)元素之間的關(guān)系。號碼之間的先后次序

39、就是數(shù)據(jù)元素之間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是研究這類非數(shù)值處理的程序設(shè)計問題。就是研究這類非數(shù)值處理的程序設(shè)計問題。v數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)系稱為結(jié)構(gòu)系稱為結(jié)構(gòu)(Structure)(Structure)。v一般來說包括以下三方面：一般來說包括以下三方面：數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、數(shù)、數(shù)據(jù)的據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)和數(shù)據(jù)的和數(shù)據(jù)的運算運算。（1 1）數(shù)據(jù)的邏輯結(jié)構(gòu)）數(shù)

40、據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的在計是指數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的在計算機內(nèi)部是如何算機內(nèi)部是如何存儲無關(guān)存儲無關(guān)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)獨立獨立于計算機。于計算機。v 數(shù)據(jù)結(jié)構(gòu)可分為數(shù)據(jù)結(jié)構(gòu)可分為線性數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)和和非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)的邏輯特征是除第一個結(jié)點和最后一個結(jié)點外，其他線性結(jié)構(gòu)的邏輯特征是除第一個結(jié)點和最后一個結(jié)點外，其他所有結(jié)點都有且只有一個直接前趨和一個直接后繼結(jié)點。所有結(jié)點都有且只有一個直接前趨和一個直接后繼結(jié)點。非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點可能有多個直接前趨和直接非線性結(jié)構(gòu)的邏輯特征是一

41、個結(jié)點可能有多個直接前趨和直接后繼。后繼。v 為了進一步研究數(shù)據(jù)的邏輯結(jié)構(gòu)，可以將數(shù)據(jù)的邏輯結(jié)構(gòu)分為為了進一步研究數(shù)據(jù)的邏輯結(jié)構(gòu)，可以將數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。v 線性結(jié)構(gòu)包括：線性表、棧和隊列等。線性結(jié)構(gòu)包括：線性表、棧和隊列等。v 非線性結(jié)構(gòu)包括樹和圖型結(jié)構(gòu)。非線性結(jié)構(gòu)包括樹和圖型結(jié)構(gòu)。（2 2）數(shù)據(jù)的存儲結(jié)構(gòu)）數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)( (是研究數(shù)據(jù)是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計算機中表示，是邏輯數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計算機中表示，是邏輯數(shù)據(jù)的存儲映

42、像，它是的存儲映像，它是面向計算機面向計算機的。的。數(shù)據(jù)在存儲器中的存儲有四種基本的映像方法：數(shù)據(jù)在存儲器中的存儲有四種基本的映像方法： 順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)。 鏈式存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)。 索引存儲結(jié)構(gòu)。索引存儲結(jié)構(gòu)。 散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)。 （3 3）數(shù)據(jù)的運算）數(shù)據(jù)的運算數(shù)據(jù)的運算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，數(shù)據(jù)的運算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，也就是刪除、檢索和排序等與問題相關(guān)的處理。也就是刪除、檢索和排序等與問題相關(guān)的處理。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)通常具有下列一些基本操作：通常具有下列一些基本操作：插入：在數(shù)據(jù)結(jié)構(gòu)的指定位置上添加一個新結(jié)點。插入：在數(shù)據(jù)結(jié)構(gòu)的指定位置上添加一個

43、新結(jié)點。刪除：刪去數(shù)據(jù)結(jié)構(gòu)中指定位置的結(jié)點。刪除：刪去數(shù)據(jù)結(jié)構(gòu)中指定位置的結(jié)點。更新：修改數(shù)據(jù)結(jié)構(gòu)中某個結(jié)點的值。更新：修改數(shù)據(jù)結(jié)構(gòu)中某個結(jié)點的值。查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足指定條件的結(jié)點及其位置。查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足指定條件的結(jié)點及其位置。排序：按照指定的順序，使結(jié)點重新排列排序：按照指定的順序，使結(jié)點重新排列。6.3.2程序設(shè)計語言簡介1 1、程序設(shè)計概念、程序設(shè)計概念程序設(shè)計程序設(shè)計(Programming)(Programming)是給出解決特定問題程序的是給出解決特定問題程序的過程，是軟件構(gòu)造活動中的重要組成部分。過程，是軟件構(gòu)造活動中的重要組成部分。程序設(shè)計是指設(shè)計、編制、調(diào)

44、試程序的方法和過程。程序設(shè)計是指設(shè)計、編制、調(diào)試程序的方法和過程。程序程序= =數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +算法算法程序設(shè)計規(guī)范是進行程序設(shè)計的具體規(guī)定。程序設(shè)計程序設(shè)計規(guī)范是進行程序設(shè)計的具體規(guī)定。程序設(shè)計要本著要本著“清晰第一，效率第二清晰第一，效率第二”的風(fēng)格。的風(fēng)格。 v 按照結(jié)構(gòu)性質(zhì)，有按照結(jié)構(gòu)性質(zhì)，有結(jié)構(gòu)化結(jié)構(gòu)化程序設(shè)計與程序設(shè)計與非結(jié)構(gòu)化非結(jié)構(gòu)化程序設(shè)計程序設(shè)計v 按照用戶的要求，有按照用戶的要求，有過程式過程式程序設(shè)計與程序設(shè)計與非過程式非過程式程序設(shè)計程序設(shè)計 v 按照程序設(shè)計風(fēng)格，有按照程序設(shè)計風(fēng)格，有邏輯式邏輯式程序設(shè)計、程序設(shè)計、函數(shù)式函數(shù)式程序設(shè)計程序設(shè)計、對象式對象式程序

45、設(shè)計。程序設(shè)計。 v程序設(shè)計過程包括程序設(shè)計過程包括分析分析、設(shè)計設(shè)計、編碼編碼、測試測試、排排錯錯等階段等階段 2 2、程序設(shè)計語言、程序設(shè)計語言v程序設(shè)計語言程序設(shè)計語言，通常簡稱為編程語言，是一組用，通常簡稱為編程語言，是一組用來定義計算機程序的來定義計算機程序的語法規(guī)則語法規(guī)則。 v程序設(shè)計語言包含三個方面，即程序設(shè)計語言包含三個方面，即語法語法、語義語義和和語語用用 v程序設(shè)計語言程序設(shè)計按照語言級別可以分為程序設(shè)計語言程序設(shè)計按照語言級別可以分為低低級語言級語言和和高級語言高級語言。3 3、面向過程和面向?qū)ο?、面向過程和面向?qū)ο? 4、語言處理程序、語言處理程序5 5、程序設(shè)計的一

46、般過程、程序設(shè)計的一般過程（1 1）確定要解決的問題）確定要解決的問題（2 2）分析問題，建立數(shù)學(xué)模型）分析問題，建立數(shù)學(xué)模型（3 3）確定數(shù)據(jù)結(jié)構(gòu)和算法）確定數(shù)據(jù)結(jié)構(gòu)和算法（4 4）編寫程序）編寫程序（5 5）調(diào)試程序）調(diào)試程序（6 6）整理資料，交付使用）整理資料，交付使用6.3.3結(jié)構(gòu)化程序設(shè)計v結(jié)構(gòu)化程序設(shè)計，它的基本思想是結(jié)構(gòu)化程序設(shè)計，它的基本思想是“自頂向下，自頂向下，逐步求精，模塊化，限制使用逐步求精，模塊化，限制使用gotogoto語句語句”和和“單單入口單出口入口單出口”的控制結(jié)構(gòu)。的控制結(jié)構(gòu)。v基于這樣的思想，提出了三種基本結(jié)構(gòu)，由這三基于這樣的思想，提出了三種基本結(jié)構(gòu)，由這三種基本結(jié)構(gòu)組成的程序，就是結(jié)構(gòu)化程序。種基本結(jié)構(gòu)組成的程序，就是結(jié)構(gòu)化程序。v1 1、順序順序結(jié)構(gòu)結(jié)構(gòu)v2 2、分支分支結(jié)構(gòu)結(jié)構(gòu)v3 3、循環(huán)循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)