1、/,第2章、程序的靈魂 算法,/,本章學(xué)習(xí)目標(biāo),理解算法的概念 了解算法的表示方法 掌握流程圖的繪制方法 掌握三種基本結(jié)構(gòu)的流程圖 了解結(jié)構(gòu)化程序設(shè)計(jì)方法,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,算法的引入,問題：計(jì)算矩形的周長 第一步：定義三個(gè)變量存儲長、寬和周長 第二步：提示用戶輸入矩型的長和寬 第三步：計(jì)算周長，兩個(gè)長加上兩個(gè)寬 第四步：打印計(jì)算結(jié)果 算法的定義： 解決問題所使用的一系列合乎邏輯的、簡潔的步驟。,length,width,/,算法與程序關(guān)系,著名科學(xué)家沃思（Niki

2、klaus Wirth）的公式： 數(shù)據(jù)結(jié)構(gòu)算法程序 擴(kuò)充后的公式： 數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計(jì)方法語言和環(huán)境程序 算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對象，語言是工具，程序設(shè)計(jì)方法是使用手段。,/,算法的特性,有窮性 確定性 有效性 有零個(gè)或多個(gè)輸入 有一個(gè)或多個(gè)輸出,/,算法的分析與優(yōu)化,分析程序的算法設(shè)計(jì)，應(yīng)先看主流程圖，再逐步細(xì)化地分析 了解算法是否實(shí)現(xiàn)了任務(wù)需求，方法是否合理 性能上是否存在瓶頸，能否被優(yōu)化 如果有多個(gè)輸入條件，處理時(shí)是否覆蓋了全部輸入條件 如果有多個(gè)輸出結(jié)果，其輸出是否被系統(tǒng)所定義和處理,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種

3、表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,算法的表示方法,案例：判斷20002500年中的每一年是否為閏年。 閏年的條件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份；,/,自然語言,自然語言描述： 設(shè)y為被檢測的年份，則算法可表示如下： S1：2000y； S2：若y不能被4整除，則輸出y“不是閏年”，然后轉(zhuǎn)到S6； S3：若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉(zhuǎn)到S6； S4：若y能被100整除，又能被400整除，輸出y“是閏年” ，然后轉(zhuǎn)到S6； S5：輸出y“不是閏年”，然后轉(zhuǎn)到S6； S6：y+1y； S7：當(dāng)y250

4、0時(shí), 返回S2繼續(xù)執(zhí)行，否則結(jié)束。,/,自然語言,使用自然語言描述算法的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)： 通俗易懂 缺點(diǎn)： 文字冗長 含義不太嚴(yán)格，容易出現(xiàn)歧義,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,傳統(tǒng)流程圖,用一些圖框表示指令或活動(dòng)的各種操作流程 ANSI規(guī)定的常用流程圖符號：,/,三種基本結(jié)構(gòu),順序結(jié)構(gòu) 選擇結(jié)構(gòu),/,三種基本結(jié)構(gòu),循環(huán)結(jié)構(gòu),/,應(yīng)用舉例,優(yōu)點(diǎn)： 比較清晰，可以解決任何復(fù)雜的問題 缺點(diǎn)： 流程圖比較長，基本結(jié)構(gòu)之間的流程線多余,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)

5、流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,N-S流程圖,美國學(xué)者I.Nassi和B.shneiderman提出 流程圖符號：,/,應(yīng)用舉例,優(yōu)點(diǎn)： 直觀易懂 缺點(diǎn)： 畫起來比較麻煩，不易修改,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,偽代碼,BEGIN（算法開始） 2000y while yy END(算法結(jié)束),/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序

6、設(shè)計(jì)方法 文檔和注釋,/,#include void main() int y=2000; while (y=2500) if(y%4)=0) if(y%100!=0) printf( %d 年是閏年n,y); else if(y%400=0) printf( %d 年是閏年n,y); else printf( %d 年是非閏年n,y); else printf( %d 年是非閏年n,y); y=y+1; ,計(jì)算機(jī)語言,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,各種表示方法比較,/,繪制流

7、程圖應(yīng)該注意的事項(xiàng),一個(gè)流程圖只有一個(gè)入口點(diǎn)和一個(gè)出口點(diǎn)； 主要畫出問題的邏輯處理過程，無需將每一步都畫的很詳細(xì)； 如果算法很復(fù)雜，則可以先畫出大的邏輯關(guān)系，再把一些關(guān)鍵處理步驟細(xì)化成的流程圖; 流程圖在跨頁時(shí)，需要在流程線上標(biāo)注出號碼，以便在下一頁找出對應(yīng)關(guān)系; 讓編程人員或讀者能夠容易讀懂流程圖。,/,內(nèi)容進(jìn)度,算法 算法的表示方法 自然語言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 計(jì)算機(jī)語言 各種表示方法的比較 結(jié)構(gòu)化程序設(shè)計(jì)方法 文檔和注釋,/,結(jié)構(gòu)化程序設(shè)計(jì)方法,C語言是結(jié)構(gòu)化程序設(shè)計(jì)方法 優(yōu)點(diǎn)： 程序便于編寫、閱讀、修改、維護(hù) 程序可靠性較好，質(zhì)量較高 主要有兩種： 自頂向下、逐步細(xì)化、模塊化設(shè)計(jì)、結(jié)構(gòu)化編碼 把一個(gè)復(fù)雜問題的求解過程分階段進(jìn)行，每個(gè)階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。例如，建筑樓房。 優(yōu)點(diǎn)：程序結(jié)構(gòu)周全、層次分明、容易設(shè)計(jì)，讀者易理解，且修改方便。 自下而上、逐步積累 先處理細(xì)節(jié)和小的地方，然后再組織起來形成系統(tǒng)。 缺點(diǎn)：很難考慮周全，往往只注意細(xì)節(jié)，而容易忽略全局，不符合一般人的思路。,/,應(yīng)用舉例,