算法設(shè)計基礎(chǔ)課件

算法設(shè)計與分析

授課教師：劉志中

lzzmff@126.comQQ:120511193TEL法設(shè)計與分析授課教師：劉志中第一章算法設(shè)計基礎(chǔ)1234算法的基本概念為什么學(xué)習(xí)和研究算法重要的問題類型小結(jié)第一章算法設(shè)計基礎(chǔ)1234算法的基本概念為什么學(xué)習(xí)和研究算１算法及其特性算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法的特性4確定性2輸出3有窮性1輸入5可行性１算法及其特性算法是對特定問題求解步驟的一種描述，是指令１算法及其特性1輸入這些輸入通常取自于某個特定的對象的集合零個或多個輸入１算法及其特性1輸入這些輸入通常取自于某個特定的對象１算法及其特性2輸出通常輸入與輸出之間有著某種特定的關(guān)系有一個或多個輸出１算法及其特性2輸出通常輸入與輸出之間有著某種特定的１算法及其特性3有窮性必須總是在執(zhí)行又窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成１算法及其特性3有窮性必須總是在執(zhí)行又窮步之后結(jié)束，１算法及其特性4確定性算法中每一條指令必須有確切的含義，不存在二義性；在任何情況下，對于相同的輸入只能得到相同的輸出；１算法及其特性4確定性算法中每一條指令必須有確切的含１算法及其特性5可行性可以通過程序?qū)崿F(xiàn)操作；１算法及其特性5可行性可以通過程序?qū)崿F(xiàn)操作；Problem—

問題規(guī)定了輸入與輸出之間的關(guān)系，可以用通用語言來描述；InstanceofaProblem—

