計算機(jī)二級考試教程第2章_算法

1、第二章第二章l 本章要點l 主要內(nèi)容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è)計（第三版） http:/ 4一個程序應(yīng)包括兩個方面的內(nèi)容: 對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure) 對操作的描述：算法(algorithm)著名計算機(jī)科學(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è)

2、計（第三版）程序設(shè)計（第三版） http:/ 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次對同一個問題，可有不同的解題方法和步驟例： 求1001nnC程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 6 2.3 2.3 算法的特性算法的特性 有窮性：包含有限的操作步驟。 確定性：算法中的每一個步驟都應(yīng)當(dāng)是確定的。 有零個或多個輸入：輸入是指在執(zhí)行算法時需要從外界取得必要

3、的信息。 有一個或多個輸出：算法的目的是為了求解，“解” 就是輸出。 有效性：算法中的每一個步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果 。一個算法應(yīng)該具有以下特點：一個算法應(yīng)該具有以下特點：C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 7 2.4 2.4 算法的表示可以用不同的方法表示算法，常用的有： 自然語言自然語言 傳統(tǒng)流程圖傳統(tǒng)流程圖 結(jié)構(gòu)化流程圖結(jié)構(gòu)化流程圖 偽代碼偽代碼 PADPAD圖圖C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 8 2.4.2 2.4.2 用流程圖表示算法用流程圖表示算法美國國家標(biāo)準(zhǔn)化協(xié)會ANSI(American National Standard

4、 Institute)規(guī)定了一些常用的流程圖符號：起止框起止框判斷框判斷框處理框處理框輸入輸入/輸出框輸出框注釋框注釋框流向線流向線連接點連接點C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 9例例2.6 將求將求5!的算法用流程圖表示的算法用流程圖表示如果需要將最后結(jié)果打印出來，可在菱形框的下面加一個輸出框。 C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 10 2.4.3 2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖三種基本結(jié)構(gòu)和改進(jìn)的流程圖1.傳統(tǒng)流程圖的弊端 傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制。因此，使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變

5、得毫無規(guī)律，閱讀者要花很大精力去追蹤流程，使人難以理解算法的邏輯。如圖：C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 11傳統(tǒng)流程圖的流程可以是： 這種如同亂麻一樣的算法稱為BS型算法，意為一碗面條(A Bowl of Spaghetti)，亂無頭緒。Be all thumbs缺點：難以閱讀、修改，使算法的可靠性和可維護(hù)性難以保證。解決辦法：必須限制箭頭的濫用，即不允許無規(guī)律地使流程隨意轉(zhuǎn)向，只能順序地進(jìn)行下去。 C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 122.三種基本結(jié)構(gòu) Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)： 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)

6、構(gòu)、循環(huán)結(jié)構(gòu) 用這三種基本結(jié)構(gòu)作為表示一個良好算法的基本單元。C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 13三種基本結(jié)構(gòu)的圖示： 順序結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)選擇結(jié)構(gòu)這兩種結(jié)構(gòu)中，箭頭沒有往回的指向。這兩種結(jié)構(gòu)中，箭頭沒有往回的指向。只有一種選擇C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 14循環(huán)循環(huán)結(jié)構(gòu)的圖示：dead-loop 當(dāng)型當(dāng)型(While型型)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 直到型直到型(Until型型)循環(huán)循環(huán) C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 15三種基本結(jié)構(gòu)的共同特點：(1)只有一個入口。 (2)只有一個出口。（請注意：一個菱形判斷框有兩個出口，而一

7、個選擇結(jié)構(gòu)只有一個出口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口混淆。）(3)結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會被執(zhí)行到。(4)結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無終止的循環(huán))。 C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 16 圖中沒有一條從入口到出口的路徑通過A框不正確的流程表示：流程內(nèi)的死循環(huán)未作判未作判斷斷C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 17 N-S流程圖用以下的流程圖符號： (1)順序結(jié)構(gòu)(2)選擇結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)C程序設(shè)計（第三版）程序設(shè)計（第三版） http:/ 18采取以下方法來保證得到結(jié)構(gòu)化的程序： 自頂向下； 逐步細(xì)化； 模塊化設(shè)計； 結(jié)構(gòu)化編碼。兩種不同的方法：兩種不同的方法： 自頂向下，逐步細(xì)化；自頂向下