[計算機(jī)軟件及應(yīng)用]算法及其描述.ppt

1、計算機(jī)常用算法與程序設(shè)計案例教程,楊克昌,請用PowerPoint 2003播放,課堂講授 ：,學(xué)時安排：36（講授）18（上機(jī)） ( 可根據(jù)實(shí)際教學(xué)計劃進(jìn)行調(diào)整),各常用算法的概念與設(shè)計要點(diǎn)。 重點(diǎn)講授應(yīng)用算法設(shè)計求解基本的典型案例，并通過相關(guān)程序，引導(dǎo)設(shè)計變通。 在基本案例引導(dǎo)下自學(xué)相關(guān)聯(lián)案例求解。 小組討論與基本案例相關(guān)的拓展與引申案例求解，為“課程設(shè)計”作準(zhǔn)備。,上機(jī)實(shí)踐：,學(xué)習(xí)建議：,學(xué)會歸納、總結(jié)和提煉；,自覺調(diào)整學(xué)習(xí)狀態(tài)：,培養(yǎng)案例求解興趣 自覺完成布置的作業(yè) 加深對算法應(yīng)用的理解 善于變通、拓展與改進(jìn),注重算法設(shè)計，提高解決實(shí)際案例的能力。,上機(jī)環(huán)境：VC+6.0 上機(jī)通過每章

2、指定的案例求解程序與習(xí)題 按要求填寫實(shí)驗報告,教學(xué)要求 了解算法概念、算法特征及算法的描述 建立算法的復(fù)雜性概念 掌握結(jié)構(gòu)化程序設(shè)計的基本方法 本章重點(diǎn) 應(yīng)用 c 語言描述算法 掌握算法時間復(fù)雜度分析,算法與程序設(shè)計概述,1.1 算法及其描述,算法是程序設(shè)計的基礎(chǔ)，是計算機(jī)科學(xué)的核心。 1.1.1 算法定義 算法是計算機(jī)解決問題的過程，是解決某一問題的運(yùn)算序列?；蛘哒f算法是問題求解過程的運(yùn)算描述。 當(dāng)面臨某一問題時，需要找到用計算機(jī)解決這個問題的方法與步驟，算法就是解決這個問題的方法與步驟的描述。,1. 算法的三要素,算法由操作、控制結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)三者組成。 (1) 操作：算術(shù)運(yùn)算，關(guān)系運(yùn)算，

3、邏輯運(yùn)算；輸入、輸出、賦值等操作。 (2) 控制結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)，模塊調(diào)用。 (3) 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)之間的邏輯關(guān)系。,2. 算法的基本特征,一個算法由有限條可完全機(jī)械地執(zhí)行的、有確定結(jié)果的指令組成，具有以下特性： (1) 確定性 (2) 可行性 (3) 有窮性 (4) 算法有零個或多個輸入 (5) 算法有一個或多個輸出,1.1.2 算法描述,（1）一個問題可以設(shè)計不同的算法來求解； 同一個算法可以采用不同的形式來表述。 （2）描述算法可以有：自然語言方式、流程圖方式、偽代碼方式、計算機(jī)語言表示方式與表格方式等。 （3）當(dāng)一個算法使用計算機(jī)程序設(shè)計語言描述時，就是程序。 本書采

4、用C語言與自然語言相結(jié)合來描述算法。,例1-1 求兩個整數(shù)a,b的最大公約數(shù)的歐幾里德算法,(1) 數(shù) a 除以 b 得余數(shù) r；若r=0，則b為所求的最大公約數(shù)。 (2) 若 r0，以b為a，r為b，繼續(xù)(1). 歐幾里德算法具體描述如下： input(a,b)； / 輸入的簡略表示 r=a%b; while(r!=0) / 實(shí)施輾轉(zhuǎn)相除 a=b; b=r; r=a%b; print(b); / 輸出的簡略表示,例1-2 由n個1組成的整數(shù)能被2011整除，求n至少為多大？,(1) 試模擬整數(shù)豎式除法：,可以證明，n是存在的，且不大于2011，因而以上豎式運(yùn)算總會停止。當(dāng)除運(yùn)算的余數(shù)為“0”

5、時，數(shù)一數(shù)被除數(shù)中有多少個“1”即可。 設(shè)整數(shù)豎式除法每次試商的被除數(shù)為a, 除數(shù)為2011，每次試商的余數(shù)為c。 循環(huán)以余數(shù)c0作為循環(huán)條件。循環(huán)外賦初值：c=1111，n=4或c=111，n=3等等。 設(shè)置豎式除法模擬循環(huán)，循環(huán)中被除數(shù)a=c*10+1，試商余數(shù)c=a%2011。 若余數(shù)c=0，結(jié)束循環(huán)，輸出結(jié)果； 否則，計算a=c*10+1為下一輪運(yùn)算的被除數(shù)，繼續(xù)試商。每商一位，統(tǒng)計被除數(shù)中“1”的個數(shù)的變量n增1。,(2) 豎式除法模擬描述,c=1111;n=4; / 變量c與n賦初值 while(c!=0) / 模擬豎式除法 a=c*10+1; c=a%2011; n=n+1; /

