C語言第2章(譚浩強).ppt

1,第2章 程序的靈魂算法,打個比方，廚師做菜肴，需要有菜譜。菜譜上一般應包括：（）配料（數(shù)據(jù)） （）操作步驟（算法） 面對同一些原料可以加工出不同風味的菜肴。 數(shù)據(jù)是操作對象，對操作的描述既是操作步驟，操作的目的是對數(shù)據(jù)進行加工處理得到期望的結果。 本課程雖然不是專門講算法的，但不會算法就達不到我們的目的用語言進行程序設計。,2,著名計算機科學家沃思提出一個公式： 數(shù)據(jù)結構算法程序 實際上，一個程序還應當采用結構化程序設計方法進行程序設計，并且用某一種計算機語言表示。因此，可以這樣表示。 程序算法數(shù)據(jù)結構程序設計方法語言 以上四個方面是一名程序設計員所應具備的知識。在這四個方面中，算法是靈魂，是解決“做什么”和“怎么做”的問題。數(shù)據(jù)結構是加工對象，語言是工具，編程需要采用合適的方法。,3,2.1 算法的概念 做任何事情都有一定的步驟，這些步驟都是有一定的順序。如：起床上學，用電腦畫畫，彈奏樂曲。不要以為只有“計算”的問題才有算法的。 什么叫做算法？廣義：為解決一個問題而采用的方法和步驟就稱為“算法”。 例如：求 1+2+3+4+100 可先算1+2、再加3、再加4直到加上100； 也可采用 100+（1+99）+（2+98）+（49+51）+50 本書所關心的算法只限于計算機算法。,4,計算機算法可分兩大類:（1）數(shù)值運算算法 （2）非數(shù)值運算算法 數(shù)值運算：求數(shù)值解、如求方程根、函數(shù) 定積分等。 非數(shù)值運算：事物管理、圖書檢索、人事 管理、行車調度管理等。 由于數(shù)值運算有現(xiàn)成的模型，可以應用數(shù)值分析方法，算法比較成熟。例如有些計算機系統(tǒng)提供“數(shù)學程序庫”，可以直接調用。 而非數(shù)值運算的種類繁多，不可能羅列所有的算法，需要設計解決特定的問題。目前計算機在非數(shù)值運算方面的應用遠遠超過了在數(shù)值運算方面的應用。,5,2.2 簡單算法舉例 例2.1 求1*2*3*4*5 設兩個量：一個被乘數(shù)p 一個乘數(shù)n S1：p=1 /* S1 是步驟一*/ S2：n=2 S3：p*n=p S4：n+1=n S5：若n不大于5，重復執(zhí)行S3、S4、S5 （若求1*3*5*7*9*11 呢？）,6,例2.2 有50個學生，將成績在80分以上的學號和成績打印出來。 說明：n:學號，ni:第i個學生學號，g:成績， gi:第i個學生成績 步驟如下： S1：1=i S2：若gi80,則輸出ni和 gi ，否則不輸出。 S3：i+1=i S4：若i小于等于50,則返回 S2繼續(xù)執(zhí)行； 否則算法結束。,7,例2.3判定2000-2005年中的每一年是否閏年，將結果輸出。 說明：閏年的條件（1）能被4整除，但不能被100整除的都是閏年（2）能被100整除，又能被400整除的是閏年。 y:年份 步驟如下： S1：y=2000 S2：若y不能被4整除，則輸出y“不是閏年”。轉到s6 S3：若y能被4整除，不能被100整除，則輸出y“是閏年”。轉到s6 S4：若y能被100整除，又能被400整除，輸出y“是閏年”。轉到s6 S5：輸出y“不是閏年”。 S6： y= y+1 S7:當y=2500,轉s2繼續(xù)執(zhí)行，否則算法結束。,8,例2.4求1-1/2+1/3-1/4+1/99-1/100 說明：sum:累加項；deno:分母；sign:符號；term:某一項 步驟如下： S1:sign=1 S2:sum=1 S3:deno=2 S4:sign=(-1)*sign S5:term=sign*(1/deno) S6:sum=sum+term S7:deno=deno+1 S8:若deno=100返回s4；否則算法結束。,9,2.3 算法的特性 一個算法具有以下特性： 有窮性 包含有限的操作步驟，不能是無限的；在合理 的范圍之內。如：例2.4 條件改為deno0 確定性 每一步驟是確定的，而不應是含糊的，模棱兩 可的。 有零個或多個輸入 輸入是從外界取得必要的信息。 有一個或多個輸出 “解”就是輸出，沒有輸出的算法是無意義的。 有效性 每一步驟都應是有效的執(zhí)行，并有確定的結果。,10, 2.4 怎樣表示一個算法 表示方法： 1、自然語言 2、傳統(tǒng)流程圖 3、NS流程圖 4、結構化流程圖 5、偽代碼 、PAD圖,11,2.4.1 用自然語言表示算法 用自然語言表示通俗易懂，但容易出現(xiàn) “歧異性”。 2.4.2 用傳統(tǒng)流程圖表示算法 直觀形象，易于理解。成為世界各國程序 工作者普遍采用。 下面給出傳統(tǒng)流程圖的說明：,12,起止框,輸入/輸出框,處理框,有一個入口 一個出口,判斷框,有一個入口，兩個出口,13,流程線,注釋框,連接點,14,例2.6 求5！的算法用流程圖表示,15,例2.7 將50名學生中成績在80分以上的學號和成績輸出,16,例2.8 判斷20002500年中的每一年是否為閏年。 是閏年的條件： 1.能被整除，但不能被整100除。 2.能被100整除又能被400整除。,17,例 .9 求 1-1/2+1/3-1/4+1/99-1/100 sign符號 sum 累加和 deno分母 term項 deno100 算法結束,18,例.10 對一個大于或等于的正整數(shù)，判斷它是否為素數(shù)。 所謂素數(shù)，是指除了被和該數(shù)本身之外，不能再被其他整數(shù)整除的數(shù)。,19,2.4. 三種基本結構和改進的流程圖 1.傳統(tǒng)流程圖的弊端 傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線可以隨意地轉來轉去，無規(guī)律。如下圖，稱為BS型。,20,2.三種基本結構：1966年提出,（1）順序結構: 平鋪直敘的向下順序執(zhí)行,即執(zhí)行A操作后,執(zhí)行B操作。,（2）選擇結構: 或稱選取、分支結構，根據(jù)給定條件決定執(zhí)行A操作和執(zhí)行B操作。,21,（3）循環(huán)結構: 又稱重復結構，即反復執(zhí)行某一部分的操作。 有兩類循環(huán)結構： A:當型循環(huán)(while) B：直到型循環(huán)（until）,22,舉例：輸出5個數(shù)：1，2，3，4，5,23,結論：,3種基本結構的共同特點： （1）只有一個入口；如上圖的a點 （2）只有一個出口；如上圖的b點。區(qū)分：判斷框和選擇結構的出口 （3）結構內的每一部分都有機會執(zhí)行到；對每一個框都有一個入口和出口 如P26圖2-20 （4）結構內不存在死循環(huán)。如P26圖2-21 已經(jīng)證明，以上三種基本結構順序組成的算法，可以解決任何復雜的問題。 基本結構并不僅限于這三種，只要符合這4個條件都可以作為基本結構。如P26圖2-22圖2-23,24,2.4. 用NS流程圖表示算法 既然用基本結構的順序組合可以表示任何復雜的算法，那么基本結構的流程線就屬多余了。所以 1973年由美國學者提出了一種新的流程圖形式，在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內，這種流程圖稱為 NS 流程圖。 （Nassi 和 Shneiderman 兩位美國學者英文姓名的第一個字母）,25,請觀看以下流程符號,順序結構 循環(huán)結構（當型） A 當 Pi 成立 B A 選擇結構 循環(huán)結構（直到型） P A 成立 不成立 A B 直到 Pi 成立,26,解方程： ax2+bx+c=0,27,求 請轉換成直到型？,28,例2.12 將50名學生中成績高于80分的學號和成績輸出,29,例2.12 將50名學生中成績高于80分的學號和成績輸出（增加了輸入）,30,例2.13 判斷閏年,31,例2.14 求1-1/2+1/3-1/4+1/99-1/100,32,例：輸入三個數(shù)比較大小，輸出最大值,33,練習：用N-S圖表示算法,要求：輸入一個數(shù),求的值 有方程組y=1(x0) y=-1(x0) y=0(x=0),34,35,例：2.15 用N-S圖表示判別素數(shù)的算法，結果P29圖2-35,36,結論：,一個結構化的算法是由一些基本結構順序組成的； 在基本結構之間不存在向前或向后的跳轉，流程的轉移只存在于一個基本結構內； 一個非結構化的算法可以用一個等價的結構化算法代替； 如果一個算法不能分解成若干個基本結構，則它必然不是一個結構化的算法。,37,2.4. 用偽代碼表示算法,偽代碼是介于自然語言和計算機語言之間的文字和符號來描述算法。它不用圖形符號，書寫方便、格式緊湊、也比較好懂，便于向計算機語言算法（即程序）過度。 例如：若 為正 為正 打印 否則 打印 ,38,偽代碼書寫格式比較自由，可以隨手寫下容易表達出設計者的思想。同時，用偽代碼寫的算法很容易修改，如加一行、刪除一行等，而這卻是用流程圖表示算法時所不便處理的。 但是，用偽代碼不容易寫出結構化的算法。例如上面幾個例子都是結構化的算法。要用偽代碼寫算法就不如流程圖直觀，可能會出現(xiàn)邏輯上的錯誤（例如循環(huán)或選擇結構的范圍搞錯等）。 以上介紹的表示算法的幾種方法，在程序設計中可根據(jù)需要和習慣選用?？紤]到國內初學者的情況，本課程采用流程圖表示算法。,39,2.4. 用計算機語言表示算法,要完成一項工程，包括設計算法和實現(xiàn)算法兩個部分。一個菜譜是一個算法，廚師炒菜就是在實現(xiàn)這個算法。設計算法的目的是為了實現(xiàn)算法。因此，不僅要考慮如何設計一個算法，也要考慮如何實現(xiàn)一個算法。 以上我們只是描述算法，即用不同的形式表示操作的步驟。而要得到運算結果，就必須實現(xiàn)算法。 我們實現(xiàn)算法的任務是用計算機解題，也就是用計算機實現(xiàn)算法。計算機是無法識別流程圖和偽代碼的，只有用計算機語言編寫的程序才能被計算機執(zhí)行（通過編譯）。,40,2.5 結構化程序設計方法,前面介紹了順序結構、選擇結構、循環(huán)結構這三種基本結構。一個結構化程序就是用高級語言表示結構化算法。用三種基本結構組成的程序必然是結構化的程序，這種程序便于編寫、閱讀、