[計(jì)算機(jī)軟件及應(yīng)用]算法及其描述.ppt_第1頁(yè)
[計(jì)算機(jī)軟件及應(yīng)用]算法及其描述.ppt_第2頁(yè)
[計(jì)算機(jī)軟件及應(yīng)用]算法及其描述.ppt_第3頁(yè)
[計(jì)算機(jī)軟件及應(yīng)用]算法及其描述.ppt_第4頁(yè)
[計(jì)算機(jī)軟件及應(yīng)用]算法及其描述.ppt_第5頁(yè)
免費(fèi)預(yù)覽已結(jié)束,剩余29頁(yè)可下載查看

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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ù)雜

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論