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

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

（3）掌握算法設(shè)計(jì)方法

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

6.1.2算法的特性算法的一般應(yīng)包含以下特性：（1）有窮性。（2）確定性。（3）可行性。（4）輸入。（5）輸出。6.1.3算法與計(jì)算機(jī)程序計(jì)算機(jī)輸入輸出算法問(wèn)題算法與計(jì)算機(jī)之間的關(guān)系在計(jì)算機(jī)科學(xué)中，算法要用計(jì)算機(jī)算法語(yǔ)言描述，算法代表用計(jì)算機(jī)解一類問(wèn)題的精確、有效的方法。算法+數(shù)據(jù)結(jié)構(gòu)=計(jì)算機(jī)程序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）、自然語(yǔ)言自然語(yǔ)言是人們?nèi)粘＿M(jìn)行交流的語(yǔ)言，如漢語(yǔ)、英語(yǔ)等優(yōu)點(diǎn)：通俗易懂，即使沒(méi)有學(xué)過(guò)算法也能看懂算法執(zhí)行缺點(diǎn)：不夠嚴(yán)謹(jǐn)，容易出現(xiàn)歧義和錯(cuò)誤2、算法的描述（2）、流程圖 用圖直觀地描述一個(gè)工作過(guò)程的具體步驟

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

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

缺點(diǎn)：畫(huà)起來(lái)費(fèi)事，不易修改。常用的流程圖符號(hào)：（3）偽代碼6.1.5算法的設(shè)計(jì)要求

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

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

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

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

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

迷宮游戲

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

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

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

1、n！問(wèn)題

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

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

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

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

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

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

基本思想是：

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

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

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

基本