<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                ### 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&gt;b 后,也許不能得出最大值是哪個數據,但肯定可以推知某個數據不是 最大值。因為若 a 大于 b,則 b 不可能是最大值;否則 a 不可能是最大值。后續的比較測試 可以充分利用這個信息,以避免冗余測試。根據這個思路,我們可以將所有測試安排一個合 理的順序,以便排在后面的測試能夠利用前面測試的信息。判定樹方法就是這么一種安排測 試順序的常用方法。假設我們從測試 x1&gt;=x2 開始,如果這個比較運算結果為真,那么接下 去只需要測試 x1 與 x3 的大小,否則只需要比較 x2 和 x3 的大小。可見,每一次測試都產生 兩個分支,每個分支又是一次測試,又產生兩個分支。如此繼續下去,最終形成一個層次結 構,稱為判定樹(見圖 3.12)。 ![](https://box.kancloud.cn/2016-02-22_56cafcde62c2e.png) 圖 3.12 判定樹 我們很容易根據判定樹作出程序的流程圖,并進而轉化成 if-else 語句: ``` if x1 &gt;= x2: if x1 &gt;= x3: max = x1 else: max = x3 else: if x2 &gt;= 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 &gt; 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) ``` 當然,這簡直已稱不上是一個算法,對我們學習程序設計沒什么幫助。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看