第5章 減治法 修改

第五章減治法1234減治法的設計思想排序問題中的減治法組合問題中的減治法5查找問題中的減治法小結子問題的規(guī)模是n/2子問題的解原問題的解原問題的規(guī)模是n（1）原問題的解只存在于其中一個較小規(guī)模的子問題中;（2）原問題的解與其中一個較小規(guī)模的解之間存在某種確定的對應關系。1減治法的設計思想對于給定的整數(shù)a和非負整數(shù)n，計算an的值應用減治技術得到如下計算方法：應用分治技術得到如下計算方法：應用分治法（例如二分法）得到的算法通常具有如下遞推式：分治法和減治法區(qū)別應用減治法（例如減半法）得到的算法通常具有如下遞推式：

所以，通常來說，應用減治法處理問題的效率是很高的，一般是O(log2n)數(shù)量級。

減治法只對一個子問題求解，并且不需要進行解的合并。應用減治法（例如減半法）得到的算法通常具有如下遞推式：

2一個簡單的例子—兩個序列的中位數(shù)問題描述：一個長度為n（n≥1）的升序序列S，處在第n/2個位置的數(shù)稱為序列S的中位數(shù)。兩個序列的中位數(shù)是他們所有元素的升序序列的中位數(shù)?，F(xiàn)有兩個等長升序序列A和B，試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列的中位數(shù)。想法：分別求出兩個序列的中位數(shù)，記為a和b；比較a和b，有下列三種情況：①a=b：則a即為兩個序列的中位數(shù)；②a<b：則中位數(shù)只能出現(xiàn)在a和b之間，在序列A中舍棄a之前的元素得到序列A1，在序列B中舍棄b之后的元素得到序列B1；③a>b：則中位數(shù)只能出現(xiàn)在b和a之間，在序列A中舍棄a之后的元素得到序列A1，在序列B中舍棄b之前的元素得到序列B1；在A1和B1中分別求出中位數(shù)，重復上述過程，直到兩個序列中只有一個元素，則較小者即為所求。2一個簡單的例子—兩個序列的中位數(shù)對于兩個給定的序列A={11,13,15,17,19},B={2,4,10,15,20}，求序列A和B的中位數(shù)的過程。步驟操作說明序列A序列B1初始序列{11,13,15,17,19}{2,4,10,15,20}2分別求中位數(shù){11,13,15,17,19}{2,4,10,15,20}315>10，結果在[10,15]之間舍棄15之后元素，{11,13,15}舍棄10之前元素，{10,15,20}4分別求中位數(shù){11,13,15}{10,15,20}513<15，結果在[11,15]之間舍棄13之前元素，{13,15}舍棄15之后元素，{10,15}6分別求中位數(shù){13,15}{10,15}710<13，結果在[10,13]之間舍棄13之后元素，{13}舍棄10之前元素，{15}8長度為1，較小者為所求{13}{15}2一個簡單的例子—兩個序列的中位數(shù)1.循環(huán)直到序列A和序列B均只有一個元素

1.1a=序列A的中位數(shù)；

1.2b=序列B的中位數(shù)；

1.3比較a和b，執(zhí)行下面三種情況之一：

1.3.1若a=b，則返回a，算法結束；

1.3.2若a<b，則在序列A中舍棄a之前的元素，在序列B中舍棄b之后的元素，轉步驟1；

1.3.3若a>b，則在序列A中舍棄a之后的元素，在序列B中舍棄b之前的元素，轉步驟1；

2.序列A和序列B均只有一個元素，返回較小者；2一個簡單的例子—兩個序列的中位數(shù)查找問題中的減治法——折半查找問題描述：應用折半查找方法在一個有序序列中查找值為k的記錄。若查找成功，返回記錄k在序列中的位置，若查找失敗，返回失敗信息。5.2查找問題中的減治法

5.2.1折半查找

5.2.2二叉查找樹折半查找——想法折半查找利用了記錄序列有序的特點，其查找過程是：取有序序列的中間記錄作為比較對象，若給定值與中間記錄相等，則查找成功；若給定值小于中間記錄，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。

[r1………rmid-1]rmid

[rmid+1………rn]如果k<rmid查找這里如果k>rmid查找這里k（mid=(1+n)/2）例：查找值為14的記錄的過程：

0123456789101112137141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=141.low=1；high=n；//設置初始查找區(qū)間2.測試查找區(qū)間［low，high］是否存在，若不存在，則查找失敗；否則3.取中間點mid=(low+high)/2;比較k與r[mid]，有以下三種情況：

3.1若k<r[mid]，則high=mid-1；查找在左半?yún)^(qū)進行，轉2；

3.2若k>r[mid]，則low=mid+1；查找在右半?yún)^(qū)進行，轉2；

