算法

算法：

 什么是程序？程序= 數據結構+ 算法。

對于面向對象程序設計，強調的是數據結構，而對于面向過程的程序設計語言如C、P a s c a l、F O RT R A N等語言，主要關注的是算法。掌握算法，也是為面向對象程序設計打下一個扎實的基礎。那么，什么是算法呢？

人們使用計算機，就是要利用計算機處理各種不同的問題，而要做到這一點，人們就必須事先對各類問題進行分析，確定解決問題的具體方法和步驟，再編制好一組讓計算機執行的指令即程序，交給計算機，讓計算機按人們指定的步驟有效地工作。這些具體的方法和步驟，其實就是解決一個問題的算法。根據算法，依據某種規則編寫計算機執行的命令序列，就是編制程序，而書寫時所應遵守的規則，即為某種語言的語法。

由此可見，程序設計的關鍵之一，是解題的方法與步驟，是算法。學習高級語言的重點，就是掌握分析問題、解決問題的方法，就是鍛煉分析、分解，最終歸納整理出算法的能力。與之相對應，具體語言，如C語言的語法是工具，是算法的一個具體實現。所以在高級語言的學習中，一方面應熟練掌握該語言的語法，因為它是算法實現的基礎，另一方面必須認識到算法的重要性，加強思維訓練，以寫出高質量的程序。

下面通過例子來介紹如何設計一個算法：

[例1-4] 輸入三個數，然后輸出其中最大的數。

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

示如下：

1) 輸入A、B、C。

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

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

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

其中的2 )、3 )兩步仍不明確，無法直接轉化為程序語句，可以繼續細化：

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

3) 把C與M A X中大的一個放入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即為最大數。
這樣的算法已經可以很方便地轉化為相應的程序語句了。

[例1-5] 猴子吃桃問題：有一堆桃子不知數目，猴子第一天吃掉一半，覺得不過癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個，天天如此，到第十天早上，猴子發現只剩一只桃子了，問這堆桃子原來有多少個？

此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設第一天開始時有a1只桃子，第二天有a2只，. . .，第9天有a9只，第1 0天是a1 0只，在a1, a2, . . .，a1 0中，只有a1 0= 1是知道的，現要求a1，而我們可以看出，a1, a2, . .，a1 0之間存在一個簡單的關系：

a9= 2 * ( a1 0+ 1 )

a8= 2 * ( a9+ 1 )

┇

a1= 2 * ( a2+ 1 )

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

這就是此題的數學模型。

再考察上面從a9，a8直至a1的計算過程，這其實是一個遞推過程，這種遞推的方法在計算機解題中經常用到。另一方面，這九步運算從形式上完全一樣，不同的只是ai的下標而已。由此，我們引入循環的處理方法，并統一用a0表示前一天的桃子數，a1表示后一天的桃子數，將算法改寫如下：

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

i = 9。｛計數器初值為9｝

2) a0= 2 * ( a1+ 1 )。｛計算當天的桃子數｝

3) a1= a0。｛將當天的桃子數作為下一次計算的初值｝

4) i=i-1。

5) 若i > = 1，轉2 )。

6) 輸出a0的值。

其中2 )～5 )步為循環。

這就是一個從具體到抽象的過程，具體方法是：

1) 弄清如果由人來做，應該采取哪些步驟。

2) 對這些步驟進行歸納整理，抽象出數學模型。

3) 對其中的重復步驟，通過使用相同變量等方式求得形式的統一，然后簡練地用循環解決。

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

1.4.1 流程圖與算法的結構化描述

1. 流程圖

流程圖是一種傳統的算法表示法，它利用幾何圖形的框來代表各種不同性質的操作，用流程線來指示算法的執行方向。由于它簡單直觀，所以應用廣泛，特別是在早期語言階段，只有通過流程圖才能簡明地表述算法，流程圖成為程序員們交流的重要手段，直到結構化的程序設計語言出現，對流程圖的依賴才有所降低。

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

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

2. 算法的結構化描述