6、 每試商一位n增1 print(n); / 輸出的簡略表示,1.2 算法的復(fù)雜性分析,算法的復(fù)雜性越高，所需的計算機(jī)資源越多。 最重要的計算機(jī)資源是時間資源與空間資源。 需要計算機(jī)時間資源的量稱為時間復(fù)雜度，需要計算機(jī)空間資源的量稱為空間復(fù)雜度。 時間復(fù)雜度與空間復(fù)雜度集中反映算法的效率。,1.2.1 時間復(fù)雜度,要想充分理解算法并有效地應(yīng)用算法求解實(shí)際案例，關(guān)鍵是對算法的分析。通常我們可以利用實(shí)驗對比方法、數(shù)學(xué)方法來分析算法。 實(shí)驗對比分析很簡單，兩個算法相互比較求解時間 。 數(shù)學(xué)方法能在嚴(yán)密的邏輯推理基礎(chǔ)上判斷算法的優(yōu)劣。 在算法分析中，我們往往采用能近似表達(dá)性能的方法來展示某個算法的性能

7、指標(biāo)。,一個算法的時間復(fù)雜度是指算法運(yùn)行所需的時間。一個算法的運(yùn)行時間取決于算法所需執(zhí)行的語句（運(yùn)算）的多少。算法的時間復(fù)雜度通常用該算法執(zhí)行的總語句（運(yùn)算）的數(shù)量級決定。,一條語句的數(shù)量級即執(zhí)行它的頻數(shù)，一個算法的數(shù)量級是指它所有語句執(zhí)行頻數(shù)之和。 在分析算法時，隱藏細(xì)節(jié)的數(shù)學(xué)表示方法為大寫字母“O”記法，它可以幫助我們簡化算法復(fù)雜度計算的許多細(xì)節(jié)，提取主要成分。,算法的執(zhí)行頻數(shù)的數(shù)量級直接決定算法的時間復(fù)雜度。,2個語句各執(zhí)行1次，共執(zhí)行2次。時間復(fù)雜度為O(1),(1) x=x+1; s=s+x;,例1-3 試計算下面三個程序段的時間復(fù)雜度,(2) for(k=1;k=n;k+) x=x

8、+y; y=x+y; s=x+y; ,“k=1”執(zhí)行1次；“k=n”與“k+”各執(zhí)行n次；3個賦值語句，每個賦值語句各執(zhí)行n次；共執(zhí)行5n+1次. 時間復(fù)雜度為O(n).,例1-3 試計算下面三個程序段的執(zhí)行頻數(shù),(3) for(t=1,k=1;k=n;k+) t=t*2; for(j=1;j=t;j+) s=s+j; ,“t=1”與“k=1”各執(zhí)行1次；“k=n”與“k+”各執(zhí)行n次；“t=t*2”執(zhí)行n次；“j=1”執(zhí)行n次；“j=t”、“j+”與內(nèi)循環(huán)的賦值語句“s=s+j”各執(zhí)行頻數(shù)為:總的執(zhí)行頻數(shù)為：,時間復(fù)雜度符號O的兩個定理:,在估算算法的時間復(fù)雜度時，為簡單計，以后只考慮內(nèi)循環(huán)

9、語句的執(zhí)行頻數(shù)，而不細(xì)致計算各循環(huán)設(shè)計語句及其它語句的執(zhí)行次數(shù)，這樣簡化處理不影響算法的時間復(fù)雜度。,例1-4 估算以下程序段所代表算法的時間復(fù)雜度。 for(k=1;k=n;k+) for(j=1;j=k;j+) x=k+j; s=s+x;,每個賦值語句執(zhí)行頻率為n(n+1)/2, 該算法的時間復(fù)雜度為:O(n2),一個算法的運(yùn)行時間，與問題的規(guī)模相關(guān)，也與輸入的數(shù)據(jù)相關(guān)。,例如對給定的n個整數(shù)a(1),a(2),a(n) 排序： for(i=1;iaj) h=ai;ai=aj;aj=h;,3個賦值語句的執(zhí)行頻數(shù)之和，最理想的情形下為零（當(dāng)所有n個整數(shù)已從小到大排列時），最壞情形下為3n(n

10、1)/2（當(dāng)n個整數(shù)為從大到小排列時）。 按平均情形來分析，其時間復(fù)雜度為O(n2)。,對于一個實(shí)用算法，我們通常不必深入研究它時間復(fù)雜度的上界和下界，只需要了解該算法的特性，然后在合適的時候應(yīng)用它。,為了求解某一問題，設(shè)計出復(fù)雜性盡可能低的算法是追求的重要目標(biāo)?；蛘哒f，求解某一問題有多種算法時，選擇其中復(fù)雜性最低的算法是選用算法的重要準(zhǔn)則。,對算法的改進(jìn)與優(yōu)化，主要表現(xiàn)在有效縮減算法的運(yùn)行時間與所占空間。,1.2.2 空間復(fù)雜度,一個程序運(yùn)行所需的存儲空間通常包括固定空間需求與可變空間需求兩部分。 固定空間需求包括程序代碼、常量與靜態(tài)變量等所占的空間。 可變空間需求包括局部作用域非靜態(tài)變量所

