分治策略-在線瀏覽
2025-02-27 11:57本頁面
【正文】 法 1： c(n)=2n1方法 2： c(n) = 2c(n/2 ) + 2。在本例中，使用方法 2比方法 1少用了 2 5％的比較次數(shù)。 當(dāng) n=2時(shí)的分治法又稱二分法。2. 解決 (Conquer)：遞歸地解各子問題。3. 合并 (bine)；將子問題的結(jié)果合并成原問題的解。如果得到的子問題相對(duì)來說還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出不用進(jìn)一步細(xì)分就可求解的子問題。v 要使分治算法效率高，關(guān)鍵在于如何分割？一般地，出于一種平衡原則，總是把大問題分成 K個(gè)規(guī)模盡可能相等的子問題，但也有例外，如求表的最大最小元問題的算法，當(dāng) n＝ 6時(shí)，等分定量成兩個(gè)規(guī)模為 3的子表 L1和L2不是最佳分割。v 有形如： ax3+bx2+cx+d=0這樣的一個(gè)一元三次方程。要求由小到大依次在同一行輸出這三個(gè)實(shí)根 (根與根之間留有空格 )，并精確到小數(shù)點(diǎn)后 4位。v 樣例v 輸入： 1 5 4 20v 輸出： 問題 3:一元三次方程求解分析v 如果精確到小數(shù)點(diǎn)后兩位，可用簡單的枚舉法：將 x從 到 （步長 ） 逐一枚舉，得到 20230個(gè) f(x)，取其值與 0最接近的三個(gè) f(x)，對(duì)應(yīng)的 x即為答案。v 直接使用求根公式，極為復(fù)雜。f(b)0。v 執(zhí)行完畢，就可以得到精確到 。因此可知：在 [100,99]、 [99,98]、 …… 、 [99， 100]、 [100， 100]這 201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能有一個(gè)根。f(a+1)0時(shí)，方程在此區(qū)間內(nèi)才有解。f(a+1)0 ，則可以利用 A中所述的二分法迅速出找出解。我們使用右邊的元素2. 在左邊和（右 1）元素開始索引3. 移除左邊的索引直到我們得到一個(gè)元素 樞元素4. 移除右邊的索引直到我們得到一個(gè)元素 樞元素5. 若索引不相交，則交換值并重復(fù)步驟 3和 46. 若索引相交，則交換樞元素值和左邊索引值7. 在子數(shù)組調(diào)用快速排序得到樞元素左右的值實(shí)例原始值第一次交換第二次交換分塊v 分塊是快速排序的關(guān)鍵步驟 :1. 在我們的快速排序的說法里， pivot選為要排序的（子）數(shù)組的最后一個(gè)元素2. 使用 index low從左邊掃描（子）數(shù)組尋找 =pivot的元素3. 當(dāng)我們得到一個(gè)元素 =pivot時(shí)，使用 index high從右邊掃描尋找 =pivot的元素4. 若 lowhigh，則交換它們的值，然后開始掃描另一對(duì)可交換的元素5. 若 low=high，則完成我們需要做的，交換 low和 pivot的值，該值位于兩個(gè)分塊之間另一個(gè)分塊的實(shí)例當(dāng)前 pivot值原先的 pivot值分塊交換pivot值交換較好的快速排序v pivot值的選擇對(duì)快速排序具有決定性的作用。但是在排序之前我們無法得到中間值。它保證分塊的每部分至少有兩個(gè)元素，提供數(shù)組至少有 4個(gè)，但是它的執(zhí)行方式通常更好。v 其他改進(jìn)：－ 從遞歸到疊代的轉(zhuǎn)化，更加有效率。v 例如： 5 2 4 6 2 3 2 6v 排序后為 6 6 5 4 3 2 2 2歸并排序的整個(gè)過程歸并過程procedure Merge(var A: ListType。 {將 A[P..Q]和 A[Q+1..R]，合并到序列 A[P..R]} var I, J, {左右子序列指針 } T: Integer。 {暫存合并的序列 } begin T:= P。 J := Q + 1。 Inc(I)。 Inc(J)。 Inc(T)。 A := Lt。二分過程procedure Merge_Sort(var A: ListType。 var Q: Integer。 {計(jì)算中間下標(biāo) Q} Merge_Sort(A, P, Q)。 {繼續(xù)對(duì)右子序列遞歸排序 } Merge(A, P, Q, R) {對(duì)左右子序列歸并 } end。 問題 6:求逆序?qū)?個(gè)數(shù)v 有一實(shí)數(shù)序列 A[1]、 A[2] 、 A[3] 、 ……A[n1] 、 A[n]，若 ij，并且 A[i]A[j]，則稱 A[i]與 A[j]構(gòu)成了一個(gè)逆序?qū)?，求?shù)列 A中逆序?qū)Φ膫€(gè)數(shù)。v 例如， 5 2 4 6 2 3 2 6，可以組成的逆序?qū)τ? （ 5 2），（ 5 4），（ 5 2），（ 5 3），（ 5 2）， （ 4 2），（ 4 3），（ 4 2）， （ 6 2），（ 6 3），（ 6 2）， （ 3 2）v 共： 12個(gè)分析v 在看完試題以后，我們不難想到一個(gè)非常簡單的算法 —— 窮舉算法，即對(duì)數(shù)組中任意的兩個(gè)元素進(jìn)行判斷，看它們是不是構(gòu)成 “逆序?qū)?”，因此這種算法的時(shí)間復(fù)雜度為 O(N2)。結(jié)論v 由于 B、 C兩個(gè)數(shù)組已經(jīng)進(jìn)行了排序，因此可以設(shè)置兩個(gè)指針進(jìn)行操作，有效的統(tǒng)計(jì) B、 C兩個(gè)數(shù)組之間的 “ 逆序?qū)?” 的個(gè)數(shù)?？紤]到我們?cè)O(shè)計(jì)的二分模型本身是遞歸定義的，所以可以將我們所建立的二分模型完全與歸并排序聯(lián)系起來。v 在這里，雖然對(duì) B、 C兩個(gè)序列當(dāng)中的元素進(jìn)行了排序，使得序列 A當(dāng)中某一部分元素的順序被打亂了，但由于求解過程是遞歸定義的，在排序之前 B、 C兩個(gè)序列各自其中的元素之間的 “ 逆序?qū)?” 個(gè)數(shù)已經(jīng)被統(tǒng)計(jì)過了，并且排不排序?qū)y(tǒng)計(jì) B、 C兩個(gè)數(shù)組之間的 “ 逆序?qū)?” 的個(gè)數(shù)不會(huì)產(chǎn)生影響?？偨Y(jié)歸納v 分治是一種解題的策略，它的基本思想是： “如果整個(gè)問題比較復(fù)雜，可
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1