什么是程序？程序= 數(shù)據(jù)結(jié)構(gòu)+ 算法。

對(duì)于面向?qū)ο蟪绦蛟O(shè)計(jì)，強(qiáng)調(diào)的是數(shù)據(jù)結(jié)構(gòu)，而對(duì)于面向過(guò)程的程序設(shè)計(jì)語(yǔ)言如C、P a s c a l、F O RT R A N等語(yǔ)言，主要關(guān)注的是算法。掌握算法，也是為面向?qū)ο蟪绦蛟O(shè)計(jì)打下一個(gè)扎實(shí)的基礎(chǔ)。那么，什么是算法呢？

人們使用計(jì)算機(jī)，就是要利用計(jì)算機(jī)處理各種不同的問(wèn)題，而要做到這一點(diǎn)，人們就必須事先對(duì)各類問(wèn)題進(jìn)行分析，確定解決問(wèn)題的具體方法和步驟，再編制好一組讓計(jì)算機(jī)執(zhí)行的指令即程序，交給計(jì)算機(jī)，讓計(jì)算機(jī)按人們指定的步驟有效地工作。這些具體的方法和步驟，其實(shí)就是解決一個(gè)問(wèn)題的算法。根據(jù)算法，依據(jù)某種規(guī)則編寫(xiě)計(jì)算機(jī)執(zhí)行的命令序列，就是編制程序，而書(shū)寫(xiě)時(shí)所應(yīng)遵守的規(guī)則，即為某種語(yǔ)言的語(yǔ)法。

由此可見(jiàn)，程序設(shè)計(jì)的關(guān)鍵之一，是解題的方法與步驟，是算法。學(xué)習(xí)高級(jí)語(yǔ)言的重點(diǎn)，就是掌握分析問(wèn)題、解決問(wèn)題的方法，就是鍛煉分析、分解，最終歸納整理出算法的能力。與之相對(duì)應(yīng)，具體語(yǔ)言，如C語(yǔ)言的語(yǔ)法是工具，是算法的一個(gè)具體實(shí)現(xiàn)。所以在高級(jí)語(yǔ)言的學(xué)習(xí)中，一方面應(yīng)熟練掌握該語(yǔ)言的語(yǔ)法，因?yàn)樗撬惴▽?shí)現(xiàn)的基礎(chǔ)，另一方面必須認(rèn)識(shí)到算法的重要性，加強(qiáng)思維訓(xùn)練，以寫(xiě)出高質(zhì)量的程序。

下面通過(guò)例子來(lái)介紹如何設(shè)計(jì)一個(gè)算法：

[例1-4] 輸入三個(gè)數(shù)，然后輸出其中最大的數(shù)。

首先，得先有個(gè)地方裝這三個(gè)數(shù)，我們定義三個(gè)變量A、B、C，將三個(gè)數(shù)依次輸入到Ａ、B、C中，另外，再準(zhǔn)備一個(gè)M A X裝最大數(shù)。由于計(jì)算機(jī)一次只能比較兩個(gè)數(shù)，我們首先把A與B比，大的數(shù)放入M A X中，再把M A X 與C比，又把大的數(shù)放入M A X中。最后，把M A X輸出，此時(shí)M A X中裝的就是Ａ、Ｂ、C三數(shù)中最大的一個(gè)數(shù)。算法可以表

示如下：

1) 輸入A、B、C。

2) A與B中大的一個(gè)放入M A X中。

3) 把C與M A X中大的一個(gè)放入M A X中。

4) 輸出M A X，M A X即為最大數(shù)。

其中的2 )、3 )兩步仍不明確，無(wú)法直接轉(zhuǎn)化為程序語(yǔ)句，可以繼續(xù)細(xì)化：

2) 把A與B中大的一個(gè)放入M A X中，若A > B，則MAX ←A；否則MAX ←B。

3) 把C與M A X中大的一個(gè)放入M A X中，若C > M A X，則M A X←C。

于是算法最后可以寫(xiě)成：

1) 輸入A，B，C。

2) 若A > B，則MAX ←A；

