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

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

2、指定的案例求解程序與習(xí)題 按要求填寫實(shí)驗(yàn)報(bào)告,教學(xué)要求 了解算法概念、算法特征及算法的描述 建立算法的復(fù)雜性概念 掌握結(jié)構(gòu)化程序設(shè)計(jì)的基本方法 本章重點(diǎn) 應(yīng)用 c 語(yǔ)言描述算法 掌握算法時(shí)間復(fù)雜度分析,算法與程序設(shè)計(jì)概述,1.1 算法及其描述,算法是程序設(shè)計(jì)的基礎(chǔ)，是計(jì)算機(jī)科學(xué)的核心。 1.1.1 算法定義 算法是計(jì)算機(jī)解決問(wèn)題的過(guò)程，是解決某一問(wèn)題的運(yùn)算序列?；蛘哒f(shuō)算法是問(wèn)題求解過(guò)程的運(yùn)算描述。 當(dāng)面臨某一問(wèn)題時(shí)，需要找到用計(jì)算機(jī)解決這個(gè)問(wèn)題的方法與步驟，算法就是解決這個(gè)問(wèn)題的方法與步驟的描述。,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. 算法的基本特征,一個(gè)算法由有限條可完全機(jī)械地執(zhí)行的、有確定結(jié)果的指令組成，具有以下特性： (1) 確定性 (2) 可行性 (3) 有窮性 (4) 算法有零個(gè)或多個(gè)輸入 (5) 算法有一個(gè)或多個(gè)輸出,1.1.2 算法描述,（1）一個(gè)問(wèn)題可以設(shè)計(jì)不同的算法來(lái)求解； 同一個(gè)算法可以采用不同的形式來(lái)表述。 （2）描述算法可以有：自然語(yǔ)言方式、流程圖方式、偽代碼方式、計(jì)算機(jī)語(yǔ)言表示方式與表格方式等。 （3）當(dāng)一個(gè)算法使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述時(shí)，就是程序。 本書采

4、用C語(yǔ)言與自然語(yǔ)言相結(jié)合來(lái)描述算法。,例1-1 求兩個(gè)整數(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)； / 輸入的簡(jiǎn)略表示 r=a%b; while(r!=0) / 實(shí)施輾轉(zhuǎn)相除 a=b; b=r; r=a%b; print(b); / 輸出的簡(jiǎn)略表示,例1-2 由n個(gè)1組成的整數(shù)能被2011整除，求n至少為多大？,(1) 試模擬整數(shù)豎式除法：,可以證明，n是存在的，且不大于2011，因而以上豎式運(yùn)算總會(huì)停止。當(dāng)除運(yùn)算的余數(shù)為“0”

5、時(shí)，數(shù)一數(shù)被除數(shù)中有多少個(gè)“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é)果； 否則，計(jì)算a=c*10+1為下一輪運(yùn)算的被除數(shù)，繼續(xù)試商。每商一位，統(tǒng)計(jì)被除數(shù)中“1”的個(gè)數(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); / 輸出的簡(jiǎn)略表示,1.2 算法的復(fù)雜性分析,算法的復(fù)雜性越高，所需的計(jì)算機(jī)資源越多。 最重要的計(jì)算機(jī)資源是時(shí)間資源與空間資源。 需要計(jì)算機(jī)時(shí)間資源的量稱為時(shí)間復(fù)雜度，需要計(jì)算機(jī)空間資源的量稱為空間復(fù)雜度。 時(shí)間復(fù)雜度與空間復(fù)雜度集中反映算法的效率。,1.2.1 時(shí)間復(fù)雜度,要想充分理解算法并有效地應(yīng)用算法求解實(shí)際案例，關(guān)鍵是對(duì)算法的分析。通常我們可以利用實(shí)驗(yàn)對(duì)比方法、數(shù)學(xué)方法來(lái)分析算法。 實(shí)驗(yàn)對(duì)比分析很簡(jiǎn)單，兩個(gè)算法相互比較求解時(shí)間 。 數(shù)學(xué)方法能在嚴(yán)密的邏輯推理基礎(chǔ)上判斷算法的優(yōu)劣。 在算法分析中，我們往往采用能近似表達(dá)性能的方法來(lái)展示某個(gè)算法的性能

