第2章　算法——程序的靈魂

2.1　復(fù)習(xí)筆記

一、概述

一個(gè)程序主要包括以下兩方面的信息：

（1）對(duì)數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)（data structure）。

（2）對(duì)操作的描述，即算法（algorithm）。

二、算法概述

1算法定義

廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱(chēng)為“算法”。

2算法分類(lèi)

（1）數(shù)值運(yùn)算算法，數(shù)值運(yùn)算的目的是求數(shù)值解。

（2）非數(shù)值運(yùn)算算法。

三、算法的特性

1有窮性

一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。

2確定性

算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。

3有零個(gè)或多個(gè)輸入

輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。

4有一個(gè)或多個(gè)輸出

算法的目的是為了求解，“解”是指輸出。

5有效性

算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。

四、怎樣表示一個(gè)算法

1用自然語(yǔ)言表示算法

自然語(yǔ)言是指人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，其特點(diǎn)是通俗易懂，但語(yǔ)義語(yǔ)法不嚴(yán)格，描述能力不足。

2用流程圖表示算法

（1）概述

美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI規(guī)定了一些常用的流程圖符號(hào)（如圖2-1所示），已為世界各國(guó)程序工作者普遍采用。

圖2-1　常用的流程圖符號(hào)

（2）流程圖元素

①菱形框

菱形框的作用是對(duì)一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立決定如何執(zhí)行其后的操作。它有一個(gè)入口，兩個(gè)出口，如圖2-2所示。

圖2-2　菱形框

②連接點(diǎn)

連接點(diǎn)（小圓圈）是用于將畫(huà)在不同地方的流程線連接起來(lái)，如圖2-3所示。

圖2-3　連接點(diǎn)

③注釋框

注釋框不是流程圖中必要的部分，不反映流程和操作，只是為了對(duì)流程圖中某些框的操作作必要的補(bǔ)充說(shuō)明，以幫助閱讀流程圖的人更好地理解流程圖的作用。

（3）流程圖組成

①表示相應(yīng)操作的框；

②帶箭頭的流程線；

③框內(nèi)外必要的文字說(shuō)明。

3三種基本結(jié)構(gòu)和改進(jìn)的流程圖

（1）傳統(tǒng)流程圖的弊端

傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制。

（2）三種基本結(jié)構(gòu)

①順序結(jié)構(gòu)

如圖2-4所示，虛線框內(nèi)是一個(gè)順序結(jié)構(gòu)。其中A和B兩個(gè)框是順序執(zhí)行的。順序結(jié)構(gòu)是最簡(jiǎn)單的一種基本結(jié)構(gòu)。

圖2-4　順序結(jié)構(gòu)

②選擇結(jié)構(gòu)

選擇結(jié)構(gòu)又稱(chēng)選取結(jié)構(gòu)或分支結(jié)構(gòu)，如圖2-5所示。虛線框內(nèi)是一個(gè)選擇結(jié)構(gòu)，此結(jié)構(gòu)中必包含一個(gè)判斷框，根據(jù)給定的條件P是否成立而選擇執(zhí)行A框或B框。

圖2-5　選擇結(jié)構(gòu)

③循環(huán)結(jié)構(gòu)

又稱(chēng)重復(fù)結(jié)構(gòu)，即反復(fù)執(zhí)行某一部分的操作，有兩類(lèi)循環(huán)結(jié)構(gòu)，如圖2-6所示。

圖2-6　循環(huán)結(jié)構(gòu)

（3）三種結(jié)構(gòu)共同特點(diǎn)

①只有一個(gè)入口；

②只有一個(gè)出口；

③結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到；

④結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。

基本結(jié)構(gòu)并不一定只限于上面3種，只要具有上述4個(gè)特點(diǎn)的都可以作為基本結(jié)構(gòu)。如圖2-7為經(jīng)典的do…while循環(huán)結(jié)構(gòu)、而圖2-8為經(jīng)典的switch選擇結(jié)構(gòu)。

圖2-7　do…while循環(huán)結(jié)構(gòu)

圖2-8　switch選擇結(jié)構(gòu)

4用N-S流程圖表示算法

（1）概述

在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫(xiě)在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他從屬于它的框，或者說(shuō)，由一些基本的框組成一個(gè)大的框，這種流程圖又稱(chēng)N-S結(jié)構(gòu)化流程圖。

（2）N-S流程圖符號(hào)

①順序結(jié)構(gòu)

順序結(jié)構(gòu)用圖2-9形式表示。A和B兩個(gè)框組成一個(gè)順序結(jié)構(gòu)。

圖2-9　順序結(jié)構(gòu)

②選擇結(jié)構(gòu)

選擇結(jié)構(gòu)用圖2-10表示，其中p為判斷條件。

圖2-10　選擇結(jié)構(gòu)

③循環(huán)結(jié)構(gòu)

當(dāng)型循環(huán)結(jié)構(gòu)用圖2-11形式表示，當(dāng)p₁條件成立時(shí)反復(fù)執(zhí)行A操作，直到p₁條件不成立為止。

圖2-11　當(dāng)型循環(huán)結(jié)構(gòu)

直到型循環(huán)結(jié)構(gòu)用圖2-12形式表示，先執(zhí)行A操作，然后判斷p₁條件是否成立，如果p₁成立，反復(fù)執(zhí)行A，只當(dāng)p₁條件不成立才停止循環(huán)。

圖2-12　直到型循環(huán)結(jié)構(gòu)

5用偽代碼表示算法

（1）概述

偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。

（2）特點(diǎn)

①偽代碼書(shū)寫(xiě)格式比較自由，容易表達(dá)出設(shè)計(jì)者的思想；

②用偽代碼寫(xiě)的算法很容易修改；

③用偽代碼很容易寫(xiě)出結(jié)構(gòu)化的算法。

6用計(jì)算機(jī)語(yǔ)言表示算法

用流程圖或偽代碼描述一個(gè)算法后，還要將它轉(zhuǎn)換成計(jì)算機(jī)語(yǔ)言程序。用計(jì)算機(jī)語(yǔ)言表示的算法是計(jì)算機(jī)能夠執(zhí)行的算法，其必須嚴(yán)格遵循所用語(yǔ)言的語(yǔ)法規(guī)則。

五、結(jié)構(gòu)化程序設(shè)計(jì)方法

1基本思路

結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是：把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段進(jìn)行，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。

2結(jié)構(gòu)化程序設(shè)計(jì)方法

（1）自頂向下

（2）逐步細(xì)化

（3）模塊化設(shè)計(jì)

（4）結(jié)構(gòu)化編碼