### 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 章會 告訴大家,有一些看似簡單的問題實際上不存在算法,而另一些問題雖然有算法但需要天文 數字的時間和空間來完成計算,從而毫無實際價值。
- 前言
- 第 1 章 計算與計算思維
- 1.1 什么是計算?
- 1.1.1 計算機與計算
- 1.1.2 計算機語言
- 1.1.3 算法
- 1.1.4 實現
- 1.2 什么是計算思維?
- 1.2.1 計算思維的基本原則
- 1.2.2 計算思維的具體例子
- 1.2.3 日常生活中的計算思維
- 1.2.4 計算思維對其他學科的影響
- 1.3 初識 Python
- 1.3.1 Python 簡介
- 1.3.2 第一個程序
- 1.3.3 程序的執行方式
- 1.3.4 Python 語言的基本成分
- 1.4 程序排錯
- 1.5 練習
- 第 2 章 用數據表示現實世界
- 2.1 數據和數據類型
- 2.1.1 數據是對現實的抽象
- 2.1.1 常量與變量
- 2.1.2 數據類型
- 2.1.3 Python 的動態類型*
- 2.2 數值類型
- 2.2.1 整數類型 int
- 2.2.2 長整數類型 long
- 2.2.3 浮點數類型 float
- 2.2.4 數學庫模塊 math
- 2.2.5 復數類型 complex*
- 2.3 字符串類型 str
- 2.3.1 字符串類型的字面值形式
- 2.3.2 字符串類型的操作
- 2.3.3 字符的機內表示
- 2.3.4 字符串類型與其他類型的轉換
- 2.3.5 字符串庫 string
- 2.4 布爾類型 bool
- 2.4.1 關系運算
- 2.4.2 邏輯運算
- 2.4.3 布爾代數運算定律*
- 2.4.4 Python 中真假的表示與計算*
- 2.5 列表和元組類型
- 2.5.1 列表類型 list
- 2.5.2 元組類型 tuple
- 2.6 數據的輸入和輸出
- 2.6.1 數據的輸入
- 2.6.2 數據的輸出
- 2.6.3 格式化輸出
- 2.7 編程案例:查找問題
- 2.8 練習
- 第 3 章 數據處理的流程控制
- 3.1 順序控制結構
- 3.2 分支控制結構
- 3.2.1 單分支結構
- 3.2.2 兩路分支結構
- 3.2.3 多路分支結構
- 3.3 異常處理
- 3.3.1 傳統的錯誤檢測方法
- 3.3.2 傳統錯誤檢測方法的缺點
- 3.3.3 異常處理機制
- 3.4 循環控制結構
- 3.4.1 for 循環
- 3.4.2 while 循環
- 3.4.3 循環的非正常中斷
- 3.4.4 嵌套循環
- 3.5 結構化程序設計
- 3.5.1 程序開發過程
- 3.5.2 結構化程序設計的基本內容
- 3.6 編程案例:如何求 n 個數據的最大值?
- 3.6.1 幾種解題策略
- 3.6.2 經驗總結
- 3.7 Python 布爾表達式用作控制結構*
- 3.8 練習
- 第 4 章 模塊化編程
- 4.1 模塊化編程基本概念
- 4.1.1 模塊化設計概述
- 4.1.2 模塊化編程
- 4.1.3 編程語言對模塊化編程的支持
- 4.2 Python 語言中的函數
- 4.2.1 用函數減少重復代碼 首先看一個簡單的用字符畫一棵樹的程序:
- 4.2.2 用函數改善程序結構
- 4.2.3 用函數增強程序的通用性
- 4.2.4 小結:函數的定義與調用
- 4.2.5 變量的作用域
- 4.2.6 函數的返回值
- 4.3 自頂向下設計
- 4.3.1 頂層設計
- 4.3.2 第二層設計
- 4.3.3 第三層設計
- 4.3.4 第四層設計
- 4.3.5 自底向上實現與單元測試
- 4.3.6 開發過程小結
- 4.4 Python 模塊*
- 4.4.1 模塊的創建和使用
- 4.4.2 Python 程序架構
- 4.4.3 標準庫模塊
- 4.4.4 模塊的有條件執行
- 4.5 練習
- 第 5 章 圖形編程
- 5.1 概述
- 5.1.1 計算可視化
- 5.1.2 圖形是復雜數據
- 5.1.3 用對象表示復雜數據
- 5.2 Tkinter 圖形編程
- 5.2.1 導入模塊及創建根窗口
- 5.2.2 創建畫布
- 5.2.3 在畫布上繪圖
- 5.2.4 圖形的事件處理
- 5.3 編程案例
- 5.3.1 統計圖表
- 5.3.2 計算機動畫
- 5.4 軟件的層次化設計:一個案例
- 5.4.1 層次化體系結構
- 5.4.2 案例:圖形庫 graphics
- 5.4.3 graphics 與面向對象
- 5.5 練習
- 第 6 章 大量數據的表示和處理
- 6.1 概述
- 6.2 有序的數據集合體
- 6.2.1 字符串
- 6.2.2 列表
- 6.2.3 元組
- 6.3 無序的數據集合體
- 6.3.1 集合
- 6.3.2 字典
- 6.4 文件
- 6.4.1 文件的基本概念
- 6.4.2 文件操作
- 6.4.3 編程案例:文本文件分析
- 6.4.4 緩沖
- 6.4.5 二進制文件與隨機存取*
- 6.5 幾種高級數據結構*
- 6.5.1 鏈表
- 6.5.2 堆棧
- 6.5.3 隊列
- 6.6 練習
- 第 7 章 面向對象思想與編程
- 7.1 數據與操作:兩種觀點
- 7.1.1 面向過程觀點
- 7.1.2 面向對象觀點
- 7.1.3 類是類型概念的發展
- 7.2 面向對象編程
- 7.2.1 類的定義
- 7.2.2 對象的創建
- 7.2.3 對象方法的調用
- 7.2.4 編程實例:模擬炮彈飛行
- 7.2.5 類與模塊化
- 7.2.6 對象的集合體
- 7.3 超類與子類*
- 7.3.1 繼承
- 7.3.2 覆寫
- 7.3.3 多態性
- 7.4 面向對象設計*
- 7.5 練習
- 第 8 章 圖形用戶界面
- 8.1 圖形用戶界面概述
- 8.1.1 程序的用戶界面
- 8.1.2 圖形界面的組成
- 8.1.3 事件驅動
- 8.2 GUI 編程
- 8.2.1 UI 編程概述
- 8.2.2 初識 Tkinter
- 8.2.3 常見 GUI 構件的用法
- 8.2.4 布局
- 8.2.5 對話框*
- 8.3 Tkinter 事件驅動編程
- 8.3.1 事件和事件對象
- 8.3.2 事件處理
- 8.4 模型-視圖設計方法
- 8.4.1 將 GUI 應用程序封裝成對象
- 8.4.2 模型與視圖
- 8.4.3 編程案例:匯率換算器
- 8.5 練習
- 第 9 章 模擬與并發
- 9.1 模擬
- 9.1.1 計算機建模
- 9.1.2 隨機問題的建模與模擬
- 9.1.3 編程案例:乒乓球比賽模擬
- 9.2 原型法
- 9.3 并行計算*
- 9.3.1 串行、并發與并行
- 9.3.2 進程與線程
- 9.3.3 多線程編程的應用
- 9.3.4 Python 多線程編程
- 9.3.5 小結
- 9.4 練習
- 第 10 章 算法設計和分析
- 10.1 枚舉法
- 10.2 遞歸
- 10.3 分治法
- 10.4 貪心法
- 10.5 算法分析
- 10.5.1 算法復雜度
- 10.5.2 算法分析實例
- 10.6 不可計算的問題
- 10.7 練習
- 第 11 章 計算+X
- 11.1 計算數學
- 11.2 生物信息學
- 11.3 計算物理學
- 11.4 計算化學
- 11.5 計算經濟學
- 11.6 練習
- 附錄
- 1 Python 異常處理參考
- 2 Tkinter 畫布方法
- 3 Tkinter 編程參考
- 3.1 構件屬性值的設置
- 3.2 構件的標準屬性
- 3.3 各種構件的屬性
- 3.4 對話框
- 3.5 事件
- 參考文獻