7、指標(biāo)。,一個(gè)算法的時(shí)間復(fù)雜度是指算法運(yùn)行所需的時(shí)間。一個(gè)算法的運(yùn)行時(shí)間取決于算法所需執(zhí)行的語(yǔ)句（運(yùn)算）的多少。算法的時(shí)間復(fù)雜度通常用該算法執(zhí)行的總語(yǔ)句（運(yùn)算）的數(shù)量級(jí)決定。,一條語(yǔ)句的數(shù)量級(jí)即執(zhí)行它的頻數(shù)，一個(gè)算法的數(shù)量級(jí)是指它所有語(yǔ)句執(zhí)行頻數(shù)之和。 在分析算法時(shí)，隱藏細(xì)節(jié)的數(shù)學(xué)表示方法為大寫字母“O”記法，它可以幫助我們簡(jiǎn)化算法復(fù)雜度計(jì)算的許多細(xì)節(jié)，提取主要成分。,算法的執(zhí)行頻數(shù)的數(shù)量級(jí)直接決定算法的時(shí)間復(fù)雜度。,2個(gè)語(yǔ)句各執(zhí)行1次，共執(zhí)行2次。時(shí)間復(fù)雜度為O(1),(1) x=x+1; s=s+x;,例1-3 試計(jì)算下面三個(gè)程序段的時(shí)間復(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個(gè)賦值語(yǔ)句，每個(gè)賦值語(yǔ)句各執(zhí)行n次；共執(zhí)行5n+1次. 時(shí)間復(fù)雜度為O(n).,例1-3 試計(jì)算下面三個(gè)程序段的執(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)的賦值語(yǔ)句“s=s+j”各執(zhí)行頻數(shù)為:總的執(zhí)行頻數(shù)為：,時(shí)間復(fù)雜度符號(hào)O的兩個(gè)定理:,在估算算法的時(shí)間復(fù)雜度時(shí)，為簡(jiǎn)單計(jì)，以后只考慮內(nèi)循環(huán)

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

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

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

12、質(zhì)是程序的機(jī)器，程序是計(jì)算機(jī)的靈魂。,算法是程序的核心。程序是某一算法用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。,1.3.1 算法與程序,程序設(shè)計(jì)反映了利用計(jì)算機(jī)解決問(wèn)題的全過(guò)程，包括: 建立數(shù)學(xué)模型; 數(shù)據(jù)的組織方式;設(shè)計(jì)合適的算法; 編寫程序來(lái)實(shí)現(xiàn)算法;上機(jī)調(diào)試程序，使之運(yùn)行后能產(chǎn)生求解問(wèn)題的結(jié)果。,一個(gè)程序應(yīng)包括對(duì)數(shù)據(jù)的描述與對(duì)運(yùn)算操作的描述兩個(gè)方面的內(nèi)容。 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序,數(shù)據(jù)結(jié)構(gòu)是對(duì)數(shù)據(jù)的描述;算法是對(duì)運(yùn)算操作的描述。,例1-7 編寫程序?qū)崿F(xiàn)求兩個(gè)整數(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è)計(jì),任何簡(jiǎn)單或復(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è)計(jì)的三種基本結(jié)構(gòu)，也是結(jié)構(gòu)化程序設(shè)計(jì)必須采用的結(jié)構(gòu)。,結(jié)構(gòu)化程序設(shè)計(jì)方法是目前國(guó)內(nèi)外普遍采用的一種程序設(shè)計(jì)方法。結(jié)構(gòu)化程序設(shè)計(jì)方法在實(shí)踐中不斷發(fā)展和完善，已成為軟件開發(fā)的重要方法討論。,結(jié)構(gòu)化程序設(shè)計(jì)的基本要點(diǎn):,（1） 自頂向下，逐步求精 （2） 模塊化設(shè)計(jì) （3） 結(jié)構(gòu)化編碼,逐步求精總是和自頂向下結(jié)合使用，將問(wèn)題求解逐步具體化的過(guò)程，一般把逐步求精看作自頂向下設(shè)計(jì)的具體體現(xiàn)。,模塊化是結(jié)構(gòu)化程序設(shè)計(jì)的重要原則。 一個(gè)程序是由一個(gè)主控模塊和若干子模塊組成。 主控模塊用來(lái)完成某些公用操作及功能選擇; 而子模塊用來(lái)完成某項(xiàng)特定的功能。,例1-8 把歐幾里德算法設(shè)計(jì)成子模塊，通過(guò)主模塊調(diào)用實(shí)現(xiàn)求n個(gè)整數(shù)的最大公約數(shù)。,/ 實(shí)現(xiàn)歐幾里德算法的函數(shù),c135 （可加c135在VC+6.0的鏈接）,/ 求n個(gè)整數(shù)的最大公約數(shù),c136 (調(diào)用c135, 可加c136在VC+6.0的鏈接),在設(shè)計(jì)好一個(gè)結(jié)構(gòu)化的算法之后，還需進(jìn)行結(jié)構(gòu)化編碼，將已設(shè)計(jì)好的算法用計(jì)算機(jī)語(yǔ)言來(lái)表示，編寫出能在計(jì)算機(jī)上進(jìn)行編譯與運(yùn)行的程序。 結(jié)構(gòu)化程序設(shè)計(jì)的過(guò)程就是將問(wèn)題求解由抽象逐步具體化的過(guò)程。這種方法符合人們解決復(fù)雜