2.8 算法

2.8.1 算法概念

人們使用計算機，就是要利用計算機處理各種不同的問題，而要做到這一點，人們就必須事先對各類問題進行分析，確定解決問題的具體方法和步驟，再根據這些步驟，編制一組讓計算機執行的指令（即程序），讓計算機按人們指定的規則有效地工作。這些具體的方法和步驟，其實就是解決一個問題的算法。根據算法，依據某種規則編寫計算機執行的命令序列，就是編制程序，而書寫時所應遵守的規則即為某種語言的語法。由此可見，程序設計的關鍵之一是解題的方法與步驟，即算法。學習高級語言的重點和難點之一就是掌握分析問題、解決問題的方法，鍛煉分析、分解問題并最終歸納整理出算法的能力。與此相對應的，具體語言（如C語言）的語法是工具，是算法的一個具體實現。所以在高級語言的學習中，一方面應熟練掌握該語言的語法——因為它是算法實現的基礎；另一方面必須認識到算法的重要性，加強思維訓練，尋找問題的最優解決方法，以編寫出高質量的程序。

下面通過例2-8來介紹如何設計一個算法。

例2-8 設有一物體從高空墜下，每次落地后都反彈至距離原高度2/3差1m的地方，現在測得第9次反彈后的高度為2m，請編寫程序，求出該物體從多高的地方開始下墜。

問題分析：

此題粗看起來有些無從著手，但仔細分析物體的運動規律后，能找到一些蛛絲馬跡。假設物體墜落時的高度為h₀，設第1～9次反彈的高度依次為h₁，…，h₉，現在只有h₉=2是已知的，但從物體的反彈規律能找出各反彈高度之間的關系：

可進一步轉換為：,i=1,2,…,9，這就是此題的數學模型。

算法設計：

上面從h₉到h₀的計算過程，其實是一個遞推過程，這種遞推方法在計算機解題中經常用到。另外，這些遞推運算的形式完全一樣，只是h_i的下標不同而已。因此可以通過循環來處理。為了方便算法描述，統一用h₀表示上一次的反彈高度，h₁表示本次的反彈高度，算法可以詳細描述如下：

5）若i≥1，轉至步驟2。

6）輸出h₀的值。

其中第2～5步為循環，遞推計算各次反彈的高度。

上面的示例演示了一個算法的設計過程，即從具體到抽象的過程，具體方法是：

1）弄清解決問題的基本步驟。

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

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

算法的描述方法有自然語言描述、偽代碼、傳統流程圖、N-S圖及PAD圖等，自然語言描述簡單、明了，但是由于程序員之間母語的差別，妨礙了他們的正常交流，因此出現了后面四種算法描述形式，下面主要介紹流程圖描述方法。如果讀者對其他描述方法感興趣，可以參考其他資料。