11、占用的空間、從堆空間中動態(tài)分配的空間與調(diào)用函數(shù)所需的系統(tǒng)?？臻g等。,算法的空間復(fù)雜度是指算法運(yùn)行的存儲空間，是實(shí)現(xiàn)算法所需的內(nèi)存空間的大小。,二維或三維數(shù)組是空間復(fù)雜度高的主要因素之一。在算法設(shè)計時，為降低空間復(fù)雜度，要注意盡可能少用高維數(shù)組。,從應(yīng)用的角度看，因空間所限影響算法運(yùn)行的情形較為少見。因而在設(shè)計算法時，應(yīng)把降低算法的時間復(fù)雜度作為首要的考慮因素。,在論述某一算法時，如果其空間復(fù)雜度不高，不至于因所占有的內(nèi)存空間而影響算法實(shí)現(xiàn)時，通常不涉及對該算法的空間復(fù)雜度的討論。,1.3 算法與程序設(shè)計,計算機(jī)的一切操作都是由程序控制的，離開了程序，計算機(jī)將一事無成。從這個意義來說，計算機(jī)的本

12、質(zhì)是程序的機(jī)器，程序是計算機(jī)的靈魂。,算法是程序的核心。程序是某一算法用計算機(jī)程序設(shè)計語言的具體實(shí)現(xiàn)。,1.3.1 算法與程序,程序設(shè)計反映了利用計算機(jī)解決問題的全過程，包括: 建立數(shù)學(xué)模型; 數(shù)據(jù)的組織方式;設(shè)計合適的算法; 編寫程序來實(shí)現(xiàn)算法;上機(jī)調(diào)試程序，使之運(yùn)行后能產(chǎn)生求解問題的結(jié)果。,一個程序應(yīng)包括對數(shù)據(jù)的描述與對運(yùn)算操作的描述兩個方面的內(nèi)容。 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序,數(shù)據(jù)結(jié)構(gòu)是對數(shù)據(jù)的描述;算法是對運(yùn)算操作的描述。,例1-7 編寫程序?qū)崿F(xiàn)求兩個整數(shù)a,b(ab)的最大公約數(shù)(a,b)的歐幾里德算法,#include void main() long a,b,c,r; scan

13、f(%ld,%ld, / 輸出求解結(jié)果 ,1.3.2 結(jié)構(gòu)化程序設(shè)計,任何簡單或復(fù)雜的算法都可以由順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)組合而成。所以，順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)被稱為程序設(shè)計的三種基本結(jié)構(gòu)，也是結(jié)構(gòu)化程序設(shè)計必須采用的結(jié)構(gòu)。,結(jié)構(gòu)化程序設(shè)計方法是目前國內(nèi)外普遍采用的一種程序設(shè)計方法。結(jié)構(gòu)化程序設(shè)計方法在實(shí)踐中不斷發(fā)展和完善，已成為軟件開發(fā)的重要方法討論。,結(jié)構(gòu)化程序設(shè)計的基本要點(diǎn):,（1） 自頂向下，逐步求精 （2） 模塊化設(shè)計 （3） 結(jié)構(gòu)化編碼,逐步求精總是和自頂向下結(jié)合使用，將問題求解逐步具體化的過程，一般把逐步求精看作自頂向下設(shè)計的具體體現(xiàn)。,模塊化是結(jié)構(gòu)化程序設(shè)計的重要原則。 一個程序是由一個主控模塊和若干子模塊組成。 主控模塊用來完成某些公用操作及功能選擇; 而子模塊用來完成某項特定的功能。,例1-8 把歐幾里德算法設(shè)計成子模塊，通過主模塊調(diào)用實(shí)現(xiàn)求n個整數(shù)的最大公約數(shù)。,/ 實(shí)現(xiàn)歐幾里德算法的函數(shù),c135 （可加c135在VC+6.0的鏈接）,/ 求n個整數(shù)的最大公約數(shù),c136 (調(diào)用c135, 可加c136在VC+6.0的鏈接),在設(shè)計好一個結(jié)構(gòu)化的算法之后，還需進(jìn)行結(jié)構(gòu)化編碼，將已設(shè)計好的算法用計算機(jī)語言來表示，編寫出能在計算機(jī)上進(jìn)行編譯與運(yùn)行的程序。 結(jié)構(gòu)化程序設(shè)計的過程就是將問題求解由抽象逐步具體化的過程。這種方法符合人們解決復(fù)雜