分治策略-文庫吧資料
2025-01-30 11:57本頁面
【正文】 ， 3。這個整理過程可以用一個遞歸過程來實現(xiàn)。3. 左鄰括號的預(yù)算符為 “*” 或 “” 。v 樣例 :輸 入表達(dá)式 應(yīng)輸 出表達(dá)式a+b(+c) a+b+c(a*b)+c/(d*e) a*b+a/(d*e)a+b/(cd) a+b/(cd)分析對于四則運(yùn)算表達(dá)式，我們分析一下哪些括號可以去掉。v 所有變量為單個小寫字母。思考題 1: 剔除多余括號 v 輸入一個含有括號的四則運(yùn)算表達(dá)式，可能含有多余的括號，編程整理該表達(dá)式，去掉所有多余的括號，原表達(dá)式中所有變量和運(yùn)算符相對位置保持不變，并保持與原表達(dá)式等價。 ”v 分治包含 “分 ”和 “治 ”兩層含義，如何分，分后如何 “治 ”成為解決問題的關(guān)鍵所在v 不是所有的問題都可以采用分治，只有那些能將問題分成與原問題類似的子問題，并且歸并后符合原問題的性質(zhì)的問題，才能進(jìn)行分治v 分治可進(jìn)行二分，三分等等，具體怎么分，需看問題的性質(zhì)和分治后的效果。所以這個排序過程對整個問題的求解的正確性是沒有任何影響的。因為排序的過程是可以在遞歸求解子問題時就能夠完成的，算法的時間復(fù)雜度就降到了 O(nlogn)。而且這一統(tǒng)計步驟是能夠在線性時間內(nèi)完成的。 v 時間效率不盡如人意 …..v 問題出現(xiàn)在哪里呢？？ 轉(zhuǎn)換思維v 用分治怎么樣 ?v 首先將這一序列 A一分為二，分成兩個不同的序列 B、 Cv 如果求出了 B,C的逆序?qū)?,那么可由 B,C求出 A的逆序?qū)?.v 如何來統(tǒng)計序列 B和序列 C之間的 “逆序?qū)?”呢？ v 如果還按照窮舉的思想來統(tǒng)計的話，那么我們采用分治法就沒有什么意義 !!!提示v 在遞歸的求解 B、 C兩個序列中的逆序?qū)Φ膫€數(shù)以后，如果對 B、 C兩個序列當(dāng)中的元素進(jìn)行排序的話，要統(tǒng)計 B、 C兩個序列之間的 “逆序?qū)?”是非常容易的 .v 如圖v 排序前v 排序后v 在 B數(shù)組當(dāng)中，首先， B中的 6， 5， 4都與 C數(shù)組當(dāng)中的 3， 2， 2都構(gòu)成了 “逆序?qū)?”，而 2不會構(gòu)成逆序?qū)?，因?B、 C兩個數(shù)組之間構(gòu)成的逆序?qū)Φ膫€數(shù)為 3+3+3=9。v n≤10000。 end。 {繼續(xù)對左子序列遞歸排序 } Merge_Sort(A, Q + 1, R)。 begin if P R then begin {若子序列 A中不止一個元素 } Q := (P + R 1) div 2。 P, R: Integer)。 {合并后的序列賦給 A} end。 {合并后的序列的指針右移 } end。 end。 end else begin {否則右序列的首元素進(jìn)入合并序列 } Lt[t] := A[J]。 while T = R do begin{合并未完成 } if (I = Q) and ((J R) or (A[I] = A[J])) then begin Lt[t] := A[I]。 I := P。 {合并后的序列的指針 } Lt: ListType。 P, Q, R: Integer)。總是先處理最短的子數(shù)組（有限的棧大小， pop， push）－ 當(dāng)子數(shù)組足夠?。?525個元素）使用插入排序，在小問題上它更快快速排序算法 (分塊 )問題 5: 歸并排序v 已知某數(shù)列存儲在序列 A[1]， A[2]， …… ， A[n]，現(xiàn)需要采用分治策略對它們進(jìn)行從大到?。◤男〉酱螅┡判?。并且沒有自然的情況會產(chǎn)生最壞的情況。v 事實證明每個子數(shù)組的第一個，中間的和最后一個元素的中間值是上面所說的中間值的很好的替代。v 理想的 pivot值是子數(shù)組的中間值，即是排序數(shù)組的中間組成。問題 4: 快速排序v 最有效的一般目的的排序， O(n lg n)v 基本策略－ 把要排序的數(shù)據(jù)數(shù)組（或向量）分成兩個子數(shù)組這樣：v 在第一個子數(shù)組中的數(shù)據(jù)比一個已知值要小v 在第二個數(shù)組中的數(shù)據(jù)比那個值要大－ 技術(shù)上來說稱為 “分塊 ”v 已知值稱為 ‘樞元素 ’－ 一旦我們已經(jīng)分好塊，樞元素將處于它最終的位置－ 然后我們繼續(xù)把子數(shù)組分為更小的數(shù)組，直到剩余部分只有一個元素（遞歸?。┛焖倥判蛩惴?. 選擇一個元素作為樞元素。若 f(a)=0 ，解即為 a；若 f(a)即：除區(qū)間 [100， 100]外，其余區(qū)間 [a,a+1]，只有當(dāng) f(a)=0或 f(a)思路分析B、求方程的所有三個實根v 所有的根的范圍都在 100至 100之間，且根與根之差的絕對值 =1。重復(fù)執(zhí)行如下的過程： (1)若 a+b或 f((a+b)/2)=0，則可確定根為(a+b)/2并退出過程； (2)若 f(a)* f((a+b)/2)0，則由題目給出的定理可知根在區(qū)間 (a,(a+b)/2)中，故對區(qū)間重復(fù)該過程； (3)若 f(a)* f((a+b)/2)0 ，則必然有 f((a+b)/2)* f(b)0 ，根在 ((a+b)/2,b)中，對此區(qū)間重復(fù)該過程。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值分析A、當(dāng)已知區(qū)間 (a,b)內(nèi)有一個根時，用二分法求根，若區(qū)間 (a,b)內(nèi)有根，則必有 f(a)而題目已改成精度為小數(shù)點后 4位，枚舉算法時間復(fù)雜度將達(dá)不到要求。v 提示：記方程 f(x)=ax3+bx2+cx+d，若存在 2個數(shù) x1和 x2，且 x1x2， f(x1)*f(x2)0，則在 (x1， x2)之間一定有一個根。給出該方程中各項的
電大資料相關(guān)推薦
鄂ICP備17016276號-1