否則M A X←B。

3) 若C > M A X，則M A X←C。

4) 輸出M A X，M A X即為最大數(shù)。
這樣的算法已經(jīng)可以很方便地轉(zhuǎn)化為相應(yīng)的程序語(yǔ)句了。

[例1-5] 猴子吃桃問(wèn)題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺(jué)得不過(guò)癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個(gè)，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問(wèn)這堆桃子原來(lái)有多少個(gè)？

此題粗看起來(lái)有些無(wú)從著手的感覺(jué)，那么怎樣開(kāi)始呢？假設(shè)第一天開(kāi)始時(shí)有a1只桃子，第二天有a2只，. . .，第9天有a9只，第1 0天是a1 0只，在a1, a2, . . .，a1 0中，只有a1 0= 1是知道的，現(xiàn)要求a1，而我們可以看出，a1, a2, . .，a1 0之間存在一個(gè)簡(jiǎn)單的關(guān)系：

a9= 2 * ( a1 0+ 1 )

a8= 2 * ( a9+ 1 )

┇

a1= 2 * ( a2+ 1 )

也就是：ai= 2 * ( ai + 1+1) i=9,8,7,6,…,1

這就是此題的數(shù)學(xué)模型。

再考察上面從a9，a8直至a1的計(jì)算過(guò)程，這其實(shí)是一個(gè)遞推過(guò)程，這種遞推的方法在計(jì)算機(jī)解題中經(jīng)常用到。另一方面，這九步運(yùn)算從形式上完全一樣，不同的只是ai的下標(biāo)而已。由此，我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)，將算法改寫(xiě)如下：

1) a1=1; ｛第1 0天的桃子數(shù)，a1的初值｝

i = 9。｛計(jì)數(shù)器初值為9｝

2) a0= 2 * ( a1+ 1 )。｛計(jì)算當(dāng)天的桃子數(shù)｝

3) a1= a0。｛將當(dāng)天的桃子數(shù)作為下一次計(jì)算的初值｝

4) i=i-1。

5) 若i > = 1，轉(zhuǎn)2 )。

6) 輸出a0的值。

其中2 )～5 )步為循環(huán)。

這就是一個(gè)從具體到抽象的過(guò)程，具體方法是：

1) 弄清如果由人來(lái)做，應(yīng)該采取哪些步驟。

2) 對(duì)這些步驟進(jìn)行歸納整理，抽象出數(shù)學(xué)模型。

3) 對(duì)其中的重復(fù)步驟，通過(guò)使用相同變量等方式求得形式的統(tǒng)一，然后簡(jiǎn)練地用循環(huán)解決。

算法的描述方法有自然語(yǔ)言描述、偽代碼、流程圖、N – S圖、PA D 圖等。

1.4.1 流程圖與算法的結(jié)構(gòu)化描述

1. 流程圖

流程圖是一種傳統(tǒng)的算法表示法，它利用幾何圖形的框來(lái)代表各種不同性質(zhì)的操作，用流程線來(lái)指示算法的執(zhí)行方向。由于它簡(jiǎn)單直觀，所以應(yīng)用廣泛，特別是在早期語(yǔ)言階段，只有通過(guò)流程圖才能簡(jiǎn)明地表述算法，流程圖成為程序員們交流的重要手段，直到結(jié)構(gòu)化的程序設(shè)計(jì)語(yǔ)言出現(xiàn)，對(duì)流程圖的依賴才有所降低。

下面介紹常見(jiàn)的流程圖符號(hào)及流程圖的例子。
本章例1 – 1的算法的流程圖如圖1 – 2所示。本章例1 – 2的算法的流程圖如圖1 – 3所示。在流程圖中，判斷框左邊的流程線表示判斷條件為真時(shí)的流程，右邊的流程線表示條件為假時(shí)的流程，有時(shí)就在其左、右流程線的上方分別標(biāo)注“真”、“假”或“T”、“F”或“Y”、“N”。

另外還規(guī)定，流程線是從下往上或從右向左時(shí)，必須帶箭頭，除此以外，都不畫(huà)箭頭，流程線的走向總是從上向下或從左向右。

