C語言課件第2章New1.pptVIP

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