算法

2019-11-17 05:20:48

字體：大中小

來源：轉載

供稿：網友

　　什么是程序？程序= 數據結構+ 算法。對于面向對象程序設計，強調的是數據結構，而對于面向過程的程序設計語言如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時執行Ｄ。
算法（圖八）