分治策略朱全民ppt課件-文庫(kù)吧資料
2025-05-12 08:34本頁(yè)面
【正文】 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個(gè)元素）使用插入排序，在小問題上它更快 快速排序算法 (分塊 ) 問題 5: 歸并排序 ?已知某數(shù)列存儲(chǔ)在序列 A[1]， A[2]， …… ， A[n]，現(xiàn)需要采用分治策略對(duì)它們進(jìn)行從大到小（從小到大）排序。并且沒有自然的情況會(huì)產(chǎn)生最壞的情況。 ? 事實(shí)證明每個(gè)子數(shù)組的第一個(gè)，中間的和最后一個(gè)元素的中間值是上面所說的中間值的很好的替代。 ? 理想的 pivot值是子數(shù)組的中間值，即是排序數(shù)組的中間組成。 問題 4: 快速排序 ? 最有效的一般目的的排序， O(n lg n) ? 基本策略 － 把要排序的數(shù)據(jù)數(shù)組（或向量）分成兩個(gè)子數(shù)組這樣： ? 在第一個(gè)子數(shù)組中的數(shù)據(jù)比一個(gè)已知值要小 ? 在第二個(gè)數(shù)組中的數(shù)據(jù)比那個(gè)值要大 － 技術(shù)上來說稱為“分塊” ? 已知值稱為‘樞元素’ － 一旦我們已經(jīng)分好塊，樞元素將處于它最終的位置 － 然后我們繼續(xù)把子數(shù)組分為更小的數(shù)組，直到剩余部分只有一個(gè)元素（遞歸?。? 快速排序算法 1. 選擇一個(gè)元素作為樞元素。若 f(a)=0 ，解即為 a；若f(a)即：除區(qū)間 [100， 100]外，其余區(qū)間 [a,a+1]，只有當(dāng) f(a)=0或 f(a) 思路分析 B、求方程的所有三個(gè)實(shí)根 ? 所有的根的范圍都在 100至 100之間，且根與根之差的絕對(duì)值 =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)中，故對(duì)區(qū)間重復(fù)該過程； (3)若 f(a)* f((a+b)/2)0 ，則必然有 f((a+b)/2)* f(b)0 ，根在 ((a+b)/2,b)中，對(duì)此區(qū)間重復(fù)該過程。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值 分析 A、當(dāng)已知區(qū)間 (a,b)內(nèi)有一個(gè)根時(shí)，用二分法求根，若區(qū)間 (a,b)內(nèi)有根，則必有 f(a)而題目已改成精度為小數(shù)點(diǎn)后 4位，枚舉算法時(shí)間復(fù)雜度將達(dá)不到要求。 ? 提示：記方程 f(x)=ax3+bx2+cx+d，若存在 2個(gè)數(shù) x1和x2，且 x1x2， f(x1)*f(x2)0，則在 (x1， x2)之間一定有一個(gè)根。給出該方程中各項(xiàng)的系數(shù) (a， b， c， d均為實(shí)數(shù) )，并約定該方程存在三個(gè)不同實(shí)根 (根的范圍在 100至 100之間 )，且根與根之差的絕對(duì)值 =1。 分治策略的解題思路 if 問題不可分 then begin 直接求解； 返回問題的解； end else begin 對(duì)原問題進(jìn)行分治； 遞歸對(duì)每一個(gè)分治的部分求解 歸并整個(gè)問題，得出全問題的解； end。 ? 分治求解可用一個(gè)遞歸過程來表示。 分治思想 問題 S 問題 S S的解 問題 S1 …… 問題 S2 問題 Si 問題 Sn …… S1的解 …… S2的解 Si的解 Sn的解 …… 問題的分解 子集解的合并 子問題求解 分治思想 ? 由分治法所得到的子問題與原問題具有相同的類型。若子問題足夠小，則可直接求解。 ? 其三個(gè)步驟如下； 1. 分解 (Divide)：將原問題分成一系列子問題。 證明 令 n=2k C(2K)=2C(2K1)+2 =2[2C(2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1