3.3若k=r[mid]，則查找成功，返回記錄在表中位置mid；折半查找——算法判定樹——描述折半查找的判定過程。長度為n的判定樹的構造方法為：

（1）當n=0時，判定樹為空；（2）當n＞0時，判定樹的根結點是有序表中序號為mid=(n+1)/2的記錄，根結點的左子樹是與有序表r[1]~r[mid-1]相對應的判定樹，根結點的右子樹是與r[mid+1]~r[n]相對應的判定樹。具有11個結點的判定樹6312548111079

在表中查找任一記錄的過程，即是判定樹中從根結點到該記錄結點的路徑，和給定值的比較次數(shù)等于該記錄結點在樹中的層數(shù)。具有n個結點的判定數(shù)的深度為。5.2.2查找問題中的減治法——二叉查找樹在一個無序序列中執(zhí)行查找操作，可以將無序序列建立一棵二叉查找樹，然后在二叉查找樹中查找值為k的記錄，若查找成功，返回記錄k的存儲地址，若查找失敗，返回空指針。二叉查找樹定義？二叉查找樹查找——想法由二叉查找樹的定義，在二叉查找樹root中查找給定值k的過程是：⑴若root是空樹，則查找失敗；⑵若k＝根結點的值，則查找成功；⑶若k<根結點的值，則在root的左子樹上查找；⑷若k>根結點的值，則在root的右子樹上查找；上述過程一直持續(xù)到查找成功或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。二叉查找樹=平衡二叉樹？在二叉查找樹中查找關鍵字值為35，95的過程：5030208090858840353250302080908588403532二叉查找樹查找——實例簡述查找過程？BiNode*SearchBST(BiNode*root,intk){if(root==NULL)returnNULL；

elseif(root->data==k)

returnroot;elseif(k<root->data)

returnSearchBST(root->lchild,k);elsereturnSearchBST(root->rchild,k);}二叉查找樹查找——算法

在二叉排序樹上查找關鍵碼等于給定值的結點的過程，恰好走了一條從根結點到該結點的路徑，和給定值的比較次數(shù)等于給定值的結點在二叉排序樹中的層數(shù)，比較次數(shù)最少為1次（即整個二叉排序樹的根結點就是待查結點），最多不超過樹的深度。具有n個結點的二叉樹的深度至少是，至多是n，所以，二叉排序樹的查找性能在O(log2n)和O(n)之間。

問題：如何建立二叉查找樹？輸入數(shù)據(jù){53,78,65,17,87,09,81,15}二叉搜索樹的建立輸入數(shù)據(jù){53,78,65,17,87,09,81,15}要求：創(chuàng)建一棵二叉搜索樹53537853786553786517537865871753786509178753786581178709537865151787098135154550402510203028插入新結點28二叉搜索樹的插入每次結點的插入，都要從根結點出發(fā)搜索插入位置，然后把新結點作為葉結點插入。為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。搜索成功:樹中已有這個元素,不再插入。搜索不成功:樹中原來沒有關鍵碼等于給定值的結點，把新元素加到搜索操作停止的地方。問題2：二叉搜索樹的形態(tài)只有一種嗎？

同樣3個數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達到最大。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

1231321231231235.2.3查找問題中的減治法——選擇問題問題描述：設無序序列T=(r1,r2,…,rn)，T的第k（1≤k≤n）小元素定義為T按升序排列后在第k個位置上的元素。給定一個序列T和一個整數(shù)k，尋找T的第k小元素的問題稱為選擇問題）。將尋找第n/2小元素的問題稱為中值問題。應用：中值濾波選擇問題——想法考慮快速排序的劃分過程，一般情況下，設待劃分的序列為ri～rj，選定一個軸值對序列ri～rj進行劃分，使得比軸值小的元素都位于軸值的左側，比軸值大的元素都位于軸值的右側，假定軸值的最終位置是s，則：（1）若k=s，則rs就是第k小元素；（2）若k<s，則第k小元素一定在序列ri

～rs-1中；（3）若k>s，則第k小元素一定在序列rs+1

～rj中；無論哪種情況，或者已經得出結果，或者將選擇問題的查找區(qū)間減少一半（如果軸值恰好是序列的中值）。分治法設計思想？兩者在時間復雜度區(qū)別？選擇問題——實例以5為軸值劃分序列4<5，只在左側查找以2為軸值劃分序列4>2，只在右側查找以4為軸值劃分序列4＝4,軸值第4小元素5381469272341569872341

243

4334

找第4小的元素過程：選擇問題——算法1.設置初始查找區(qū)間：i=1;j=n;2.以ri為軸值對序列ri~rj進行一次劃分，得到軸值的位置s;3.將軸值位置s與k比較

3.1如果k等于s，則將rs作為結果返回；

3.2否則，如果k<s，則j=s-1，轉步驟2；