問題實例某一個問題實例包含了求解該問題所需輸入；輸入:由n個數(shù)組成的一個序列<a1,a2,,an>輸出:對輸入系列的一個排列(重排）<a1’,a2’,,an’>，使得<a1’a2’

an’>排序問題的一個實例Input:<31,41,59,26,41,58>——Output:<26,31,41,41,58,59>算法概念理解:問題及問題實例Problem—問題輸入:由n個數(shù)組成的一個序列<a1算法的其他特性4抽象分級2健壯性3可理解性1正確性5高效性算法的其他特性4抽象分級2健壯性3可理解性1正確性5高效性算法的其他特性1正確性對于任意合法的輸入，算法都會得到正確的結(jié)果；算法的其他特性1正確性對于任意合法的輸入，算法都會得到正確的算法的其他特性2健壯性算法對非法輸入的抵抗能力；對錯誤的輸入，算法應(yīng)能識別并作出處理；而不產(chǎn)生錯誤的動作或陷入癱瘓；危害：美國電話電報公司算法的其他特性2健壯性算法對非法輸入的抵抗能力；對錯誤的輸入算法的其他特性3可理解性容易理解與實現(xiàn)；易于被人理解，易于轉(zhuǎn)換成程序；算法的其他特性3可理解性容易理解與實現(xiàn)；易于被人理解，易于轉(zhuǎn)算法的其他特性4抽象分級對某些具體的細(xì)節(jié)進(jìn)行抽象；不過細(xì)地描述細(xì)節(jié)；算法步驟太多，會增加算法的理解難度；算法的其他特性4抽象分級對某些具體的細(xì)節(jié)進(jìn)行抽象；不過細(xì)地描算法的其他特性5高效性時間效率與空間效率；時間效率---求解速度；空間效率---額外的存儲空間；理想目標(biāo)：較短的執(zhí)行時間、較少的輔助空間；算法的其他特性5高效性時間效率與空間效率；時間效率---求解

算法的描述方法4程序設(shè)計語言2程序流程圖3偽代碼1自然語言算法的描述方法4程序設(shè)計語言2程序流程圖3偽代碼1自然語

算法的描述方法1自然語言

優(yōu)點：容易書寫、容易理解

缺點:(1)歧義性，二義性，不滿足確定性；(2)自然語言不夠簡練，導(dǎo)致算法描述過長；(3)抽象級別高，不易轉(zhuǎn)換成計算機程序算法的描述方法1自然語言優(yōu)點：容易書寫、容易理解

算法的描述方法2程序流程圖

優(yōu)點：直觀易懂、能夠隨意表示控制流程；

缺點:(1)嚴(yán)密性不如程序設(shè)計語言；(2)靈活性不如自然語言；算法的描述方法2程序流程圖優(yōu)點：直觀易懂、能夠隨意

算法的描述方法3偽代碼

偽代碼是介于自然語言和程序設(shè)計語言之間的方法；它采用某一程序設(shè)計語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計。

偽代碼不是一種實際的編程語言，但在表達(dá)能力上類似于編程語言，同時極小化描述算法不必要的細(xì)節(jié)，是比較合適的算法描述語言，被稱為“算法語言”或“第一語言”。算法的描述方法3偽代碼偽代碼是介于自然語言和程序設(shè)

算法設(shè)計的一般過程1理解問題

求解目標(biāo)、已知信息、

顯示條件、隱含條件

輸入什么、輸出什么、結(jié)果的呈現(xiàn)

全面準(zhǔn)確地理解、分析問題，能夠事半功倍算法設(shè)計的一般過程1理解問題求解目標(biāo)、已知信息、

算法設(shè)計的一般過程2選擇算法設(shè)計技術(shù)

算法設(shè)計策略；

本課程所講解的方法可以用于解決不同領(lǐng)域的不同問題；

蠻力法、分治法、減治法、動態(tài)規(guī)劃、回溯等

基于這些基本的算法與技術(shù)，設(shè)計出高效、智能的好算法！算法設(shè)計的一般過程2選擇算法設(shè)計技術(shù)算法設(shè)計策略；

算法設(shè)計的一般過程3設(shè)計并描述算法

清楚地描述算法的步驟；

描述方法：自然語言、流程圖、偽代碼

本課程：C++與自然語言---偽代碼算法設(shè)計的一般過程3設(shè)計并描述算法清楚地描述算法的

算法設(shè)計的一般過程4手工運行算法

計算機比較傻；比較機械，吩咐干啥就干啥

發(fā)現(xiàn)不了算法中的邏輯錯誤；

解決方法：手工運行算法；帶入一個具體的事例，按照算法流程走一遍；

實例的選擇：盡可能地覆蓋多個方面；考慮問題的特殊性；算法設(shè)計的一般過程4手工運行算法計算機比較傻；比較

算法設(shè)計的一般過程5分析算法的效率

時間效率與空間效率；

更關(guān)注的是時間效率；

算法性能比較：時間短、效果好！算法設(shè)計的一般過程5分析算法的效率時間效率與空間效

算法設(shè)計的一般過程6實現(xiàn)算法

計算機不能直接執(zhí)行偽代碼；

算法是需要不斷完善和改進(jìn)的；算法設(shè)計的一般過程6實現(xiàn)算法計算機不能直接執(zhí)行偽代

算法設(shè)計的一般過程待求解的問題分析問題選擇算法設(shè)計技術(shù)設(shè)計并描述算法分析算法的效率手工運行算法根據(jù)算法編寫代碼不滿意滿意算法設(shè)計的一般過程待求解的問題分析問題選擇算法設(shè)計技術(shù)

算法設(shè)計實例1.2例1.2求兩個自然數(shù)的最大公約數(shù)求解思路：用短除法找出兩個自然數(shù)的所有公因子，將這些公因子相乘，結(jié)果就是這兩個數(shù)的最大公約數(shù)。算法設(shè)計實例1.2例1.2求兩個自然數(shù)的最大公約數(shù)求解

算法設(shè)計實例1.2算法1.CommFactor1輸入：兩個自然數(shù)m和n輸出：m和n的最大公約數(shù)factor=1;循環(huán)變量i從2~min(m,n),執(zhí)行以下操作；

2.1如果i是m和n的公因子，則執(zhí)行下述操作；

2.1.1factor=factor*i;2.1.2m=m/i;n=n/i;2.2如果i不是m和n的公因子，則i=i+1；3.輸出factor；算法設(shè)計實例1.2算法1.CommFactor1輸入

算法設(shè)計實例1.2算法1.編程實現(xiàn)intCommFactor1(intm,intn){inti,factor=1;for(inti=2;i<=m&&i<=n;i++){while(m%i==0&&n%n==0){factor=factor*i;m=m/i;n=n/i;}}returnfactor;}算法設(shè)計實例1.2算法1.編程實現(xiàn)intCommF2為什么要學(xué)習(xí)和研究算法2為什么要學(xué)習(xí)和研究算法2

算法訓(xùn)練能夠提高計算思維能力計算機不夠智能，不能主動地分析問題解決問題；需要人的智慧分析問題，形式化地描述問題；采用抽象思維和邏輯思維設(shè)計問題解決方案；采用抽象思維和邏輯思維設(shè)計問題解決方案；2算法訓(xùn)練能夠提高計算思維能力計算機不夠智能，不能主動地分2

算法訓(xùn)練能夠提高計算思維能力美國計算機協(xié)會與美國電氣與電子工程師協(xié)會（ACM/IEEE-CS）認(rèn)為計算機專業(yè)的基本能力包括：計算思維能力、算法設(shè)計與分析能力、程序設(shè)計與實現(xiàn)能力、系統(tǒng)能力；計算機求解問題的過程中，最重要的環(huán)節(jié)就是將人的想法抽象為算法；算法訓(xùn)練像一種思維體操，能夠鍛煉我們的思維，使思維變得清晰、更有邏輯；2算法訓(xùn)練能夠提高計算思維能力美國計算機協(xié)會與美國電氣與電2

算法研究是推動計算機技術(shù)發(fā)展的關(guān)鍵檢索技術(shù)壓縮與解壓縮信息安全與數(shù)據(jù)加密2算法研究是推動計算機技術(shù)發(fā)展的關(guān)鍵檢索技術(shù)壓縮與解壓縮信思考如下問題案例一——查找問題思考如下問題案例一——查找問題231333231788131723233313233323178132333231781323233317813172323338案例二——排序問題231333231788131723233313233323voidinsertSort(intr[],intn){ for(i=2;i<=n;i++){r[0]=r[i]; j=i-1; for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j]; j=j-1; } r[j+1]=r[0]; }}案例二——排序問題voidinsertSort(intr[],i案例三——圖問題案例三——圖問題案例四——組合問題最小乘車費用假設(shè)12345678910費用122131404958697990101而任意一輛汽車從不行駛超過10公里。某人想行駛n公里，假設(shè)他可以任意次換車，請你幫他找到一種乘車方案，使得總費用最小。案例四——組合問題最小乘車費用案例五——幾何問題怎么修圍墻滿足利用最大化？案例五——幾何問題怎么修圍墻滿足利用最大