C語言程序設(shè)計大學(xué)課件第2章算法

1、 2.1 2.1 算法的概念算法的概念 2.2 2.2 簡單算法舉例簡單算法舉例 2.3 2.3 算法的特性算法的特性 2.4 2.4 怎樣表示一個算法怎樣表示一個算法 2.5 2.5 化程序設(shè)計方法化程序設(shè)計方法 C程序設(shè)計（第三版）程序設(shè)計（第三版） 4 一個程序應(yīng)包括兩個方面的內(nèi)容: 對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure) 對操作的描述：算法(algorithm) 著名計算機科學(xué)家沃思提出一個公式: 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法 = 程序程序 數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具 完整的程序設(shè)計應(yīng)該是: C程序設(shè)計（第三版）程序設(shè)計（第三版）

2、 5 2.1 2.1 算法的概念算法的概念 廣義地說，為解決一個問題而采取的方 法和步驟，就稱為“算法”。 方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次 對同一個問題，可有不同的解題方法和步驟 例： 求 100 1n n C程序設(shè)計（第三版）程序設(shè)計（第三版） 6 2.1 2.1 算法的概念算法的概念 為了有效地進行解題，不僅需要保證 算法正確，還要考慮算法的質(zhì)量，選擇合 適的算法。希望方法簡單，運算步驟少。 計算機算法可分為兩大類別： 數(shù)值運算算法：求數(shù)值解，例如求方程的

3、 根、求函數(shù)的定積分等。 非數(shù)值運算：包括的面十分廣泛，最常見 的是用于事務(wù)管理領(lǐng)域，例如圖書檢索、 人事管理、行車調(diào)度管理等。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 7 2.2 2.2 簡單算法舉例簡單算法舉例 例例2.1: 求求12345 步驟1：先求12，得到結(jié)果2 步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6 步驟3：將6再乘以4，得24 步驟4：將24再乘以5，得120 如果要求如果要求1 12 210001000，則要寫，則要寫999999個步驟個步驟 C程序設(shè)計（第三版）程序設(shè)計（第三版） 8 S1：使p=1。 S2：使i=2。 S3：使pi，乘積仍放在變量p中，可表示為：

4、pip S4：使i的值加1，即i+1i。 S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后 的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就 是5!的值。 可以設(shè)兩個變量：可以設(shè)兩個變量：一個變量代表被乘數(shù)，一 個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié) 果，而直接將每一步驟的乘積放在被乘數(shù) 變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán) 算法來求結(jié)果, 算法可改寫： C程序設(shè)計（第三版）程序設(shè)計（第三版） 9 S1：1p S2：3 i S3：pi p S4：i+2 p S5：若i11，返回S3。否則，結(jié)束。 如果題目改為：求1351000 算法只需作很少的改動： C程序設(shè)計（第三版）程序設(shè)計（第三版）

5、 10 用這種方法表示的算法具有通用性、 靈活性。S3到S5組成一個循環(huán)，在實現(xiàn) 算法時 要反復(fù)多次執(zhí)行S3，S4，S5等步 驟，直到某一時刻，執(zhí)行S5步驟時經(jīng)過 判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回 S3步驟為止。此時算法結(jié)束，變量p的值 就是所求結(jié)果。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 11 例例2.2 有有50個學(xué)生，要求將他們之中成績在個學(xué)生，要求將他們之中成績在80 分以上者打印出來。設(shè)分以上者打印出來。設(shè)n表示學(xué)號，表示學(xué)號， n1代表代表 第一個學(xué)生學(xué)號，第一個學(xué)生學(xué)號， 代表第代表第i個學(xué)生學(xué)號。用個學(xué)生學(xué)號。用G 代表學(xué)生成績代表學(xué)生成績 ， gi代表第代表第i個學(xué)生成

6、績，算法個學(xué)生成績，算法 表示如下表示如下: S1：1 i S2：如果80，則打印和，否則不打印。 S3：i+1 i S4：如果i50，返回S2，繼續(xù)執(zhí)行。否則算法結(jié)束 變量i作為下標，用來控制序號(第幾個學(xué) 生，第幾個成績)。當(dāng)i超過50時，表示 已對 50個學(xué)生的成績處理完畢，算法結(jié)束。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 12 例例2.3 判定判定20002500年中的每一年是否閏年，年中的每一年是否閏年， 將結(jié)果輸出。將結(jié)果輸出。 變量變量i i作為下標，用來控制序號作為下標，用來控制序號( (第幾個學(xué)第幾個學(xué) 生，第幾個成績生，第幾個成績) )。當(dāng)。當(dāng)i i超過超過5050時，表