3.3否則，i=s+1，轉步驟2；5.3排序問題中的減治法

5.3.2堆排序

5.3.1插入排序插入排序

基本原理，每步將一個待排序的對象，按其關鍵字大小，插入到前面已經排好序的一組對象適當位置上，直到對象全部插入為止。直接插入排序(InsertSort)

基本思想：當插入第i個對象時，前面的R[1],R[2],…,R[i-1]已經排好序，此時，用R[i]的關鍵字與R[i-1],R[i-2],…的關鍵字順序進行比較，找到插入位置即將R[i]插入，原來位置上對象向后順移。直接插入排序算法INSERTSORT(rectypeR[]){inti,j;for(i=2;i<n;i++){R[0]＝R[i];j＝i-1;while(R[0].key<R[j].key)R[j+1]＝R[j--];R[j+1]＝R[0];}}算法中引入附加記錄R[0]有兩個作用：其一是進入查找循環(huán)之前，它保存了R[i]的副本，使得不至于因記錄的后移而丟失R[i]中的內容；其二是在while循環(huán)“監(jiān)視”下標變量j是否越界，一旦越界（即j<1），R[0]自動控制while循環(huán)的結束，從而避免了在while循環(huán)內的每一次都要檢測j是否越界（即省略了循環(huán)條件j>=1）。因此，我們把R[0]稱為“監(jiān)視哨”。直接插入排序舉例i(1)(2)(3)(4)(5)(6)(0)[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]算法分析直接插入排序算法由兩重循環(huán)組成，對于有n個記錄的排序，內循環(huán)表明完成一趟排序所需進行的記錄關鍵字間的比較和記錄的后移。若初始時關鍵字遞增有序（正序），這是最好情況。每一趟排序中僅需進行一次關鍵字的比較，所以總的比較次數(shù)為n-1。在while循環(huán)之前和之中，至少要移動記錄兩次，所以總的移動次數(shù)為2(n-1)。若初始時關鍵字遞減有序（反序），這是最壞情況。這時的記錄比較和移動次數(shù)分別為：直接插入排序的穩(wěn)定性直接插入排序是一種穩(wěn)定的排序方法。原理：關鍵字相同的兩個對象，在整個排序過程中，不會通過比較而相互交換。5.3.2排序問題中的減治法——堆排序堆是具有下列性質的完全二叉樹：每個結點的值都小于或等于其左右孩子結點的值（小根堆）；或者每個結點的值都大于或等于其左右孩子結點的值（大根堆）。如果將具有n個結點的堆按層序從1開始編號，則結點之間滿足如下關系：問題描述：應用堆排序方法對一個記錄序列進行升序排列。ki≤k2iki≤k2i+1ki≥k2iki≥k2i+11≤i≤n/2或堆排序——想法堆排序是利用堆（假設利用大根堆）的特性進行排序的方法，其基本思想是：首先將待排序的記錄序列構造成一個堆，此時，堆頂記錄是堆中所有記錄的最大者，將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換），然后將剩余記錄再調整成堆，這樣又找出了次大記錄，以此類推，直到堆中只有一個記錄為止。堆排序——實例282516321836163216282518362532162818362528323628161825堆排序——算法1.設置i和j，分別指向當前要篩選的結點和要篩選結點的左孩子；2.若ri已是葉子，則篩選完畢；否則，比較要篩選結點的左右孩子，并將j指向值較大的結點；3.將ri和rj進行比較，有以下兩種情況：

3.1如果ri>rj，則完全二叉樹已經是堆，篩選完畢；

3.2否則將ri和rj交換；令i=j，轉步驟2繼續(xù)進行篩選；算法5.4——篩選法調整堆

voidSiftHeap(intr[],intk,intn){i=k;j=2*i;//置i為要篩的結點，j為i的左孩子

while(j<=n)//篩選還沒有進行到葉子

{if(j<n&&r[j]<r[j+1])j++;//比較i的左右孩子，j為較大者

if(r[i]>r[j])//根結點已經大于左右孩子中的較大者

break;else{r[i]←→r[j];//將根結點與結點j交換

i=j;j=2*i;//被篩結點位于原來結點j的位置

}}}C++描述5.4

組合問題中的減治法5.4.1淘汰賽冠軍問題

5.4.2假幣問題問題描述：假設有n=2k個選手進行競技淘汰賽，最后決出冠軍的選手，設計競技淘汰比賽的過程。組合問題中的減治法——淘汰賽冠軍問題

淘汰賽冠軍問題——實例

stringGame(stringr[],intn){i=n;while(i>1){i=i/2;for(j=0;j<i;j++)if(Comp(r[j+i],r[j]))r[j]=r[j+i];}returnr[0];}淘汰賽冠軍問題——算法問題描述：在n枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣較輕。通過一架來任意比較兩組硬幣，從