2. 算法的結(jié)構(gòu)化描述

早期的非結(jié)構(gòu)化語(yǔ)言中都有g(shù) o t o語(yǔ)句，它允許程序從一個(gè)地方直接跳轉(zhuǎn)到另一個(gè)地方去。執(zhí)行這樣做的好處是程序設(shè)計(jì)十分方便靈活，減少了人工復(fù)雜度，但其缺點(diǎn)也是十分突出的，一大堆跳轉(zhuǎn)語(yǔ)句使得程序的流程十分復(fù)雜紊亂，難以看懂也難以驗(yàn)證程序的正確性，如果有錯(cuò)，排起錯(cuò)來(lái)更是十分困難。這種轉(zhuǎn)來(lái)轉(zhuǎn)去的流程圖所表達(dá)的混亂與復(fù)雜，正是軟件危機(jī)中程序人員處境的一個(gè)生動(dòng)寫(xiě)照。而結(jié)構(gòu)化程序設(shè)計(jì)，就是要把這團(tuán)亂麻理清。

經(jīng)過(guò)研究，人們發(fā)現(xiàn)，任何復(fù)雜的算法，都可以由順序結(jié)構(gòu)、選擇（分支）結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)組成，因此，我們構(gòu)造一個(gè)算法的時(shí)候，也僅以這三種基本結(jié)構(gòu)作為“建筑單元”，遵守三種基本結(jié)構(gòu)的規(guī)范，基本結(jié)構(gòu)之間可以并列、可以相互包含，但不允許交叉，不允許從一個(gè)結(jié)構(gòu)直接轉(zhuǎn)到另一個(gè)結(jié)構(gòu)的內(nèi)部去。正因?yàn)檎麄€(gè)算法都是由三種基本結(jié)構(gòu)組成的，就像用模塊構(gòu)建的一樣，所以結(jié)構(gòu)清晰，易于正確性驗(yàn)證，易于糾錯(cuò)，這種方法，就是結(jié)構(gòu)化方法。遵循這種方法的程序設(shè)計(jì)，就是結(jié)構(gòu)化程序設(shè)計(jì)。

相應(yīng)地，只要規(guī)定好三種基本結(jié)構(gòu)的流程圖的畫(huà)法，就可以畫(huà)出任何算法的流程圖。

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

順序結(jié)構(gòu)是簡(jiǎn)單的線性結(jié)構(gòu)，各框按順序執(zhí)行。其流程圖的基本形態(tài)如圖1 – 4所示，語(yǔ)句的執(zhí)行順序?yàn)椋篈→B→C。

(2) 選擇（分支）結(jié)構(gòu)

這種結(jié)構(gòu)是對(duì)某個(gè)給定條件進(jìn)行判斷，條件為真或假時(shí)分別執(zhí)行不同的框的內(nèi)容。其基本形狀有兩種，如圖1-5 a）、b）所示。圖1-5 a）的執(zhí)行序列為：當(dāng)條件為真時(shí)執(zhí)行A，否則執(zhí)行B；圖1 – 5 b）的執(zhí)行序列為：當(dāng)條件為真時(shí)執(zhí)行A，否則什么也不做。

1 、(3) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)有兩種基本形態(tài)：w h i l e型循環(huán)和d o – w h i l e型循環(huán)。
2、a. while 型循環(huán)如圖1 – 6所示。其執(zhí)行序列為：當(dāng)條件為真時(shí)，反復(fù)執(zhí)行A，一旦條件為假，跳出循環(huán)，執(zhí)行循環(huán)緊后的 語(yǔ)句。

b. do-while型循環(huán)如圖1 – 7所示。

執(zhí)行序列為：首先執(zhí)行A，再判斷條件，條件為真時(shí)，一直循環(huán)執(zhí)行A，一旦條件為假，結(jié)束循環(huán)，執(zhí)行循環(huán)緊后的下一條語(yǔ)句。

在圖1 – 6、圖1 – 7中，A被稱為循環(huán)體，條件被稱為循環(huán)控制條件。要注意的是：