7、示時，表示 已對已對 5050個學(xué)生的成績處理完畢，算法結(jié)束。個學(xué)生的成績處理完畢，算法結(jié)束。 分析：分析：閏年的條件是：(1)能被4整除，但不能被 100整除的年份都是閏年，如1996,2004年是閏 年；(2)能被100整除，又能被400整除的年份是 閏年。如1600,2000年是閏年。不符合這兩個條 件的年份不是閏年。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 13 設(shè)y為被檢測的年份，算法可表示如下 ： S1：2000 y S2：若y不能被4整除，則輸出y “不是閏年”。然后轉(zhuǎn) 到S6。 S3：若y能被4整除，不能被100整除，則輸出y “是閏 年”。然后轉(zhuǎn)到S6。 S4：若y能被100

8、整除，又能被400整除，輸出y“是閏年 ”，否則輸出“不是閏年”。 然后轉(zhuǎn)到S6。 S5: 輸出y “不是閏年”。 S6：y+1 y S7：當(dāng)y2500時，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y2500，算法 停止。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 14 以上算法中每做一 步都分別分離出一 些范圍(巳能判定為 閏年或非閏年)，逐 步縮小范圍，直至 執(zhí)行S5時，只可能 是非閏年。 “其它” 包括能被4 整除，又能被100整 除，而不能被400整 除的那些年份(如 1990) 是非閏年。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 15 例例2.4 求求 算法如下 ： 100 1 99 1 . 4 1 3 1

9、2 1 1 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：若deno100返回S4，否則算法結(jié)束。 單詞作變量名，以使算 法更易于理解： sum表示累加和，deno是 英文分母（denom inator） 縮寫，sign代表數(shù)值的符 號，term代表某一項。 反復(fù)執(zhí)行S4到S8步驟，直到分母大于100為止。 一共執(zhí)行了99次循環(huán)，向sum累加入了99個分數(shù)。 sum最后的值就是多項式的值。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 16 例例

10、2.5 對一個大于或等于對一個大于或等于3的正整數(shù)，判斷的正整數(shù)，判斷 它是不是一個素數(shù)。它是不是一個素數(shù)。 概念：概念：所謂素數(shù)，是指除了1和該數(shù)本身之外， 不能被其它任何整數(shù)整除的數(shù)。例如，13是 素數(shù)。因為它不能被2，3，4，12整除。 分析：分析：判斷一個數(shù)n(n3)是否素數(shù)的方法： 將n作為被除數(shù)，將2到(n-1)各個整數(shù)輪流作 為除數(shù)，如果都不能被整除，則n為素數(shù)。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 17 算法如下 ： S1：輸入n的值 S2：i=2 （i作為除數(shù)） S3：n被i除，得余數(shù)r S4：如果r=0，表示n能被i整除，則打印n“不是 素數(shù)”，算法結(jié)束。否則執(zhí)行S5

11、S5：i+1i S6：如果in-1，返回S3。否則打印 n “是素數(shù) ”。然后結(jié)束。 實際上，n不必被2到(n-1)的整數(shù)除，只 需被2到n/2間整數(shù)除，甚至只需被2到 之間 的整數(shù)除即可。 n C程序設(shè)計（第三版）程序設(shè)計（第三版） 18 2.3 2.3 算法的特性算法的特性 有窮性：包含有限的操作步驟。 確定性：算法中的每一個步驟都應(yīng)當(dāng)是確 定的。 有零個或多個輸入：輸入是指在執(zhí)行算法 時需要從外界取得必要的信息。 有一個或多個輸出：算法的目的是為了求 解，“解” 就是輸出。 有效性：算法中的每一個步驟都應(yīng)當(dāng)能有 效地執(zhí)行，并得到確定的結(jié)果 。 一個算法應(yīng)該具有以下特點：一個算法應(yīng)該具有以

