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

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

（3）掌握算法設計方法

（4）數(shù)據(jù)結(jié)構(gòu)的基本概念2．難點結(jié)合實例掌握算法設計方法6.1 算法的概念目錄6.2 算法策略6.3算法設計與數(shù)據(jù)結(jié)構(gòu)6.4本章小結(jié)61974年圖靈獎獲得者DonaldErvinKnuth:計算機科學就是算法的研究TheArtofComputerProgramming6.1算法的概念算法（Algorithm）是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運算，是對解題方案的準確與完整的描述。算法是一種解決問題的方法，是數(shù)學及其應用的重要組成部分。

6.1.2算法的特性算法的一般應包含以下特性：（1）有窮性。（2）確定性。（3）可行性。（4）輸入。（5）輸出。6.1.3算法與計算機程序計算機輸入輸出算法問題算法與計算機之間的關系在計算機科學中，算法要用計算機算法語言描述，算法代表用計算機解一類問題的精確、有效的方法。算法+數(shù)據(jù)結(jié)構(gòu)=計算機程序6.1.4算法的控制結(jié)構(gòu)與描述1、算法的控制結(jié)構(gòu) 算法中各操作之間的執(zhí)行順序稱之為算法的控制結(jié)構(gòu)。 算法一般都可以用順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)三種基本控制結(jié)構(gòu)組合而成。10（1）、自然語言自然語言是人們?nèi)粘＿M行交流的語言，如漢語、英語等優(yōu)點：通俗易懂，即使沒有學過算法也能看懂算法執(zhí)行缺點：不夠嚴謹，容易出現(xiàn)歧義和錯誤2、算法的描述（2）、流程圖 用圖直觀地描述一個工作過程的具體步驟

常用來描述算法的圖形工具有：流程圖或程序框圖、N-S圖和PAD圖。

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

缺點：畫起來費事，不易修改。常用的流程圖符號：（3）偽代碼6.1.5算法的設計要求

1、正確性。2、可讀性。3、高效率與低存儲量。

6.2算法策略6.2.1窮舉法問題1：有一把鎖和一串鑰匙（共有10把鑰匙），怎樣找出所有開這把鎖的鑰匙？ 窮舉法又稱列舉法、枚舉法，是蠻力策略的具體體現(xiàn)，是一種簡單而直接地解決問題的方法。其基本思想是逐一列舉問題所涉及的所有情形，并根據(jù)問題提出的條件檢驗哪些是問題的解，哪些應予排除。

窮舉法的特點是算法設計比較簡單，解的可能為有限種，一一列舉問題所涉及的所有情形。 例如： 在QQ上，OicqPassOver這個工具窮舉用戶的口令，它根據(jù)機器性能最高可以每秒測試20000個口令，如果口令簡單，一分鐘內(nèi)，密碼就會遭到破譯。

窮舉法運用于一些經(jīng)典問題1、百錢百雞問題 中國古代算書張丘建的《算經(jīng)》中有一道著名的百雞問題：公雞每只值5文錢，母雞每只值3文錢，而3只小雞值1文錢?，F(xiàn)在用100文錢買100只雞，問：這100只雞中，公雞、母雞和小雞各有多少只？ 這個問題流傳很廣，解法很多，但從現(xiàn)代數(shù)學觀點來看，實際上是一個求不定方程整數(shù)解的問題。解法如下：設公雞、母雞、小雞分別為x、y、z只，由題意得：

用窮舉法求解，對每組求得滿足等式方程組的值，從而找到百錢百雞的解。用窮舉算法解決問題，通?？梢詮膬蓚€方面進行分析： 1、問題所涉及的情況：問題所涉及的情況有哪些，情況的種數(shù)可不可以確定。把它描述出來。 2、答案需要滿足的條件：分析出來的這些情況，需要滿足什么條件，才成為問題的答案，把這些條件描述出來。由于窮舉法窮舉的數(shù)據(jù)量過大，效率較低，對于小規(guī)模的問題還是適用的，但是問題規(guī)模一旦擴大，窮舉法就沒有什么可取性了。一般巧妙和高效算法很少來自窮舉法。6.2.2回溯法

迷宮游戲

回溯算法也叫試探法，是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。

回溯法的指導思想：走不通，就掉頭 回溯法在搜索過程中通過對約束條件的判定，排除錯誤答案，提高了搜索效率。網(wǎng)絡爬蟲網(wǎng)絡爬蟲是一個功能強大的自動提取網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)下載網(wǎng)頁，是搜索引擎的重要組成部分。它可以完全不依賴用戶干預實現(xiàn)網(wǎng)絡上的自動“爬行”和搜索。網(wǎng)絡爬蟲是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁在抓取網(wǎng)頁的時候，網(wǎng)絡爬蟲采用了深度優(yōu)先策略，深度優(yōu)先是指網(wǎng)絡爬蟲會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個起始頁，繼續(xù)跟蹤鏈接。這個方法有個優(yōu)點是網(wǎng)絡爬蟲在設計的時候比較容易。這是一種典型的回溯算法。回溯法的本質(zhì)也是一種窮舉法，但與窮舉法相比，回溯法的“聰明”之處在于能適時“回頭”，若再往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問題。6.2.3遞歸法人們都熟悉一個民間故事：從前有一座山，山上有一座廟，廟里有一個老和尚正在給小和尚講故事，故事里說，從前有一座山，山上有一座廟，廟里有一個老和尚正在給小和尚講故事，故事里說……。