早期的非結構化語言中都有g o t o語句，它允許程序從一個地方直接跳轉到另一個地方去。執行這樣做的好處是程序設計十分方便靈活，減少了人工復雜度，但其缺點也是十分突出的，一大堆跳轉語句使得程序的流程十分復雜紊亂，難以看懂也難以驗證程序的正確性，如果有錯，排起錯來更是十分困難。這種轉來轉去的流程圖所表達的混亂與復雜，正是軟件危機中程序人員處境的一個生動寫照。而結構化程序設計，就是要把這團亂麻理清。

經過研究，人們發現，任何復雜的算法，都可以由順序結構、選擇（分支）結構和循環結構這三種基本結構組成，因此，我們構造一個算法的時候，也僅以這三種基本結構作為“建筑單元”，遵守三種基本結構的規范，基本結構之間可以并列、可以相互包含，但不允許交叉，不允許從一個結構直接轉到另一個結構的內部去。正因為整個算法都是由三種基本結構組成的，就像用模塊構建的一樣，所以結構清晰，易于正確性驗證，易于糾錯，這種方法，就是結構化方法。遵循這種方法的程序設計，就是結構化程序設計。

相應地，只要規定好三種基本結構的流程圖的畫法，就可以畫出任何算法的流程圖。

(1) 順序結構

順序結構是簡單的線性結構，各框按順序執行。其流程圖的基本形態如圖1 - 4所示，語句的執行順序為：A→B→C。

(2) 選擇（分支）結構

這種結構是對某個給定條件進行判斷，條件為真或假時分別執行不同的框的內容。其基本形狀有兩種，如圖1-5 a）、b）所示。圖1-5 a）的執行序列為：當條件為真時執行A，否則執行B；圖1 - 5 b）的執行序列為：當條件為真時執行A，否則什么也不做。

1 、(3) 循環結構循環結構有兩種基本形態：w h i l e型循環和d o - w h i l e型循環。
2、a. while 型循環如圖1 - 6所示。其執行序列為：當條件為真時，反復執行A，一旦條件為假，跳出循環，執行循環緊后的
語句。

b. do-while型循環如圖1 - 7所示。

執行序列為：首先執行A，再判斷條件，條件為真時，一直循環執行A，一旦條件為假，結束循環，執行循環緊后的下一條語句。

在圖1 - 6、圖1 - 7中，A被稱為循環體，條件被稱為循環控制條件。要注意的是：

1) 在循環體中，必然對條件要判斷的值進行修改，使得經過有限次循環后，循環一定能結束，如圖1 - 3中的i = i - 1。2) 當型循環中循環體可能一次都不執行，而直到型循環則至少執行一次循環體。3) 直到型循環可以很方便地轉化為當型循環，而當型循環不一定能轉化為直到型循環。

例如，圖1 - 7可以轉化為圖1 - 8。

2 用N-S圖描述算法

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

N - S圖中，一個算法就是一個大矩形框，框內又包含若干基本的框，三種基本結構的N - S 圖描述如下所示：

1. 順序結構如圖1 - 9所示，執行順序先A后B。
2. 選擇結構
對應于圖1 - 5的N - S圖為圖1 - 1 0。圖1-10 a)條件為真時執行A，條件為假時執行B。圖1 - 1 0 b )條件為真時執行A，為假時什么都不做。

3. 循環結構
1) while型循環的N - S圖如圖1 - 11所示，條件為真時一直循環執行循環體A，直到條件為假時才跳出循環。
2) do-while型循環的N - S圖如圖1 - 1 2，一直循環執行循環體A，直到條件為假時才跳出循環。
本章例1 - 1的N - S圖如圖1 - 1 3，例1 - 2的N - S圖如圖1 - 1 4。應該說，N - S圖比流程圖更直觀易懂，而且相對簡練一些。

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

3. 循環結構
如圖1 - 1 7所示。圖1-17 a)為w h i l e型循環，圖1-17 b)為d o - w h i l e型循環。

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

原文轉自：http://www.anti-gravitydesign.com