12、下特點： C程序設(shè)計（第三版）程序設(shè)計（第三版） 19 2.4 2.4 算法的表示算法的表示 可以用不同的方法表示算法，常用的有： 自然語言 傳統(tǒng)流程圖 結(jié)構(gòu)化流程圖 偽代碼 PAD圖 C程序設(shè)計（第三版）程序設(shè)計（第三版） 20 2.4.1 2.4.1 用自然語言表示算法用自然語言表示算法 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可 以是漢語或英語或其它語言。用自然語言 表示通俗易懂，但文字冗長，容易出現(xiàn)“ 歧義性”。自然語言表示的含義往往不大 嚴格，要根據(jù)上下文才能判斷其正確含義 ，描述包含分支和循環(huán)的算法時也不很方 便。因此，除了那些很簡單的問題外，一 般不用自然語言描述算法。 C程序設(shè)計（第三

13、版）程序設(shè)計（第三版） 21 2.4.2 2.4.2 用流程圖表示算法用流程圖表示算法 美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定了一 些常用的流程圖符號： 起止框起止框判斷框判斷框處理框處理框輸入輸入/輸出框輸出框 注釋框注釋框流向線流向線 連接點連接點 C程序設(shè)計（第三版）程序設(shè)計（第三版） 22 例例2.6 將求將求5!的算法用流程圖表示的算法用流程圖表示 如果需要將最后結(jié) 果打印出來，可在 菱形框的下面加一 個輸出框。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 23 例例2.7 將例將例2.2的算的算 法用流程圖表示。打法用

14、流程圖表示。打 印印50名名 學(xué)生中成績在學(xué)生中成績在 80分以上者的學(xué)號和分以上者的學(xué)號和 成績。成績。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 24 如果如果包括 這個輸入數(shù)據(jù) 的部分，流程 圖為 C程序設(shè)計（第三版）程序設(shè)計（第三版） 25 例例2.8 將例將例 2.3判定閏判定閏 年的算法用年的算法用 流程圖表示流程圖表示 用流程圖表示算法要比 用文字描述算法邏輯清 晰、易于理解。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 26 例例2.9 將例將例2.4的算法用流程圖表示的算法用流程圖表示 100 1 99 1 . 4 1 3 1 2 1 1 C程序設(shè)計（第三版）程序設(shè)計（第三版） 2

15、7 例例2.10 將例將例2.5判斷素數(shù)判斷素數(shù) 的算法用流程圖表示的算法用流程圖表示 C程序設(shè)計（第三版）程序設(shè)計（第三版） 28 小結(jié)：小結(jié)： 流程圖是表示算法的較好的工具。 一個流程圖包括以下幾部分 ： (1)表示相應(yīng)操作的框； (2)帶箭頭的流程線； (3)框內(nèi)外必要的文字說明。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 29 2.4.3 2.4.3 三種基本結(jié)構(gòu)和改進的流程圖三種基本結(jié)構(gòu)和改進的流程圖 1.傳統(tǒng)流程圖的弊端 傳統(tǒng)流程圖用流程線指出各框的執(zhí)行 順序，對流程線的使用沒有嚴格限制。因 此，使用者可以毫不受限制地使流程隨意 地轉(zhuǎn)向，使流程圖變得毫無規(guī)律，閱讀者 要花很大精力去追

16、蹤流程，使人難以理解 算法的邏輯。如圖： C程序設(shè)計（第三版）程序設(shè)計（第三版） 30 傳統(tǒng)流程圖的流程可以是： 這種如同亂麻一樣的算法稱為BS型算 法，意為一碗面條(A Bowl of Spaghetti)，亂無頭緒。 缺點：難以閱讀、修改，使算法的 可靠性和可維護性難以保證。 解決辦法：必須限制箭頭的濫用， 即不允許無規(guī)律地使流程隨意轉(zhuǎn)向， 只能順序地進行下去。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 31 2.三種基本結(jié)構(gòu) Bohra和Jacopini提出了以下三種基本 結(jié)構(gòu)： 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 用這三種基本結(jié)構(gòu)作為表示一個良好算 法的基本單元。

17、C程序設(shè)計（第三版）程序設(shè)計（第三版） 32 三種基本結(jié)構(gòu)的圖示： 順序結(jié)構(gòu)順序結(jié)構(gòu) 選擇結(jié)構(gòu)選擇結(jié)構(gòu) C程序設(shè)計（第三版）程序設(shè)計（第三版） 33 循環(huán)循環(huán)結(jié)構(gòu)的圖示： 當(dāng)型當(dāng)型(While型型)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 直到型直到型(Until型型)循環(huán)循環(huán) C程序設(shè)計（第三版）程序設(shè)計（第三版） 34 三種基本結(jié)構(gòu)的共同特點： (1)只有一個入口。 (2)只有一個出口。（請注意：一個菱形判斷 框有兩個出口，而一個選擇結(jié)構(gòu)只有一個出 口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口 混淆。） (3)結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。 (4)結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無終止的循環(huán)) 。 C程序設(shè)計（第三版）程序

