C語言程序設(shè)計第02章-算法

1、第二章 本章要點算法的概念 算法的表示結(jié)構(gòu)化程序設(shè)計方法 一個程序應(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è)計方法語言工具完整的程序設(shè)計應(yīng)該是: 2.1 算法的概念 1、算法：計算機求解某一問題而采用的具體方法和步驟，就稱為“算法”。對同一個問題，可有不同的解題方法和步驟 為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡單，運算步驟少。 2.1 算法的概念(1)數(shù)值運算算法：求數(shù)值解，例如求方程的根

2、、求函數(shù)的定積分等。(2)非數(shù)值運算算法：包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域，例如圖書檢索、人事管理、車輛調(diào)度管理等。2、計算機算法可分為兩大類別：有窮性：包含有限的操作步驟確定性：算法中的每一個步驟都應(yīng)當是確定的 有零個或多個輸入：輸入是指在執(zhí)行算法時需要從外界取得必要的信息 有一個或多個輸出：算法的目的是為了求解，“解” 就是輸出 有效性：算法中的每一個步驟都應(yīng)當能有效地執(zhí)行，并得到確定的結(jié)果 。3、算法的特性： 2.2 算法的描述方法可以用不同的方法表示算法，常用的有：自然語言傳統(tǒng)流程圖N-S流程圖偽代碼計算機語言 1、 用自然語言表示算法 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以

3、是漢語或英語或其它語言。用自然語言表示的算法通俗易懂，但文字冗長，容易出現(xiàn)“歧義性”。自然語言表示的含義往往不太嚴格，要根據(jù)上下文才能判斷其正確含義，描述包含分支和循環(huán)的算法時也不很方便。因此，除了那些很簡單的問題外，一般不用自然語言描述算法。 2、 用傳統(tǒng)的流程圖表示算法 美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流程線連接點三種基本結(jié)構(gòu) Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)： 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 用這三種基本結(jié)構(gòu)作為表示一個良好算法的基本單元。

4、三種基本結(jié)構(gòu)的圖示： 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)的圖示： 當型(While型)循環(huán)結(jié)構(gòu) 直到型(Until型)循環(huán) 不 3、用N-S流程圖表示算法 1973年美國學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其它的從屬于它的框，或者說，由一些基本的框組成一個大的框。這種流程圖又稱N-S結(jié)構(gòu)化流程圖 。 N-S流程圖用以下的流程圖符號： (1)順序結(jié)構(gòu)(2)選擇結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu) 用三種N-S流程圖中的基本框，可以組成復(fù)雜的N-S流程圖。圖中的A框或B框，可以是一個簡單的操作，也可以是三

5、個基本結(jié)構(gòu)之一。 A框可以是一個選擇結(jié)構(gòu) B框可以是一個循環(huán)結(jié)構(gòu) 4、用偽代碼表示算法概念：偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。特點：它如同一篇文章一樣 ，自上而下地寫下來。每一行(或幾行)表示一個基本操作。它不用圖形符號，因此書寫方便 、格式緊湊，也比較好懂，也便于向計算機語言算法(即程序)過渡。用處：適用于設(shè)計過程中需要反復(fù)修改時的流程描述。 IF x is positive THEN print x ELSE print -x也可以用漢字偽代碼表示： 若 x為正 打印 x 否則 打印 -x也可以中英文混用，如： IF x 為正 print x ELSE prin

6、t -x例： “打印x的絕對值”的算法可以用偽代碼表示為： 5、用計算機語言表示算法概念：用計算機實現(xiàn)算法。計算機是無法識別流程圖和偽代碼的。只有用計算機語言編寫的程序才能被計算機執(zhí)行。因此在用流程圖或偽代碼描述出一個算法后，還要將它轉(zhuǎn)換成計算機語言程序。 特點：用計算機語言表示算法必須嚴格遵循所用的語言的語法規(guī)則，這是和偽代碼不同的。用處：要完成一件工作，包括設(shè)計算法和實現(xiàn)算法兩個部分。設(shè)計算法的目的是為了實現(xiàn)算法。強調(diào)說明： 寫出了C程序，仍然只是描述了算法，并未實現(xiàn)算法。只有運行程序才是實現(xiàn)算法。應(yīng)該說，用計算機語言表示的算法是計算機能夠執(zhí)行的算法。例1、從a,b中找出一個較大數(shù)賦給ma

