### 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) ``` 當然，這簡直已稱不上是一個算法，對我們學習程序設計沒什么幫助。