18、設(shè)計（第三版） 35 圖中沒有一條 從入口到出口的 路徑通過A框 不正確的流程表示： 流程內(nèi)的死循環(huán) C程序設(shè)計（第三版）程序設(shè)計（第三版） 36 小結(jié)：小結(jié)： 由三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu) ，可以解決任何復(fù)雜的問題。由基本 結(jié)構(gòu)所構(gòu)成的算法屬于“結(jié)構(gòu)化”的 算法，它不存在無規(guī)律的轉(zhuǎn)向，只在 本基本結(jié)構(gòu)內(nèi)才允許存在分支和向前 或向后的跳轉(zhuǎn)。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 37 擴展：擴展： 只要具有上述四 個特點的都可以 作為基本結(jié)構(gòu)。 可以自己定義基 本結(jié)構(gòu)，并由這 些基本結(jié)構(gòu)組成 結(jié)構(gòu)化程序。 此圖符合基本結(jié)構(gòu)的特點 C程序設(shè)計（第三版）程序設(shè)計（第三版） 38 這是一個多分

19、 支選擇結(jié)構(gòu)，根據(jù) 表達式的值決定執(zhí) 行路線。虛線框內(nèi) 的結(jié)構(gòu)是一個入口 一個出口，并且有 上述全部的四個特 點。由此構(gòu)成的算 法結(jié)構(gòu)也是結(jié)構(gòu)化 的算法?？梢哉J為 這是由三種基本結(jié) 構(gòu)所派生出來的。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 39 2.4.4 2.4.4 用用N-SN-S流程圖表示算法流程圖表示算法 1973年美國學(xué)者I.Nassi和B.Shneiderman 提出了一種新的流程圖形式。在這種流程圖 中，完全去掉了帶箭頭的流程線。全部算法 寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其 它的從屬于它的框，或者說，由一些基本的 框組成一個大的框。這種流程圖又稱N-S結(jié) 構(gòu)化流程圖。 C程序

20、設(shè)計（第三版）程序設(shè)計（第三版） 40 N-S流程圖用以下的流程圖符號： (1)順序結(jié)構(gòu) (2)選擇結(jié)構(gòu) (3)循環(huán)結(jié)構(gòu) C程序設(shè)計（第三版）程序設(shè)計（第三版） 41 用三種N-S流程圖中的基本框，可以組成復(fù)雜 的N-S流程圖。圖中的A框或B框，可以是一個簡 單的操作，也可以是三個基本結(jié)構(gòu)之一。 A框可以是一個選擇結(jié)構(gòu) B框可以是一個循環(huán)結(jié)構(gòu) C程序設(shè)計（第三版）程序設(shè)計（第三版） 42 例例2.11 將例將例2.1 的求的求5!算法用算法用 N-S圖表示圖表示 C程序設(shè)計（第三版）程序設(shè)計（第三版） 43 例例2.12 將例將例2.2 的算法用的算法用N-S 圖表示。（圖表示。（ 打印打印5

21、0名學(xué)名學(xué) 生中成績高生中成績高 于于80分的學(xué)分的學(xué) 號和成績）號和成績） 沒有輸入數(shù)據(jù) C程序設(shè)計（第三版）程序設(shè)計（第三版） 44 例例2.12 將例將例2.2 的算法用的算法用N-S 圖表示。（圖表示。（ 打印打印50名學(xué)名學(xué) 生中成績高生中成績高 于于80分的學(xué)分的學(xué) 號和成績）號和成績） 有輸入數(shù)據(jù) C程序設(shè)計（第三版）程序設(shè)計（第三版） 45 例例2.13 將例將例2.3 判定閏判定閏 年的算年的算 法用法用N-S 圖表示圖表示 C程序設(shè)計（第三版）程序設(shè)計（第三版） 46 例例2.14 將例將例2.4的算的算 法用法用N-S圖表示圖表示 100 1 99 1 . 4 1 3 1