所謂遞歸就是一個函數(shù)或過程可以直接或間接地調(diào)用自己。遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調(diào)用自己，稱為直接遞歸調(diào)用；如果一個算法A調(diào)用另一個算法B，而算法B又調(diào)用算法A，則此種遞歸稱為間接遞歸調(diào)用。德羅斯特效應

1、n！問題

階乘可以這樣遞歸地定義成函數(shù)：

這樣，所有自然數(shù)的階乘就可以通過上面的兩句話表示了。2的階乘就是1×2；3的階乘就是2的階乘乘3，即1×2×3……不僅如此，人們還可以知道0的階乘是多少，1的階乘應該等于0的階乘乘以1，顯然0的階乘必須是1才行。2、漢諾塔（Hanoi）問題

相傳印度有座大寺廟，它曾被認為是宇宙的中心。神廟中放置了一塊上面插有三根長木釘?shù)哪景澹谄渲械囊桓踞斏?，由上至下放?4片直徑由小至大的圓環(huán)形金屬片。古印度教的天神指示他的僧侶們將64片金屬片全部移至另一根木釘上。移動規(guī)則只有兩個： （1）在每次的移動中，只能移動一片金屬片； （2）過程中任意時刻必須保證金屬片小的在上，大的在下。 使用遞歸時必須符合以下三個條件： （1）可將一個問題轉(zhuǎn)化為一個新的問題，而新問題的解決方法仍與原問題的解法相同，只不過所處理的對象有所不同而已，即它們只是有規(guī)律的遞增或遞減。（2）可以通過轉(zhuǎn)化過程使問題回到對原問題的求解。（3）必須要有一個明確的結(jié)束遞歸的條件，否則遞歸會無止境地進行下去。遞歸對某些問題而言存在重復調(diào)用，導致算法效率不高。6.2.4分治法分治法的設計思想是將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。1、找出偽幣一個裝有16枚硬幣的袋子，16枚硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這枚偽造的硬幣。為了幫助你完成這一任務，將提供一臺可用來比較兩組硬幣重量的儀器，比如天平。利用這臺儀器，可以知道兩組硬幣的重量是否相同。

方法1任意取1枚硬幣，與其他硬幣進行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。最多可能有15次比較。方法2將硬幣分為8組，每組2個，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。最多可能有8次比較。方法3分析上述三種方法,分別需要比較18次,8次,4次,那么形成比較次數(shù)差異的根據(jù)原因在哪里?方法1:每枚硬幣都至少進行了一次比較,而有一枚硬幣進行了15次比較方法2:每一枚硬幣只進行了一次比較方法3:將硬幣分為兩組后一次比較可以將硬幣的范圍縮小到了原來的一半,這樣充分地利用了只有1枚偽幣的基本性質(zhì)。根據(jù)以上比較，第三種方法就是分治法，可以得到以下的采用分治方法的結(jié)論：1、參與比較的硬幣數(shù)量越多，使用該方法來實現(xiàn)就越快，而且投機性大大減少；2、解決方法關鍵在于能將大問題分割成若干小問題；3、小問題與原有問題是完全類似的。2、二分法二分查找又稱為折半查找，是一種可在有序順序表上實現(xiàn)的效率比較高的查找算法。是一個典型的分治算法。牛頓二分法二分法查找分治法所能解決的問題一般具有以下幾個特征：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。思考：求解一元二次方程實根6.2.5貪心法貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。只顧眼前利益，每次都選最好的1、商場找零 假設只有3種面額的幣值，它們的面值分別為20元、10元、5元、和1元?，F(xiàn)要找給某顧客37元，這時，售貨員幾乎不假思索地拿出1個20元、1個l0元、1個5元和2個1元的錢幣交給顧客。人們不僅能很快決定要拿哪些錢幣，而且與其它找法相比．這時拿出的錢幣的個數(shù)肯定是最少的。在這里，收貨員實際使用了這樣的算法：首先選出一個面值不超過37元的最大面額錢幣（20元），然后從37元中減去20元，剩下17元中再選出一個不超過17元的最大面額錢幣（10元），如此做下去，直到找足37元。這就是所謂的貪心法。2、最短距離

Dijkstra算法又稱為單源最短路徑，所謂單源是在一個有向圖中，從一個頂點出發(fā)，求該頂點至所有可到達頂點的最短路徑問題。

Dijstra算法是運用貪心的策略，從源點開始，不斷地通過相聯(lián)通的點找出到其他點的最短距離

基本思想是：

設置一個頂點的集合s，并不斷地擴充這個集合，一個頂點屬于集合s當且僅當從源點到該點的路徑已求出。開始時s中僅有源點，并且調(diào)整非s中點的最短路徑長度，找當前最短路徑點，將其加入到集合s，直到終點在s中。貪心法主要有以下兩個特點：（1）貪心選擇性質(zhì)：算法中每一步選擇都是當前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未作出的選擇。（2）最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)解（即局部最優(yōu)解），要保證最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。6.2.6動態(tài)規(guī)劃

動態(tài)規(guī)劃是運籌學的一個分支，是求解決策過程最優(yōu)化的數(shù)學方法。 20世紀50年代美國數(shù)學家貝爾曼（RechardBellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)性原理，把多階段決策過程轉(zhuǎn)化為一系列單階段問題逐個求解，創(chuàng)立了解決多階段過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃所處理的對象是多階段決策問題。多階段決策問題，是指這樣的一類特殊的活動過程，問題可以分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，形成一個決策序列，該決策序列也稱為一個策略。1、最短距離

Dijkstra算法又稱為單源最短路徑，所謂單源是在一個有向圖中，從一個頂點出發(fā)，求該頂點至所有可到達頂點的最短路徑問題。

基本