1) 在循環(huán)體中，必然對(duì)條件要判斷的值進(jìn)行修改，使得經(jīng)過(guò)有限次循環(huán)后，循環(huán)一定能結(jié)束，如圖1 – 3中的i = i – 1。2) 當(dāng)型循環(huán)中循環(huán)體可能一次都不執(zhí)行，而直到型循環(huán)則至少執(zhí)行一次循環(huán)體。3) 直到型循環(huán)可以很方便地轉(zhuǎn)化為當(dāng)型循環(huán)，而當(dāng)型循環(huán)不一定能轉(zhuǎn)化為直到型循環(huán)。

例如，圖1 – 7可以轉(zhuǎn)化為圖1 – 8。

2 用N-S圖描述算法

N – S圖是另一種算法表示法，是由美國(guó)人I . N a s s i和B . S h n e i d e r m a n共同提出的，其根據(jù)是：既然任何算法都是由前面介紹的三種結(jié)構(gòu)組成，所以各基本結(jié)構(gòu)之間的流程線就是多余的，因此，N – S圖也是算法的一種結(jié)構(gòu)化描述方法。

N – S圖中，一個(gè)算法就是一個(gè)大矩形框，框內(nèi)又包含若干基本的框，三種基本結(jié)構(gòu)的N – S 圖描述如下所示：

1. 順序結(jié)構(gòu)如圖1 – 9所示，執(zhí)行順序先A后B。
2. 選擇結(jié)構(gòu)
對(duì)應(yīng)于圖1 – 5的N – S圖為圖1 – 1 0。圖1-10 a)條件為真時(shí)執(zhí)行A，條件為假時(shí)執(zhí)行B。圖1 – 1 0 b )條件為真時(shí)執(zhí)行A，為假時(shí)什么都不做。

3. 循環(huán)結(jié)構(gòu)
1) while型循環(huán)的N – S圖如圖1 – 11所示，條件為真時(shí)一直循環(huán)執(zhí)行循環(huán)體A，直到條件為假時(shí)才跳出循環(huán)。
2) do-while型循環(huán)的N – S圖如圖1 – 1 2，一直循環(huán)執(zhí)行循環(huán)體A，直到條件為假時(shí)才跳出循環(huán)。
本章例1 – 1的N – S圖如圖1 – 1 3，例1 – 2的N – S圖如圖1 – 1 4。應(yīng)該說(shuō)，N – S圖比流程圖更直觀易懂，而且相對(duì)簡(jiǎn)練一些。

3 用PAD圖描述算法
PA D（Problem Analysis Diagram），是近年來(lái)在軟件開(kāi)發(fā)中被廣泛使用的一種算法的圖形表示法，與前述的流程圖、N – S圖相比，流程圖、N – S圖都是自上而下的順序描述，而PA D圖除了自上而下以外，還有自左向右的展開(kāi)，所以，如果說(shuō)流程圖、N – S圖是一維的算法描述的話，則PA D圖就是二維的，它能展現(xiàn)算法的層次結(jié)構(gòu)，更直觀易懂。
下面是PA D圖的幾種基本形態(tài)：
1. 順序結(jié)構(gòu)：
如圖1 – 1 5所示。
2. 選擇結(jié)構(gòu)
(1) 單分支選擇，條件為真執(zhí)行A，如圖1-16 a）。
(2) 兩分支選擇，如圖1-16 b)，條件為真執(zhí)行A，為假執(zhí)行B。
(3) 多分支選擇，如圖1-16 c)，當(dāng)I = I1時(shí)執(zhí)行A，Ｉ= I2時(shí)執(zhí)行B，I = I3時(shí)執(zhí)行C，I = I4時(shí)執(zhí)行Ｄ。

3. 循環(huán)結(jié)構(gòu)
如圖1 – 1 7所示。圖1-17 a)為w h i l e型循環(huán)，圖1-17 b)為d o – w h i l e型循環(huán)。

本章例1 . 1的PA D圖如圖1 – 1 8，例1 – 2的PA D圖如圖1 – 1 9。