C語言課件第2章New1.ppt

2.1 算法的概念 2.2 簡單算法舉例 2.3 算法的特性 2.4 怎樣表示一個(gè)算法 2.5 結(jié)構(gòu)化程序設(shè)計(jì)方法 ,第2章 程序的靈魂算法,程 序 包 括 對數(shù)據(jù)的描述 指定數(shù)據(jù)的類型、組織形式，即數(shù)據(jù)結(jié)構(gòu)。 對操作的描述 即操作步驟，也稱算法(algorithm)。 著名計(jì)算機(jī)科學(xué)家沃思(Nikilaus Wirth)提出：,程 序 設(shè) 計(jì) 包 括 采用某種程序設(shè)計(jì)方法 使用某種計(jì)算機(jī)語言工具,程序設(shè)計(jì)人員所應(yīng)具備和綜合運(yùn)用的知識,算法,加工對象,設(shè)計(jì)方法,設(shè)計(jì)工具,為解決問題而采取的方法和步驟，稱為“算法”。 盡量采用簡單、有效的算法。,保證算法正確 考慮算法的質(zhì)量,本書所考慮的只限于計(jì)算機(jī)能執(zhí)行的算法。,算 法 必 備 條 件：,2.1 算 法 的 概 念,計(jì)算機(jī)算法分兩類： 數(shù)值算法（目的是求數(shù)值解） 有比較成熟的算法可供選用。 常常把這些算法匯編成冊(寫成程序形式)，或者將這些程序存放在磁盤或磁帶上，供用戶調(diào)用。,非數(shù)值算法（常用于事務(wù)管理領(lǐng)域）,涵蓋面很廣：計(jì)算機(jī)在非數(shù)值運(yùn)算方面的應(yīng)用遠(yuǎn)多于在數(shù)值運(yùn)算方面的應(yīng)用。難以規(guī)范化，只能對一些典型的算法作比較深入的研究。,2.1 算 法 的 概 念,算 法 一： 步驟1： 先求12，得到2。 步驟2： 將得到的2再乘以3，得到6。 步驟3： 將6再乘以4，得到24。 步驟4： 將24再乘以5，得到120。 算法雖然正確，但太繁瑣。 每次都直接使用上一步驟的數(shù)值結(jié)果，不方便。應(yīng)找到 一種通用的表示方法。,例2.1 求12345。,2.2 簡單算法舉例,設(shè)兩個(gè)變量：變量p代表被乘數(shù)，變量i代表乘數(shù)。 將每一步的乘積放在被乘數(shù)變量p中，算法改寫如下： S1： 使p=1 S2： 使i=2 S3： 使pi，乘積放在p中（pi=p） S4： 使i的值加1（i+1 = i） S5： 若i不大于5，重新執(zhí)行S3、S4和S5； 否則，算法結(jié)束。,算 法 二 ：,計(jì)算機(jī)的優(yōu)勢 在此得以體現(xiàn),2.2 簡單算法舉例,如果題目改為： 求1357999。 則算法二只需作很少改動(dòng)： S1： 1=p S2： 3=i S3： pi=p S4： i+2=i S5： 若i100，返回S3； 否則，結(jié)束。,可見，算法二具有通用性、靈活性，更為簡單有效。,2.2 簡單算法舉例,例2.3 判定20002500年中的每一年是否閏年，將結(jié)果輸出。 閏 年 的 條 件 ： 能被4整除，但不能被100整除的年份是閏年， 如1996年，2004年； 能被100整除，又能被400整除的年份是閏年， 如1600年、2000年。 不符合這兩個(gè)條件的年份不是閏年。,2.2 簡單算法舉例,設(shè) y 為被檢測的年份，算法如下： S1：2000=y 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+1=y S7：當(dāng)y2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y2500，算法停止。,2.2 簡單算法舉例,圖 2.1,圖2.1,能被4整除，又能被100整除，而不能被400整除的那些年份 如100，200，1000,如，1600,如，4040,2.2 簡單算法舉例,一 個(gè) 算 法 應(yīng) 具 有 以 下 特 點(diǎn)： 1.有窮性 一個(gè)算法應(yīng)包含有限步操作。并且還應(yīng)該“在合理的范圍 之內(nèi)”。究竟什么算“合理限度”，并無嚴(yán)格標(biāo)準(zhǔn)，由人們的 常識和需要而定。 2.確定性 算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、 模棱兩可的。,2.3 算法的特性,3.有零個(gè)或多個(gè)輸入 所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得的必要的信息。 一個(gè)算法也可以沒有輸入。 4.有一個(gè)或多個(gè)輸出 算法的目的是為了求解，“解” 就是輸出。沒有輸出的算法 是沒有意義的。 5.有效性 算法中的每一個(gè)步驟都應(yīng)能有效地執(zhí)行，并得到確定的結(jié) 果。,2.3 算法的特性,程序員：必須設(shè)計(jì)算法， 并根據(jù)算法編寫程序。,普通用戶：只需給以必要 的輸入，就能得到結(jié)果。,2.3 算法的特性,自然語言表示 傳統(tǒng)流程圖表示 N-S流程圖表示 偽代碼表示 計(jì)算機(jī)語言表示（對算法的實(shí)現(xiàn)）,2.4 怎樣表示一個(gè)算法,2.4.1 用自然語言表示算法 優(yōu)點(diǎn)：通俗易懂 缺點(diǎn)：文字冗長， 容易出現(xiàn)“歧義性”。不方便描述包含分 支和循環(huán)的算法。 2.4.2 用流程圖表示算法 是指用一些圖框來表示算法中的各種操作。 美國國家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號(見圖2.3)。,對給定的條件進(jìn)行判斷，根據(jù)判斷結(jié)果決定其后的操作， 單入口，雙出口，見圖2.4,連接畫在不同地方的流程線，避免流程圖交叉或過長。見圖2.5,常 用 的 流 程 圖 符 號,圖 2.4 菱形框示意圖,圖 2.5 連接點(diǎn)示意圖,常 用 的 流 程 圖 符 號,求5!,流 程 圖 舉 例,求5!并輸出,流 程 圖 舉 例,判斷是否為潤年,傳統(tǒng)流程圖的構(gòu)成： 操作框 (起止、I/O、判斷、處理、注釋) 流程線 （箭頭表示執(zhí)行順序） 文字說明 傳統(tǒng)流程圖的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：直觀，邏輯關(guān)系明確，易于理解。 缺點(diǎn)：占用篇幅多，表示復(fù)雜算法時(shí)，費(fèi)時(shí)費(fèi)力。,傳統(tǒng)流程圖的構(gòu)成及特點(diǎn),算法的重要性（4要素之一） 算法的特性（有窮、確定、有效、 0或多個(gè)I，1或多個(gè)O） 自然語言表示算法 通俗易懂 不方便表示分支和循環(huán) 傳統(tǒng)流程圖表示算法 直觀形象 占用篇幅較多,要 點(diǎn) 回 顧,1.傳統(tǒng)流程圖的弊端 對流程線的使用無限制，使流程毫無規(guī)律。如圖2.13。 難以保證算法可靠性和可維護(hù)性。 那么，如何表示分支和循環(huán)這些非順序的流程呢？ 規(guī)定出幾種基本結(jié)構(gòu)，順序排列組成一個(gè)算法。,2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖,圖2.13,圖2.13,2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖,2. 三種基本結(jié)構(gòu) 1966，Bohra和Jacopini提出以下三種結(jié)構(gòu)： (1) 順序結(jié)構(gòu)，圖2.14。 (2) 選擇結(jié)構(gòu)，又稱分支結(jié)構(gòu)，圖2.15 。 兩個(gè)分支中可以有一個(gè)是空，圖2.16 。 (3) 循環(huán)結(jié)構(gòu)，又稱重復(fù)結(jié)構(gòu)，分兩類： 當(dāng)(While)型循環(huán)結(jié)構(gòu) 直到(Until)型循環(huán)結(jié)構(gòu),2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖,圖2.14,Return,順 序 結(jié) 構(gòu),圖2.15 圖2.16,Return,分 支 結(jié) 構(gòu), 當(dāng)型(While型)循環(huán) 先判斷條件p1，當(dāng)條件p1成立時(shí)，執(zhí)行A，條件 p1不成立時(shí)終止循環(huán)，見圖2.17(a)。 直到型(Until型)循環(huán) 先執(zhí)行A，然后判斷條件p2是否成立，當(dāng)條件p2不 成立時(shí)，執(zhí)行A，條件p2成立時(shí)終止循環(huán)， 見圖2.17(b) 。,循 環(huán) 結(jié) 構(gòu),圖2.17（a）,Return,循 環(huán) 結(jié) 構(gòu),圖2.17（b）,“當(dāng)” 型循環(huán)的例子: 打印1，2，3，4，5,循 環(huán) 結(jié) 構(gòu),“直到” 型循環(huán)的例子: 打印1，2，3，4，5,循 環(huán) 結(jié) 構(gòu),三 種 基 本 結(jié) 構(gòu) 的 特 點(diǎn) ： 只有一個(gè)入口。 只有一個(gè)出口。 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到。圖2.20 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無終止的循環(huán))。圖2.21,2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖,菱形判斷框,選擇結(jié)構(gòu),圖2.20 圖2.21,Return,2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖,由基本結(jié)構(gòu)派生出的基本結(jié)構(gòu),N-S流程圖由三種基本結(jié)構(gòu)順序組合而成，無流程線。 N-S流程圖所用符號：,2.4.4 用N-S流程圖表示算法,順 序 結(jié) 構(gòu),分 支 結(jié) 構(gòu),A或B，可以是一個(gè)簡單操作，也可以是3個(gè)基本結(jié)構(gòu)之一。,當(dāng) 型 循 環(huán) 結(jié) 構(gòu),直 到 型 循 環(huán) 結(jié) 構(gòu),2.4.4 用N-S流程圖表示算法,2.4.4 用N-S流程圖表示算法,A框：選擇結(jié)構(gòu),B框：循環(huán)結(jié)構(gòu),例2.11 求5的階乘算法用N-S圖表示。,N-S 流 程 圖 舉 例,例2.13 判定閏年的算法用N-S圖表示。,N-S 流 程 圖 舉 例,N-S流程圖的優(yōu)點(diǎn)： 比文字描述直觀、形象、 易于理解 比傳統(tǒng)流程圖緊湊易畫 整個(gè)算法由各個(gè)基本結(jié)構(gòu)順序組成，N-S圖中的上下順序就是執(zhí)行時(shí)的順序 用N-S圖表示的算法都是結(jié)構(gòu)化的算法,2.4.4 用N-S流程圖表示算法,特點(diǎn)：流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)范圍之內(nèi),思考：結(jié)構(gòu)化的算法有何特點(diǎn)？,傳統(tǒng)流程圖和N-S圖： 直觀易懂，但畫起來較費(fèi)事，適合用來表示算法。 偽代碼：書寫方便 、格式緊湊，也比較好懂， 適合用來設(shè)計(jì)算法。,2.4.5 用偽代碼表示算法,偽代碼是指用介于自然語言和計(jì)算機(jī)語言之間的文字和符號來描述算法。,中英文混用：,用英文表示偽代碼：,IF x is positive THEN print x ELSE print x,用漢字表示偽代碼：,若 x為正 打印 x 否則 打印 x,IF x 為正 print x ELSE print x,2.4.5 用偽代碼表示算法,用偽代碼表示“打印x的絕對值”的算法,用偽代碼表示求5! 算法如下：,開始 置t的初值為1 置i的初值為2 當(dāng)i=5，執(zhí)行下面操作： 使t=ti 使i=i+1 (循環(huán)體到此結(jié)束) 打印t的值 結(jié)束,2.4.5 用偽代碼表示算法,BEGIN(算法開始) 1=t 2=i while it i+1=i print t END(算法結(jié)束),BEGIN(算法開始) 2000=y while yy END(算法結(jié)束),用偽代碼表示判斷閏年的算法如下：,偽代碼寫算法的優(yōu)點(diǎn)： 書寫格式自由，容易表達(dá)出設(shè)計(jì)者的思想； 算法容易修改； 容易寫出結(jié)構(gòu)化的算法。 偽代碼寫算法的缺點(diǎn)： 不如流程圖直觀； 可能會(huì)出現(xiàn)邏輯上的錯(cuò)誤(如循環(huán)范圍搞錯(cuò)等)。,2.4.5 用偽代碼表示算法,結(jié)構(gòu)化程序用高級語言表示的結(jié)構(gòu)化的算法。 結(jié)構(gòu)化程序的特點(diǎn)： 便于編寫、閱讀、修改和維護(hù)，程序的可靠性高； 強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu) 結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路： 將一個(gè)復(fù)雜的問題分解成若干個(gè)簡單的問題來進(jìn)行處理。,2.5 結(jié)構(gòu)化程序設(shè)計(jì)方法,結(jié)構(gòu)化程序設(shè)計(jì)方法： 自頂向下； 逐步細(xì)化； 模塊化設(shè)計(jì)； 結(jié)構(gòu)化編碼。 完成一個(gè)任務(wù)有兩種方法： 自頂向下，逐步細(xì)化； 自下而上，逐步積累。,（提倡使用此方法）,2.5 結(jié)構(gòu)化程序設(shè)計(jì)方法,圖2.36,圖2.38,圖2.39,將這三部分進(jìn)一步細(xì)化為： A部分細(xì)化為圖2.40。 B部分細(xì)化為圖2.41。,圖2.40 圖2.41,圖2.41B1處理的方法是：使x1=0，即哪個(gè)數(shù)不是素?cái)?shù)， 就使 它等于0，以后把不等于零的數(shù)打印出來就是所求的素?cái)?shù)表。 圖2.4