## 10.1 枚舉法
問題求解中常用的一種算法設計方法是枚舉策略。給定問題 P,如果知道 P 的可能解構 成一個有限集合 S = {s1, s2, ..., sn},則可以逐一列舉每個 si,檢驗它是否確實是 P 的解,這 就是枚舉法。枚舉法簡單而直接,算法容易設計實現,但當可能解集合 S 很大時,枚舉策 略的效率很差。實際使用枚舉法時,經常利用各種已知條件來從 S 中排除掉一部分不可能 情形,從而優化枚舉過程。下面通過幾個例子來說明枚舉策略在設計算法中的應用。
線性搜索
首先看一個程序設計中常見的問題——搜索(或稱查找)問題:給定數據集合 D,在 D 中查找指定數據 x。
搜索問題看上去很容易解決,一個顯而易見的做法是:反復從 D 中讀取下一個數據, 看看它是否 x,搜索結果是要么找到 x,要么發現 D 中沒有 x。然而,這個“算法”是有問 題的,因為它需要一個關鍵操作——“讀取取下一個數據”,而“下一個”未必是良定義的。 打個比方,如果一群人站成一排,當我們要從中找出張三時,可以采取按排隊次序逐個詢問 的策略。但如果這群人散亂無規則地站在一起,我們該如何循著一個有條理的過程找出張三 來呢?如何決定“下一個”要詢問的人?
可見,要想在一個數據集合中找到指定數據,就必須能夠按某種系統化的方式逐個列舉 集合元素,并與指定數據進行比較。這就是枚舉策略在搜索問題中的應用。
如果將大量數據存儲在一個列表中,則使用枚舉策略很合適,因為列表是通過位置索引 來訪問其中數據成員的,“讀取下一個數據”是良定義的操作,只要將當前位置索引加 1 即 可得下一個數據的索引。下面定義的函數 find()實現了這種搜索策略:給定數據列表 list 和 需要查找的數據 x,逐個取出 list 的成員并與 x 進行比較。如果某個成員就是 x,則返回該 成員在列表中的位置索引;如果 list 中沒有 x 則返回-1。
```
>>> def find(list,x):
for i in range(len(list)): if list[i] == x:
return i return -1
>>> find([2,4,6,8],6) 2
>>> find([2,4,6,8],7)
-1
```
find()函數對列表 list 從頭到尾進行掃描,掃描過程中檢驗每一個成員是否 x,這個算法 稱為線性搜索(linear search)算法。線性搜索算法很容易設計實現,而且當數據量不太大時,算法的性能也還可以。更重要的是,由于線性搜索是枚舉每一個數據成員,因此適用于 無序數據集合,即數據沒有按特定的大小次序排列。
然而,當數據量很大時,逐個枚舉集合中的數據就變得非常低效。這時只能通過更好地 組織數據,利用額外信息來提高搜索效率,盡量避免逐個檢查所有數據。例如,假設列表數 據從小到大有序排列,那么在枚舉過程中一旦發現當前取出的數據大于 x,就不必再繼續搜 索了,可以直接下結論說找不到 x。這種改進可以提高線性搜索算法的性能,但改善得很有 限。事實上,在數據有序的情況下,存在比線性搜索算法好得多的算法(見 10.2)。
線性搜索算法只適用于“一維”搜索空間,即所有數據排列成一排的情形。考慮在如下 矩陣中查找某個數據的問題:

