### 3.6.1 幾種解題策略
如前所述,對于復雜問題,能夠設計出多種多樣的算法,并且這些算法各有好壞的不同。
下面我們將對上述最大值問題給出四種解決方法,并討論每一種策略的好壞。
策略 1:將每個數值與其他兩個數值進行比較 由于最大值比其他所有數值都大,所以求最大值的最直接的思路就逐一檢查 x1、x2 和x3,看看哪個數值比另外兩個數值大。又由于 x1、x2 和 x3 都有可能是最大值,我們可以用 一個三路分支的 if-elif 語句來求解:
```
if x1 >= x2 and x1 >= x3:
max = x1
elif x2 >= x1 and x2 >= x3:
max = x2
else:
max = x3
```
分析一下這條 if 語句,可以看出它用到了兩個布爾表達式,而每個布爾表達式又是用 and 聯結起來的兩個比較運算式,因此可能要經過四次比較運算才能得出最大值。看上去沒什么 復雜,但這個算法其實是很不好的。考慮從 4 個數值中求最大值的問題,用這個算法就會需
要 3 個布爾表達式,每個表達式都包含用 and 聯結的 3 個比較運算式,可能要經過 9 次比較 運算才能得出最大值。對于 n 很大的情形,這個算法最壞需要(n-1)2 次比較才能得到結果, 效率很差,另外在代碼形式上也會很難看(用 and 聯結起來的 n-1 個比較運算式的長度遠遠 超出了屏幕上一行的寬度)。
上述算法的問題在于:對每個數據的檢測是獨立設計的,一個數據的測試信息不會被后 面的測試利用。例如,假設第一個分支發現 x1 大于 x2 但小于 x3,這時我們能夠推知 x3 是 最大值。但是上述代碼卻完全忽略這個信息,只是進入第二個分支繼續檢測,直至到第三個 分支才得出 x3 是最大值。
策略 2:判定樹
執行比較運算 a>b 后,也許不能得出最大值是哪個數據,但肯定可以推知某個數據不是 最大值。因為若 a 大于 b,則 b 不可能是最大值;否則 a 不可能是最大值。后續的比較測試 可以充分利用這個信息,以避免冗余測試。根據這個思路,我們可以將所有測試安排一個合 理的順序,以便排在后面的測試能夠利用前面測試的信息。判定樹方法就是這么一種安排測 試順序的常用方法。假設我們從測試 x1>=x2 開始,如果這個比較運算結果為真,那么接下 去只需要測試 x1 與 x3 的大小,否則只需要比較 x2 和 x3 的大小。可見,每一次測試都產生 兩個分支,每個分支又是一次測試,又產生兩個分支。如此繼續下去,最終形成一個層次結 構,稱為判定樹(見圖 3.12)。

圖 3.12 判定樹
我們很容易根據判定樹作出程序的流程圖,并進而轉化成 if-else 語句:
```
if x1 >= x2:
if x1 >= x3:
max = x1
else:
max = x3
else:
if x2 >= x3:
max = x2
else:
max = x3
```
分析一下圖 3.12 中的判定樹(或者分析上面的 if 語句也一樣)即可發現,為了求得最大 值,只需沿著自頂向下的某一條測試路徑走到底即可,而任一路徑上的比較運算次數都是兩 次。所以,不管三個數值的大小次序是什么,上述算法都只進行兩次比較運算,就能得出最 大值。效率與第一種策略要高。但是,這個方法導致的代碼結構更加復雜,仍然不適合處理 較大的 n。例如,如果是求 4 個數據中的最大值,就會導致 3 重嵌套的 if-else 語句。
策略 3:順序處理
前面兩種策略都不適合對很多數據求最大值。還有更好的方法嗎?
在為一個問題設計算法時,建議讀者可以先問問自己:如果是你,你會如何解決該問題。 就此例而言,對于找三個數的最大值問題,你可能不會費腦筋多想,因為只需看看三個數值 就知道最大值了。但是如果交給你一本數據記錄,其中有成千上萬的數據,而且沒有特定順 序,你又會怎么找出其中的最大值呢?
相信你一定會想出這個簡單的策略:從頭到尾逐一檢查每個數值,心中記住當前見過的 最大值;每當遇到更大的數值,就用它替換心中所記的數值。這樣,等到所有數據都檢查過 了,最后記在心里的就是最大值。
將這個策略寫成計算機算法,只需用一個變量(用 max 就好)來記錄當前見過的最大值。 當處理完所有數據,max 中存放的就是全體數據中的最大值。下面的代碼是三個數據的版本:
```
max = x1
if x2 > max:
max = x2
if x3 > max:
max = x3
```
分析一下這個順序處理策略可知,它只需要進行兩次比較運算就能得到最大值,這一點和第二種策略一樣。但是順序處理策略的代碼比第二種策略簡單得多,不需要嵌套的 if 語句。 更重要的是,這個策略是可擴展的,能夠推廣到任意 n 個數據的情形而不降低效率。例如, 如果有 4 個數據,我們只需增加一行語句:
```
max = x1
if x2 > max:
max = x2
if x3 > max:
max = x3
if x4 > max:
max = x4
```
或者更簡潔地用一個循環來表示,那樣連數據變量也可以公用,無需使用 4 個獨立變量。 將上述算法推廣到對任意 n 個數據求最大值的情形,即可得到一般的求最大值的程序。
代碼如下:
【程序 3.12】maxn.py
```
n = input("How many numbers? ")
max = input("Input a number: ")
for i in range(n-1):
x = input("Input a number: ")
if x > max:
max = x
print "max =", max
```
不難看出,為了從 n 個數據中求得最大值,這個程序只需要執行 n-1 次比較運算。
策略 4:利用現成代碼
最后值得一提的是,Python 其實有一個內建函數 max,其功能就是返回若干個數據中的 最大值。如果使用這個函數,代碼就簡單到了極致,在交互環境下就能方便地解決問題:
```
>>> x1,x2,x3 = input("Input three numbers: ")
>>> print "max =", max(x1,x2,x3)
```
當然,這簡直已稱不上是一個算法,對我們學習程序設計沒什么幫助。
- 前言
- 第 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 事件
- 參考文獻