1.2 問題的求解過程

軟件開發的過程就是計算機求解問題的過程，使用計算機解題的核心就是進行算法設計，算法是為解決特定問題而采取的有限操作步驟，是對解決方案準確而完整的描述。

算法是精確定義的，可以認為算法是問題程序化的解決方案。

1.2.1 問題及問題的求解過程

當前情況和預期的目標不同就會產生問題，求解問題（Problem Solving）是尋找一種方法來實現目標。問題的求解過程（Problem Solving Process）是人們通過使用問題領域的知識來理解和定義問題，并憑借自身的經驗和知識去選擇和使用適當的問題求解策略、技術和工具，將一個問題的描述轉換成對問題求解的過程，如圖1-2所示。

計算機求解問題的關鍵之一是尋找一種問題求解策略（Problem Solving Strategy），得到求解問題的算法，從而得到問題的解。

一個計算機程序的開發過程就是使用計算機求解問題的過程。軟件工程（Software Engineering）將軟件開發和維護過程分成若干階段，稱為系統生命周期（System Life Cycle）或軟件生命周期。

通常把軟件生命周期劃分為：分析（Analysis）、設計（Design）、編碼（Coding or Programming）、測試（Testing）和維護（Maintenance）5個階段。前4個階段屬于開發期，最后一個階段處于運行期。

算法設計的整個過程，可以包含問題需求的說明、數學模型的擬制、算法的詳細設計、算法的正確性驗證、算法的實現、算法分析、程序測試和文檔資料的編制。在此我們只關心算法的設計和分析。

現在給出在算法設計和分析過程中所要經歷的一系列典型步驟。

（1）理解問題（Understand the Problem）：在設計算法前首先要做的就是完全理解所給出的問題。明確定義所要求解的問題，并用適當的方式表示問題。

（2）設計方案（Devise a Plan）：求解問題時，考慮從何處著手，考慮選擇何種問題求解策略和技術進行求解，以得到問題求解的算法。

（3）實現方案（Carry Out the Plan）：實現求解問題的算法，使用問題實例進行測試、驗證。

（4）回顧復查（Look Back）：檢查該求解方法是否確實求解了問題或達到了目的。

（5）評估算法，考慮該解法是否可以簡化、改進和推廣。

1.2.2 算法設計與算法表示

1. 算法問題的求解過程

算法問題的求解過程本質上與一般問題的求解過程是一致的。求解一個算法問題，需要先理解問題。通過最小閱讀對問題的描述，充分理解所求解的問題。

算法一般分為兩類：精確算法和啟發式算法。精確算法（Exact Algorithm）總能保證求得問題的解；啟發式算法（Heuristic Algorithm）通過使用某種規則、簡化或智能猜測來減少問題求解的時間。

對于最優化問題，一個算法如果致力于尋找近似解而不是最優解，被稱為近似算法（Approximation Algorithm）。如果在算法中需做出某些隨機選擇，則稱為隨機算法（Randomized Algorithm）。

2. 算法設計策略

使用計算機的問題求解策略主要指算法設計策略（Algorithm Design Strategy）（技術）。算法設計策略是使用算法解題的一般性方法，可用于解決不同計算領域的多種問題。這是創造性的活動，學習已經被實踐證明是有用的一些基本設計策略是非常有用的。值得注意的是要學習設計高效的算法。算法設計方法主要有：分治策略、貪心算法、動態規劃、回溯法、分支限界法等。我們將在后面的章節中陸續介紹。

3. 算法的表示

算法需要用一種語言來描述，算法的表示是算法思想的表示形式。顯然，用自然語言描述算法時，往往一個人認為明確的操作，另一個人卻覺得不明確或者盡管兩個人都覺得明確了，但實際上有著不同的理解，因此，算法應該用無歧義的算法描述語言來描述。

計算機語言既能描述算法，又能實際執行。在這里，我們將采用C++語言來描述算法。C++語言的優點是數據類型豐富，語句精煉，功能強，效率高，可移植性好，既能面向對象又能面向過程。用C++語言來描述算法可使整個算法結構緊湊，可讀性強，便于修改。

在課程中，有時為了更好地闡明算法的思路，我們還采用C++語言與自然語言相結合的方式來描述算法。

1.2.3 算法確認和算法分析

確認一個算法是否正確的活動稱為算法確認（Algorithm Validation），其目的在于確認一個算法是否能正確無誤地工作，即證明算法對所有可能的合法輸入都能得出正確的答案。

1. 算法證明

算法證明與算法描述語言無關。使用數學工具證明算法的正確性，稱為算法證明。有些算法證明簡單，有些算法證明困難。在本課程中，僅對算法的正確性進行一般的非形式化的討論和通過對算法的程序實現進行測試。

證明算法正確性的常用方法是數學歸納法。如【程序1-1】中求最大公約數的遞歸算法rgcd，可用數學歸納法證明如下：

設m和n是整數，0≤m<n。若m=0，則因gcd(0, n)=n，程序rgcd在m=0時返回n是正確的。歸納法假定當0≤m<n<k時，函數rgcd(m, n)能在有限時間內正確返回m和n的最大公約數，那么當0<m<n=k時，考察函數rgcd(m, n)，它將具有rgcd(n%m, m)的值。這是因為0≤n%m<m且gcd(m, n)=gcd(n%m, m)，故該值正是m和n的最大公約數，證畢。

如果要表明算法是不正確的，舉一個反例，即給出一個能夠導致算法不能正確處理的輸入實例就可以。

2. 算法測試

程序測試（Program Testing）是指對程序模塊或程序總體，輸入事先準備好的樣本數據（稱為測試用例，Test Case），檢查該程序的輸出，來發現程序存在的錯誤及判定程序是否滿足其設計要求的一項活動。

調試只能指出有錯誤，而不能指出它們不存在錯誤。測試的目的是發現錯誤，調試是診斷和糾正錯誤。大多數情況下，算法的正確性驗證是通過程序測試和調試排錯來進行的。

3. 算法分析

根據算法分析與設計的步驟，在完成算法正確性檢驗之后，要做的工作就是算法分析。

算法分析（Algorithm Analysis）是對算法利用時間資源和空間資源的效率進行研究。算法分析活動將對算法的執行時間和所需的存儲空間進行估算。算法分析不僅可以預計算法能否有效地完成任務，而且可以知道在最好、最壞和平均情況下的運算時間，對解決同一問題不同算法的優劣做出比較。

當然在算法寫成程序后，便可使用樣本數據，實際測量一個程序所消耗的時間和空間，這稱為程序的性能測量（Performance Measurement）。