C語(yǔ)言第2章(譚浩強(qiáng)).ppt

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