22、 2 1 1 C程序設(shè)計（第三版）程序設(shè)計（第三版） 47 例例2.15 將例將例2.5判別判別 素數(shù)的算法用素數(shù)的算法用N-S 流程圖表示。流程圖表示。 傳統(tǒng)流程圖分析： 出口出口1 出口出口2 此圖不符合基本結(jié)構(gòu)特點！ 由于不能分解為三種基本結(jié) 構(gòu)，就無法直接用N-S流程 圖的三種基本結(jié)構(gòu)的符號來 表示。因此，應(yīng)當(dāng)先作必要 的變換。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 48 例例2.15 將例將例2.5判別判別 素數(shù)的算法用素數(shù)的算法用N-S 流程圖表示。流程圖表示。 傳統(tǒng)流程圖變換為： 一個出口一個出口 C程序設(shè)計（第三版）程序設(shè)計（第三版） 49 用用N-S流程圖表示：流程圖表示：

23、 C程序設(shè)計（第三版）程序設(shè)計（第三版） 50 N-SN-S圖表示算法的優(yōu)點圖表示算法的優(yōu)點 比文字描述直觀、形象、 易于理解； 比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除 了流程線，整個算法結(jié)構(gòu)是由各個基本 結(jié)構(gòu)按順序組成的，N-S流程圖中的上 下順序就是執(zhí)行時的順序。用N-S圖表 示的算法都是結(jié)構(gòu)化的算法，因為它不 可能出現(xiàn)流程無規(guī)律的跳轉(zhuǎn)，而只能自 上而下地順序執(zhí)行。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 51 小結(jié)：小結(jié)： 一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序 組成的。在基本結(jié)構(gòu)之間不存在向前或向 后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本 結(jié)構(gòu)范圍之內(nèi)(如循環(huán)中流程的跳轉(zhuǎn))；一 個非結(jié)構(gòu)化的算法

24、可以用一個等價的結(jié)構(gòu) 化算法代替，其功能不變 。如果一個算 法不能分解為若干個基本結(jié)構(gòu)，則它必然 不是一個結(jié)構(gòu)化的算法。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 52 2.4.5 2.4.5 用位代碼表示算法用位代碼表示算法 概念：偽代碼是用介于自然語言和計算機 語言之間的文字和符號來描述算法。 特點：它如同一篇文章一樣 ，自上而下地 寫下來。每一行(或幾行)表示一個基本操 作。它不用圖形符號，因此書寫方便 、格 式緊湊，也比較好懂，也便于向計算機語 言算法(即程序)過渡。 用處：適用于設(shè)計過程中需要反復(fù)修改時 的流程描述。 C程序設(shè)計（第三版）程序設(shè)計（第三版） 53 IF x is pos

25、itive THEN print x ELSE print -x 也可以用漢字偽代碼表示：也可以用漢字偽代碼表示： 若若 x為正為正 打印打印 x 否則否則 打印打印 -x 也可以中英文混用，如：也可以中英文混用，如： IF x 為正為正 print x ELSE print -x 例： “打印x的絕對值 ”的算法可以用偽代 碼表示為： C程序設(shè)計（第三版）程序設(shè)計（第三版） 54 開始開始 置置t的初值為的初值為1 置置i的初值為的初值為2 當(dāng)當(dāng)i=5，執(zhí)行下面操作：，執(zhí)行下面操作： 使使t=ti 使使i=i+1 循環(huán)體到此結(jié)束循環(huán)體到此結(jié)束 輸出輸出t的值的值 結(jié)束結(jié)束 也可以寫成以下形式

26、：也可以寫成以下形式： BEGIN算法開始算法開始 1t 2 i while i5 ti t i+1 i print t END算法結(jié)束算法結(jié)束 例例2.16 求求5!。用偽代。用偽代 碼表示算法：碼表示算法： C程序設(shè)計（第三版）程序設(shè)計（第三版） 55 例例2.17 輸出輸出50個學(xué)生個學(xué)生 中成績高于中成績高于80分者分者 的學(xué)號和成績。的學(xué)號和成績。 用偽代碼表示算法：用偽代碼表示算法： BEGIN算法開始算法開始 1 i while i50 input ni and gi i+1 i 1 i while i50 if gi80 print ni and gi i+1 i END算法結(jié)束算法結(jié)束 C程序設(shè)計（第三版）程序設(shè)計（第三版） 56 2.4.6 2.4.6 用計算機語言表示算法用計算機語言表示算法 概念：用計算機實現(xiàn)算法。計算機是無法 識別流程圖和偽代碼的。只有用計算機語 言編寫的程序才能被計算機執(zhí)行。因此在 用流程圖或偽代碼描述出一個算法后，還 要將它轉(zhuǎn)換成計算機語言程序。 特點：用計