### 1.1.3 算法 如前所述，程序是解決某個問題的指令序列。編程解決一個問題時，首先要找出解決問 題的方法，該解決方法一般先以非形式化的方式表述為由一系列可行的步驟組成的過程，然 后才用形式化的編程語言去實現該過程。這種解決特定問題的、由一系列明確而可行的步驟 組成的過程，稱為算法（algorithm①）。算法表達了解決問題的核心步驟，反映的是程序的解 題邏輯。 算法其實并不是隨著計算機的發明才出現的東西。例如，早在兩千多年前，古希臘數學 家歐幾里德就發明了一種求兩個自然數的最大公約數的過程，這個過程被認為是史上第一個 算法②： 【歐幾里德算法】 ``` 輸入：自然數 a、b 輸出：a、b 的最大公約數 步驟： 第 1 步：令 r 為 a / b 所得余數 第 2 步：若 r = 0，則算法結束，b 即為答案；否則置 a←b，b←r，轉到第 1 步。 ``` 又如，我們在小學學習的豎式乘法、長除法等等其實也都是算法的例子，都是通過明確 定義的一步一步的過程來解決問題。 利用計算機解決問題的關鍵就在于設計出合適的算法，當今計算機在各行各業中的成功 應用從根本上說都取決于高效算法的發現。例如，數學家發明了“充電放電”算法，從而利 用計算機證明了著名的四色定理。又如，谷歌公司的創建者發明了更合理的網頁相關性排名 算法，從而使 Google 成為最成功的搜索引擎。其他如 MP3 播放器等便攜式電子產品依靠聰 明的音頻視頻壓縮算法來節省存儲空間，GPS 導航儀利用高效的最短路徑算法來規劃最短路 線等等，不一而足。 算法是由一系列步驟構成的計算過程，但并不是隨便用一些步驟都能構成合格的算法 的。我們對算法有兩個要求：第一，每個步驟必須具備明確的可操作性；第二，構成算法的 所有步驟必須能在有限時間內完成。 先看算法步驟的可操作性。從最底層來看，計算機指令集中的基本指令顯然具有可操作 性，因為 CPU 確定無疑地能夠執行這些指令。然而，由于用簡單的機器指令來表達算法步驟 會使得算法瑣碎冗長，不能凸顯算法表達的解題邏輯，所以實際上我們會用更高級別的操作 來表達算法步驟。打個比方，如果在菜譜中使用非常細節化的指令，那么在很多菜的菜譜中 都會看到這樣的步驟： ``` …… 冷水入鍋 點火將水燒開 某蔬菜入鍋 等水再次燒開 撈出蔬菜備用 …… ``` 這種步驟雖然詳細，但太瑣碎了。幾乎沒有菜譜會在這樣的細節級別上表達操作步驟，一般 都會將這個過程寫做： ``` …… 將某蔬菜綽水 …… ``` > ① 這個詞源自 9 世紀波斯數學家 Muhammad ibn Musa al-Khwarizmi 的姓（拉丁語寫法 Algorismus）。 > ② 中國稱為輾轉相除法。 其中“綽水”是一個較高級別的指令，它本身又由若干更細節化的步驟組成，但它顯然是一 個明確定義的步驟，按照這樣的菜譜去做菜，完全是可操作的。 再以數學為例，“計算 b2 - 4ac”作為算法中的一個步驟顯然是可操作的，沒有必要細化 為“先計算 b2，再計算 4ac，再兩者相減”的步驟；而“作一條平行于直線 AB 的直線”就 不是一個明確的步驟。至于“用尺規作圖來三等分角DAOB”，則根本就是一個不可能做到的 操作，盡管其意義是明確的。 總之，在設計算法時，要選擇合適的細節級別的步驟，不但要確保所有步驟處于計算機 能力范圍之內，還應該使算法的讀者容易理解算法的邏輯。 再看算法的有限性。只滿足算法步驟的可操作性是不夠的，一個合格的算法還必須能在 有限時間內執行完畢。例如，具備一點數論知識的人都知道“檢查自然數 n 是不是質數”是 可行的步驟，例如可以逐個檢查從 2 到 n/2 的自然數是不是 n 的因子。那我們能不能設計如 下“算法”來生成所有質數呢？ ``` 第 1 步：令 n = 2 第 2 步：檢查 n 是不是質數 第 3 步：如果是就輸出 n 第 4 步：n = n + 1，轉到第 2 步 ``` 很遺憾，這不是一個合格的算法，因為自然數有無窮多個，導致“算法”的第 4 步是可 以無限進行下去的。 那么對一個給定的問題，能不能找到符合上述要求的算法呢？這其實正是計算機科學要 回答的一個基本問題：什么是可計算的？如果能夠為某個問題找到算法，該問題就稱為可計 算的。當然，如果沒能找到算法，并不意味著該問題不可計算，那也許只是因為我們不夠聰 明而已。事實上，計算機科學還從理論上對可計算性和計算復雜性進行分析。本書第 x 章會 告訴大家，有一些看似簡單的問題實際上不存在算法，而另一些問題雖然有算法但需要天文 數字的時間和空間來完成計算，從而毫無實際價值。