什么是程序？程序= 數(shù)據(jù)結(jié)構(gòu)+ 算法。
對于面向?qū)ο蟪绦蛟O(shè)計(jì)，強(qiáng)調(diào)的是數(shù)據(jù)結(jié)構(gòu)，而對于面向過程的程序設(shè)計(jì)語言如C、P a s c a l、F O RT R A N等語言，主要關(guān)注的是算法。掌握算法，也是為面向?qū)ο蟪绦蛟O(shè)計(jì)打下一個(gè)扎實(shí)的基礎(chǔ)。那么，什么是算法呢？
人們使用計(jì)算機(jī)，就是要利用計(jì)算機(jī)處理各種不同的問題，而要做到這一點(diǎn)，人們就必須事先對各類問題進(jìn)行分析，確定解決問題的具體方法和步驟，再編制好一組讓計(jì)算機(jī)執(zhí)行的指令即程序，交給計(jì)算機(jī)，讓計(jì)算機(jī)按人們指定的步驟有效地工作。這些具體的方法和步驟，其實(shí)就是解決一個(gè)問題的算法。根據(jù)算法，依據(jù)某種規(guī)則編寫計(jì)算機(jī)執(zhí)行的命令序列，就是編制程序，而書寫時(shí)所應(yīng)遵守的規(guī)則，即為某種語言的語法。
由此可見，程序設(shè)計(jì)的關(guān)鍵之一，是解題的方法與步驟，是算法。學(xué)習(xí)高級(jí)語言的重點(diǎn)，就是掌握分析問題、解決問題的方法，就是鍛煉分析、分解，最終歸納整理出算法的能力。與之相對應(yīng)，具體語言，如C語言的語法是工具，是算法的一個(gè)具體實(shí)現(xiàn)。所以在高級(jí)語言的學(xué)習(xí)中，一方面應(yīng)熟練掌握該語言的語法，因?yàn)樗撬惴▽?shí)現(xiàn)的基礎(chǔ)，另一方面必須認(rèn)識(shí)到算法的重要性，加強(qiáng)思維訓(xùn)練，以寫出高質(zhì)量的程序。
下面通過例子來介紹如何設(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 )兩步仍不明確，無法直接轉(zhuǎn)化為程序語句，可以繼續(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。
于是算法最后可以寫成：
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)的程序語句了。
[例1-5] 猴子吃桃問題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個(gè)，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問這堆桃子原來有多少個(gè)？
此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設(shè)第一天開始時(shí)有a1只桃子，第二天有a2只，. . .，第9天有a9只，第1 0天是a1 0只，在a1, a2, . . .，a1 0中，只有a1 0= 1是知道的，現(xiàn)要求a1，而我們可以看出，a1, a2, . .，a1 0之間存在一個(gè)簡單的關(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ì)算過程，這其實(shí)是一個(gè)遞推過程，這種遞推的方法在計(jì)算機(jī)解題中經(jīng)常用到。另一方面，這九步運(yùn)算從形式上完全一樣，不同的只是ai的下標(biāo)而已。由此，我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)，將算法改寫如下：
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è)從具體到抽象的過程，具體方法是：
1) 弄清如果由人來做，應(yīng)該采取哪些步驟。
2) 對這些步驟進(jìn)行歸納整理，抽象出數(shù)學(xué)模型。
3) 對其中的重復(fù)步驟，通過使用相同變量等方式求得形式的統(tǒng)一，然后簡練地用循環(huán)解決。
算法的描述方法有自然語言描述、偽代碼、流程圖、N - S圖、PA D 圖等。
1.4.1 流程圖與算法的結(jié)構(gòu)化描述
1. 流程圖
流程圖是一種傳統(tǒng)的算法表示法，它利用幾何圖形的框來代表各種不同性質(zhì)的操作，用流程線來指示算法的執(zhí)行方向。由于它簡單直觀，所以應(yīng)用廣泛，特別是在早期語言階段，只有通過流程圖才能簡明地表述算法，流程圖成為程序員們交流的重要手段，直到結(jié)構(gòu)化的程序設(shè)計(jì)語言出現(xiàn)，對流程圖的依賴才有所降低。
下面介紹常見的流程圖符號(hào)及流程圖的例子。
本章例1 - 1的算法的流程圖如圖1 - 2所示。本章例1 - 2的算法的流程圖如圖1 - 3所示。在流程圖中，判斷框左邊的流程線表示判斷條件為真時(shí)的流程，右邊的流程線表示條件為假時(shí)的流程，有時(shí)就在其左、右流程線的上方分別標(biāo)注“真”、“假”或“T”、“F”或“Y”、“N”。
另外還規(guī)定，流程線是從下往上或從右向左時(shí)，必須帶箭頭，除此以外，都不畫箭頭，流程線的走向總是從上向下或從左向右。
2. 算法的結(jié)構(gòu)化描述
早期的非結(jié)構(gòu)化語言中都有g(shù) o t o語句，它允許程序從一個(gè)地方直接跳轉(zhuǎn)到另一個(gè)地方去。執(zhí)行這樣做的好處是程序設(shè)計(jì)十分方便靈活，減少了人工復(fù)雜度，但其缺點(diǎn)也是十分突出的，一大堆跳轉(zhuǎn)語句使得程序的流程十分復(fù)雜紊亂，難以看懂也難以驗(yàn)證程序的正確性，如果有錯(cuò)，排起錯(cuò)來更是十分困難。這種轉(zhuǎn)來轉(zhuǎn)去的流程圖所表達(dá)的混亂與復(fù)雜，正是軟件危機(jī)中程序人員處境的一個(gè)生動(dòng)寫照。而結(jié)構(gòu)化程序設(shè)計(jì)，就是要把這團(tuán)亂麻理清。
對于面向?qū)ο蟪绦蛟O(shè)計(jì)，強(qiáng)調(diào)的是數(shù)據(jù)結(jié)構(gòu)，而對于面向過程的程序設(shè)計(jì)語言如C、P a s c a l、F O RT R A N等語言，主要關(guān)注的是算法。掌握算法，也是為面向?qū)ο蟪绦蛟O(shè)計(jì)打下一個(gè)扎實(shí)的基礎(chǔ)。那么，什么是算法呢？
人們使用計(jì)算機(jī)，就是要利用計(jì)算機(jī)處理各種不同的問題，而要做到這一點(diǎn)，人們就必須事先對各類問題進(jìn)行分析，確定解決問題的具體方法和步驟，再編制好一組讓計(jì)算機(jī)執(zhí)行的指令即程序，交給計(jì)算機(jī)，讓計(jì)算機(jī)按人們指定的步驟有效地工作。這些具體的方法和步驟，其實(shí)就是解決一個(gè)問題的算法。根據(jù)算法，依據(jù)某種規(guī)則編寫計(jì)算機(jī)執(zhí)行的命令序列，就是編制程序，而書寫時(shí)所應(yīng)遵守的規(guī)則，即為某種語言的語法。
由此可見，程序設(shè)計(jì)的關(guān)鍵之一，是解題的方法與步驟，是算法。學(xué)習(xí)高級(jí)語言的重點(diǎn)，就是掌握分析問題、解決問題的方法，就是鍛煉分析、分解，最終歸納整理出算法的能力。與之相對應(yīng)，具體語言，如C語言的語法是工具，是算法的一個(gè)具體實(shí)現(xiàn)。所以在高級(jí)語言的學(xué)習(xí)中，一方面應(yīng)熟練掌握該語言的語法，因?yàn)樗撬惴▽?shí)現(xiàn)的基礎(chǔ)，另一方面必須認(rèn)識(shí)到算法的重要性，加強(qiáng)思維訓(xùn)練，以寫出高質(zhì)量的程序。
下面通過例子來介紹如何設(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 )兩步仍不明確，無法直接轉(zhuǎn)化為程序語句，可以繼續(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。
于是算法最后可以寫成：
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)的程序語句了。
[例1-5] 猴子吃桃問題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個(gè)，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問這堆桃子原來有多少個(gè)？
此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設(shè)第一天開始時(shí)有a1只桃子，第二天有a2只，. . .，第9天有a9只，第1 0天是a1 0只，在a1, a2, . . .，a1 0中，只有a1 0= 1是知道的，現(xiàn)要求a1，而我們可以看出，a1, a2, . .，a1 0之間存在一個(gè)簡單的關(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ì)算過程，這其實(shí)是一個(gè)遞推過程，這種遞推的方法在計(jì)算機(jī)解題中經(jīng)常用到。另一方面，這九步運(yùn)算從形式上完全一樣，不同的只是ai的下標(biāo)而已。由此，我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)，將算法改寫如下：
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è)從具體到抽象的過程，具體方法是：
1) 弄清如果由人來做，應(yīng)該采取哪些步驟。
2) 對這些步驟進(jìn)行歸納整理，抽象出數(shù)學(xué)模型。
3) 對其中的重復(fù)步驟，通過使用相同變量等方式求得形式的統(tǒng)一，然后簡練地用循環(huán)解決。
算法的描述方法有自然語言描述、偽代碼、流程圖、N - S圖、PA D 圖等。
1.4.1 流程圖與算法的結(jié)構(gòu)化描述
1. 流程圖
流程圖是一種傳統(tǒng)的算法表示法，它利用幾何圖形的框來代表各種不同性質(zhì)的操作，用流程線來指示算法的執(zhí)行方向。由于它簡單直觀，所以應(yīng)用廣泛，特別是在早期語言階段，只有通過流程圖才能簡明地表述算法，流程圖成為程序員們交流的重要手段，直到結(jié)構(gòu)化的程序設(shè)計(jì)語言出現(xiàn)，對流程圖的依賴才有所降低。
下面介紹常見的流程圖符號(hào)及流程圖的例子。
本章例1 - 1的算法的流程圖如圖1 - 2所示。本章例1 - 2的算法的流程圖如圖1 - 3所示。在流程圖中，判斷框左邊的流程線表示判斷條件為真時(shí)的流程，右邊的流程線表示條件為假時(shí)的流程，有時(shí)就在其左、右流程線的上方分別標(biāo)注“真”、“假”或“T”、“F”或“Y”、“N”。
另外還規(guī)定，流程線是從下往上或從右向左時(shí)，必須帶箭頭，除此以外，都不畫箭頭，流程線的走向總是從上向下或從左向右。
2. 算法的結(jié)構(gòu)化描述
早期的非結(jié)構(gòu)化語言中都有g(shù) o t o語句，它允許程序從一個(gè)地方直接跳轉(zhuǎn)到另一個(gè)地方去。執(zhí)行這樣做的好處是程序設(shè)計(jì)十分方便靈活，減少了人工復(fù)雜度，但其缺點(diǎn)也是十分突出的，一大堆跳轉(zhuǎn)語句使得程序的流程十分復(fù)雜紊亂，難以看懂也難以驗(yàn)證程序的正確性，如果有錯(cuò)，排起錯(cuò)來更是十分困難。這種轉(zhuǎn)來轉(zhuǎn)去的流程圖所表達(dá)的混亂與復(fù)雜，正是軟件危機(jī)中程序人員處境的一個(gè)生動(dòng)寫照。而結(jié)構(gòu)化程序設(shè)計(jì)，就是要把這團(tuán)亂麻理清。