這時顯然無法直接采用線性搜索算法。在類似矩陣這樣的“二維”搜索空間中,如何枚舉每 一個數據呢?這個問題其實在第 3 章中介紹循環語句時就討論過,為了遍歷(即枚舉)這樣 的二維空間,可以采用嵌套的循環語句。例如下面這個 find2D()函數實現了在 row 行、col 列的矩陣 matrix 中查找數據 x 的枚舉算法:
```
>>> def find2D(matrix,row,col,x):
for i in range(row):
for j in range(col):
if matrix[i][j] == x:
return (i+1,j+1)
return -1
>>> find2D([[1,2,3],[4,5,6]],2,3,6) (2, 3)
>>> find2D([[1,2,3],[4,5,6]],2,3,7)
-1
```
顯然,這個做法可以擴展到更多維的搜索空間,利用 n 層嵌套循環即可枚舉 n 維搜索空 間中的數據。
求解不定方程
有時問題的所有可能解并沒有像上例那樣明確地存儲在某個具體集合(如列表)中,而 是構成一個無形的搜索空間,那該如何枚舉可能解呢?這需要具體問題具體分析,根據問題 的特點設計枚舉方式。下面是一個典型的例子。
中國古代數學著作中有一道“百錢買百雞”問題:假設公雞每只 5 元錢,母雞每只 3
元錢,雞雛每三只 1 元錢,用一百元錢買了一百只雞,問公雞、母雞和雞雛各買了幾只?具 備初等代數知識的人都不難列出如下方程組來求解這個問題:
```
x + y + z = 100
5x + 3y + z/3 = 100
```
其中 x、y、z 分別表示公雞、母雞和雞雛的個數。 此方程組有三個未知數卻只有兩個方程式,屬于數學中所稱的不定方程。人工求解不定
方程通常會利用方程變形、未知數代換以及分析各種約束條件等技巧,而絕不會采用枚舉所 有可能解進行檢驗的方法,因為可能解構成的空間通常非常龐大。然而,計算機的優點恰恰 在于能夠高速地、機械地執行大量的檢驗任務,因此采用枚舉策略來解不定方程是簡單而直 接的做法。問題是如何枚舉各種可能解呢?對于百錢買百雞問題,顯然只需為三個未知數做 各種可能的賦值,然后檢查是否滿足上述兩個方程式即可。各未知數的可能值都在 100 之內(因為只買了 100 只雞),所以利用枚舉法很容易得到下列程序:
```
>>> for x in range(100):
for y in range(100):
for z in range(100):
t = x + y + z
m = 5*x + 3*y + z/3
if t == 100 and m == 100:
print "x=",x,",y=",y,",z=",z
x= 0 ,y= 25 ,z= 75
x= 3 ,y= 20 ,z= 77
x= 4 ,y= 18 ,z= 78
x= 7 ,y= 13 ,z= 80
x= 8 ,y= 11 ,z= 81
x= 11 ,y= 6 ,z= 83
x= 12 ,y= 4 ,z= 84
```
采用枚舉策略時應當盡量減小可能解集合,以便提高枚舉效率。上面這個程序的效率顯 然太差,因為三重嵌套循環實際上要枚舉 100×100×100 種 x、y、z 組合。其實稍加思考就 能找到減小需要檢驗的可能解的數目的方法。首先,不需要三層嵌套循環,因為當 x 和 y 的值給定,z 的值就確定了(即 100–x–y),沒有必要再去枚舉 z;其次,x 的可能值不超 過 20(否則錢不夠),同理 y 的可能值不超過 33;最后,依題意每種雞應當都至少買 1 只, 沒有必要考慮等于 0 的情形。將這些分析落實到編程中,即可得效率更高的代碼:
```
>>> for x in range(1,20):
for y in range(1,33):
z = 100 - x - y
m = 5*x + 3*y + z/3
if m == 100:
print "x=",x,",y=",y,",z=",z
x= 3 ,y= 20 ,z= 77
x= 4 ,y= 18 ,z= 78
x= 7 ,y= 13 ,z= 80
x= 8 ,y= 11 ,z= 81
x= 11 ,y= 6 ,z= 83
x= 12 ,y= 4 ,z= 84
```
利用問題中的各種約束條件往往可以減少搜索空間或者優化枚舉過程。例如,假設為 “百錢買百雞”問題附加一個條件“盡量多買公雞”,那么可以這樣優化算法:最外層對 x 的循環中改用 range(20,0,-1),以便盡快找到滿足條件的值,得到第一個解之后就可以 終止程序,不必再找其他解了。
通過以上例子,我們看到枚舉算法的核心思想是對問題的每一個可能解進行檢驗,看看 是否滿足特定條件,這個枚舉過程在編程時是通過循環語句和條件語句實現的。對于一些復 雜問題,如果嵌套循環的層數不確定或者層數太多,直接使用循環語句和條件語句實現枚舉 檢驗是不合適甚至不可能的,這時可以考慮采用遞歸技術(見 10.2)。
當問題規模較大時,可能解的空間也很大,采用枚舉策略會導致效率很差。但是,鑒于 枚舉算法設計簡單,調試也容易,對于規模較小的問題是很好的策略。即使對于大規模的復 雜問題,枚舉策略也可以作為整體求解算法的子算法出現。
最后總結一下采用枚舉策略設計算法的一般步驟:
(1) 確定枚舉對象、枚舉范圍和判定條件;
(2) 枚舉各可能解,逐一驗證是否所需的問題解。
(3) 盡量減小枚舉范圍,提高算法效率。
- 前言
- 第 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 事件
- 參考文獻