7、x。 (1)自然語言的算法描述如下： 第一步：從鍵盤輸入兩個數(shù)a和b；第二步：如果a大于b，則把a的值賦給max， 否則，把b的值賦給max；第三步：輸出max的值。例1、從a,b中找出一個較大數(shù)賦給max。 (2) 傳統(tǒng)流程圖的算法描述如下： YNab?輸出maxmax=bmax=a結(jié)束開始輸入a,b例1、從a,b中找出一個較大數(shù)賦給max。 (3) N-S流程圖的算法描述如下： 例1、從a,b中找出一個較大數(shù)賦給max。 (4) 偽代碼的算法描述如下： begininput a and bif ab a maxelse b maxprint maxend 例1、從a,b中找出一個較大數(shù)賦給

8、max。 (5) 計算機語言的算法描述如下： #include void main()int a,b,max;scanf(%d%d,&a,&b);if(ab) max=a;else max=b;printf(%d,max);例2、計算S=,寫出其算法。(1)自然語言的算法描述如下：S1：0 SS2：1 nS3：S+n SS4：n+1 nS5：判斷n100? 是，轉(zhuǎn)S3；否則，轉(zhuǎn)S6S6：輸出S的值。(2) 傳統(tǒng)流程圖的算法描述如下：(3) N-S流程圖的算法描述如下： 0 S 1 nn100? S+n S n+1 n輸出S的值(4) 偽代碼的算法描述如下： begin 0 S 1 n do S

9、+n S n+1 n while n100 print S end(5) 計算機語言的算法描述如下：#include void main()int n,S; S=0;n=1;doS=S+n;n=n+1;while(n=100);printf(S=%dn,S);N-S圖表示算法的優(yōu)點比文字描述直觀、形象、 易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個算法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的，N-S流程圖中的上下順序就是執(zhí)行時的順序。用N-S圖表示的算法都是結(jié)構(gòu)化的算法，因為它不可能出現(xiàn)流程無規(guī)律的跳轉(zhuǎn)，而只能自上而下地順序執(zhí)行。1、三種基本結(jié)構(gòu) Bohra和Jacopini提出了以下三

10、種基本結(jié)構(gòu)： 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 用這三種基本結(jié)構(gòu)作為表示一個良好算法的基本單元。 2.3 結(jié)構(gòu)化程序設(shè)計方法三種基本結(jié)構(gòu)的圖示： 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)的圖示： 當型(While型)循環(huán)結(jié)構(gòu) 直到型(Until型)循環(huán) 不2、三種基本結(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))。 圖中沒有一條從入口到出口的路徑通過A框。不正確的流程表示：流程內(nèi)的死循環(huán)擴展：只要具有上述四個特點的

11、都可以作為基本結(jié)構(gòu)。可以自己定義基本結(jié)構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化程序。此圖符合基本結(jié)構(gòu)的特點 這是一個多分支選擇結(jié)構(gòu)，根據(jù)表達式的值決定執(zhí)行路線。虛線框內(nèi)的結(jié)構(gòu)是一個入口一個出口，并且有上述全部的四個特點。由此構(gòu)成的算法結(jié)構(gòu)也是結(jié)構(gòu)化的算法。可以認為這是由三種基本結(jié)構(gòu)所派生出來的。小結(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)。小結(jié)：一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的。在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本結(jié)構(gòu)范圍之內(nèi)(如循環(huán)

12、中流程的跳轉(zhuǎn))；一 個非結(jié)構(gòu)化的算法可以用一個等價的結(jié)構(gòu)化算法代替，其功能不變 。如果一個算法不能分解為若干個基本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化的算法。 3、結(jié)構(gòu)化程序設(shè)計的優(yōu)點一個結(jié)構(gòu)化程序 就是用高級語言表示的結(jié)構(gòu)化算法。用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、便于閱讀、便于修改和維護。結(jié)構(gòu)化程序設(shè)計強調(diào)程序設(shè)計風格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。4、結(jié)構(gòu)化程序設(shè)計方法的基本思路把一個復(fù)雜問題的求解過程 分階段進行，每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。 采取以下方法來保證得到結(jié)構(gòu)化的程序：自頂向下；逐步細化；模塊化設(shè)計；結(jié)構(gòu)化編碼。兩種不同的方法：自頂向下，逐步細化；自下而上，逐步積累。 用這種方法逐步分解，直到作者認