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

1、第二章 本章要點(diǎn)算法的概念 算法的表示結(jié)構(gòu)化程序設(shè)計(jì)方法 一個(gè)程序應(yīng)包括兩個(gè)方面的內(nèi)容:對(duì)數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure)對(duì)操作的描述：算法(algorithm)著名計(jì)算機(jī)科學(xué)家沃思提出一個(gè)公式: 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序 數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計(jì)方法語(yǔ)言工具完整的程序設(shè)計(jì)應(yīng)該是: 2.1 算法的概念 1、算法：計(jì)算機(jī)求解某一問(wèn)題而采用的具體方法和步驟，就稱(chēng)為“算法”。對(duì)同一個(gè)問(wèn)題，可有不同的解題方法和步驟 為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡(jiǎn)單，運(yùn)算步驟少。 2.1 算法的概念(1)數(shù)值運(yùn)算算法：求數(shù)值解，例如求方程的根

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

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

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

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

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

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

8、max。 (5) 計(jì)算機(jī)語(yǔ)言的算法描述如下： #include void main()int a,b,max;scanf(%d%d,&a,&b);if(ab) max=a;else max=b;printf(%d,max);例2、計(jì)算S=,寫(xiě)出其算法。(1)自然語(yǔ)言的算法描述如下：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) 計(jì)算機(jī)語(yǔ)言的算法描述如下：#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)點(diǎn)比文字描述直觀、形象、 易于理解；比傳統(tǒng)流程圖緊湊易畫(huà)。尤其是它廢除了流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成的，N-S流程圖中的上下順序就是執(zhí)行時(shí)的順序。用N-S圖表示的算法都是結(jié)構(gòu)化的算法，因?yàn)樗豢赡艹霈F(xiàn)流程無(wú)規(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)作為表示一個(gè)良好算法的基本單元。 2.3 結(jié)構(gòu)化程序設(shè)計(jì)方法三種基本結(jié)構(gòu)的圖示： 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)的圖示： 當(dāng)型(While型)循環(huán)結(jié)構(gòu) 直到型(Until型)循環(huán) 不2、三種基本結(jié)構(gòu)的共同特點(diǎn)：(1)只有一個(gè)入口； (2)只有一個(gè)出口；（請(qǐng)注意：一個(gè)菱形判斷框有兩個(gè)出口，而一個(gè)選擇結(jié)構(gòu)只有一個(gè)出口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口混淆。）(3)結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到；(4)結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無(wú)終止的循環(huán))。 圖中沒(méi)有一條從入口到出口的路徑通過(guò)A框。不正確的流程表示：流程內(nèi)的死循環(huán)擴(kuò)展：只要具有上述四個(gè)特點(diǎn)的

11、都可以作為基本結(jié)構(gòu)。可以自己定義基本結(jié)構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化程序。此圖符合基本結(jié)構(gòu)的特點(diǎn) 這是一個(gè)多分支選擇結(jié)構(gòu)，根據(jù)表達(dá)式的值決定執(zhí)行路線。虛線框內(nèi)的結(jié)構(gòu)是一個(gè)入口一個(gè)出口，并且有上述全部的四個(gè)特點(diǎn)。由此構(gòu)成的算法結(jié)構(gòu)也是結(jié)構(gòu)化的算法?？梢哉J(rèn)為這是由三種基本結(jié)構(gòu)所派生出來(lái)的。小結(jié)：由三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜的問(wèn)題。由基本結(jié)構(gòu)所構(gòu)成的算法屬于“結(jié)構(gòu)化”的算法，它不存在無(wú)規(guī)律的轉(zhuǎn)向，只在本基本結(jié)構(gòu)內(nèi)才允許存在分支和向前或向后的跳轉(zhuǎn)。小結(jié)：一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的。在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)范圍之內(nèi)(如循環(huán)

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