第5章 減治法

1、第五章第五章 減減 治治 法法1234減治法的設(shè)計思想減治法的設(shè)計思想排序問題中的減治法排序問題中的減治法組合問題中的減治法組合問題中的減治法5查找問題中的減治法查找問題中的減治法小結(jié)小結(jié)第五章第五章 減治法減治法變治法分兩個階段工作，即“變”階段和“治”階段.變治法的三種類型： 1)實例化簡(instance simplification) 2)改變表現(xiàn)(representation change) 3)問題化簡(problem reduction)problems instancesimpler instanceorAnother representationor another prob

2、lems instancesolution變變 治治 法法 概概 述述減治是基于變治的思想。減治是基于變治的思想。邏輯等價邏輯等價第五章第五章 減治法減治法子問題子問題的規(guī)模是的規(guī)模是n/2子問題的解子問題的解原問題的解原問題的解原問題原問題的規(guī)模是的規(guī)模是n（1） 原問題的原問題的解只存在于其中解只存在于其中一個較小規(guī)模的一個較小規(guī)模的子問題中子問題中;（2） 原問題的原問題的解與其中一個較解與其中一個較小規(guī)模的解之間小規(guī)模的解之間存在某種確定的存在某種確定的對應(yīng)關(guān)系。對應(yīng)關(guān)系。1 1 減治法的設(shè)計思想減治法的設(shè)計思想第五章第五章 減治法減治法對于給定的整數(shù)對于給定的整數(shù)a和非負整數(shù)和非負整

3、數(shù)n，計算，計算an的值的值應(yīng)用減治技術(shù)得到如下計算方法：應(yīng)用減治技術(shù)得到如下計算方法：且是奇數(shù)且是偶數(shù)1)(1)(122)1(22naananaannn1122naanaannn應(yīng)用分治技術(shù)得到如下計算方法：應(yīng)用分治技術(shù)得到如下計算方法：第五章第五章 減治法減治法應(yīng)用分治法（例如二分法）得到的算法通常具有應(yīng)用分治法（例如二分法）得到的算法通常具有如下遞推式：如下遞推式： 分治法和減治法區(qū)別分治法和減治法區(qū)別應(yīng)用減治法（例如減半法）得到的算法通常具有應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：如下遞推式： 111)2/(0)(nnnTnT足夠小nnfnTngnT)()2/(2)()(

4、第五章第五章 減治法減治法2 2一個簡單的例子一個簡單的例子兩個序列的中位數(shù)兩個序列的中位數(shù)問題描述：一個長度為問題描述：一個長度為n（n1）的升序序列）的升序序列S，處在第，處在第n/2個位置的數(shù)稱為序列個位置的數(shù)稱為序列S的中位的中位數(shù)數(shù) 。兩個序列的中位數(shù)是他們所有元素的升。兩個序列的中位數(shù)是他們所有元素的升序序列的中位數(shù)?，F(xiàn)有兩個等長升序序列序序列的中位數(shù)?，F(xiàn)有兩個等長升序序列A和和B，試設(shè)計一個在時間和空間兩方面都盡，試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列的中位數(shù)?？赡芨咝У乃惴?，找出兩個序列的中位數(shù)。第五章第五章 減治法減治法想法：想法：分別求出兩個序列的中位

5、數(shù)，記為分別求出兩個序列的中位數(shù)，記為a和和b；比；比較較a和和b，有下列三種情況：，有下列三種情況： a = b：則：則a即為兩個序列的中位數(shù)；即為兩個序列的中位數(shù)； a b：則中位數(shù)只能出現(xiàn)在：則中位數(shù)只能出現(xiàn)在b和和a之間，在序列之間，在序列A中舍棄中舍棄a之后的元素得到序列之后的元素得到序列A1，在序列，在序列B中舍棄中舍棄b之前的元素得到序列之前的元素得到序列B1；在在A1和和B1中分別求出中位數(shù)，重復上述過程，直中分別求出中位數(shù)，重復上述過程，直到兩個序列中只有一個元素，則較小者即為所求。到兩個序列中只有一個元素，則較小者即為所求。2 2一個簡單的例子一個簡單的例子兩個序列的中位數(shù)

6、兩個序列的中位數(shù)第五章第五章 減治法減治法對于兩個給定的序列對于兩個給定的序列A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列，求序列A和和B的中位數(shù)的過程。的中位數(shù)的過程。步步驟驟操作說明操作說明序列序列A序列序列B1初始序列初始序列11, 13, 15, 17, 192, 4, 10, 15, 202分別求中位數(shù)分別求中位數(shù)11, 13, 15, 17, 192, 4, 10, 15, 2031510，結(jié)果在，結(jié)果在10, 15之間之間舍棄舍棄15之后元素，之后元素，11,13,15舍棄舍棄10之前元素，之前元素，10,15,204分別求中位數(shù)分別求

7、中位數(shù)11,13,1510,15,2051315，結(jié)果在，結(jié)果在11, 15之間之間舍棄舍棄13之前元素，之前元素，13,15舍棄舍棄15之后元素，之后元素，10,156分別求中位數(shù)分別求中位數(shù)13,1510,1571013，結(jié)果在，結(jié)果在10, 13之間之間舍棄舍棄13之后元素，之后元素，13舍棄舍棄10之前元素，之前元素，158長度為長度為1，較小者為所求，較小者為所求13152 2一個簡單的例子一個簡單的例子兩個序列的中位數(shù)兩個序列的中位數(shù)第五章第五章 減治法減治法1. 循環(huán)直到序列循環(huán)直到序列A和序列和序列B均只有一個元素均只有一個元素 1.1 a = 序列序列A的中位數(shù)；的中位數(shù)；

8、1.2 b = 序列序列B的中位數(shù)；的中位數(shù)； 1.3 比較比較a和和b，執(zhí)行下面三種情況之一：，執(zhí)行下面三種情況之一： 1.3.1 若若a=b，則返回，則返回a，算法結(jié)束；，算法結(jié)束； 1.3.2 若若ab，則在序列，則在序列A中舍棄中舍棄a之后的元素，之后的元素，在序列在序列B中舍棄中舍棄b之前的元素，轉(zhuǎn)步驟之前的元素，轉(zhuǎn)步驟1； 2. 序列序列A和序列和序列B均只有一個元素，返回較小者；均只有一個元素，返回較小者；2 2一個簡單的例子一個簡單的例子兩個序列的中位數(shù)兩個序列的中位數(shù)第五章第五章 減治法減治法查找問題中的減治法查找問題中的減治法折半查找折半查找問題描述：應(yīng)用折半查找方法在一個

9、有序序列中問題描述：應(yīng)用折半查找方法在一個有序序列中查找值為查找值為k的記錄。若查找成功，返回記錄的記錄。若查找成功，返回記錄k在序在序列中的位置，若查找失敗，返回失敗信息。列中的位置，若查找失敗，返回失敗信息。 第五章第五章 減治法減治法折半查找折半查找想法想法折半查找利用了記錄序列有序的特點，其查找過程是：取折半查找利用了記錄序列有序的特點，其查找過程是：取有序序列的中間記錄作為比較對象，若給定值與中間記錄有序序列的中間記錄作為比較對象，若給定值與中間記錄相等，則查找成功；若給定值小于中間記錄，則在中間記相等，則查找成功；若給定值小于中間記錄，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間

10、記錄，則在中間錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復上述過程，直到查找成記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。功，或所查找的區(qū)域無記錄，查找失敗。 r1 rmid-1 rmid rmid+1 rn 如果krmid查找這里k（mid=(1+n)/2）第五章第五章 減治法減治法折半查找折半查找實例實例在有序表在有序表 7, 14, 18, 21, 23, 29, 31, 35, 38 中查找值為中查找值為18的的過程如下：過程如下： 第五章第五章 減治法減治法1. low=1；high=n； /設(shè)置初始查找區(qū)

11、間設(shè)置初始查找區(qū)間2. 測試查找區(qū)間測試查找區(qū)間low，high是否存在，若不是否存在，若不存在，則查找失敗；否則存在，則查找失??；否則3. 取中間點取中間點mid=(low+high)/2; 比較比較k與與rmid，有以下三種情況：有以下三種情況： 3.1 若若krmid，則，則low=mid+1；查找在右；查找在右半?yún)^(qū)進行，轉(zhuǎn)半?yún)^(qū)進行，轉(zhuǎn)2； 3.3 若若k=rmid，則查找成功，返回記錄在，則查找成功，返回記錄在表中位置表中位置mid；折半查找折半查找算法算法第五章第五章 減治法減治法查找問題中的減治法查找問題中的減治法二叉查找樹二叉查找樹在一個無序序列中執(zhí)行查找操作，可以在一個無序序列

12、中執(zhí)行查找操作，可以將無序序列建立一棵二叉查找樹，然后將無序序列建立一棵二叉查找樹，然后在二叉查找樹中查找值為在二叉查找樹中查找值為k的記錄，若查的記錄，若查找成功，返回記錄找成功，返回記錄k的存儲地址，若查找的存儲地址，若查找失敗，返回空指針。失敗，返回空指針。二叉查找樹定義？二叉查找樹定義？第五章第五章 減治法減治法二叉查找樹查找二叉查找樹查找想法想法由二叉查找樹的定義，在二叉查找樹由二叉查找樹的定義，在二叉查找樹root中查找中查找給定值給定值k的過程是：的過程是：若若root是空樹，則查找失??；是空樹，則查找失??；若若k根結(jié)點的值，則查找成功；根結(jié)點的值，則查找成功；若若k根結(jié)點的值，

13、則在根結(jié)點的值，則在root的右子樹上查找；的右子樹上查找；上述過程一直持續(xù)到查找成功或者待查找的子樹上述過程一直持續(xù)到查找成功或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。為空，如果待查找的子樹為空，則查找失敗。 二叉查找樹二叉查找樹=平衡二叉樹？平衡二叉樹？第五章第五章 減治法減治法在二叉查找樹中查找關(guān)鍵字值為在二叉查找樹中查找關(guān)鍵字值為35，95的過程：的過程：5030208090858840353250302080908588403532二叉查找樹查找二叉查找樹查找實例實例簡述查找過程？簡述查找過程？第五章第五章 減治法減治法BiNode * SearchBST( (BiNo

14、de *root, int k) ) if ( (root= =NULL) ) return NULL； else if ( (root-data=k) ) return root; else if ( (k-data) ) return SearchBST( (root-lchild, k) ); else return SearchBST( (root-rchild, k) ); 二叉查找樹查找二叉查找樹查找算法算法第五章第五章 減治法減治法查找問題中的減治法查找問題中的減治法選擇問題選擇問題問題描述：設(shè)無序序列問題描述：設(shè)無序序列T=(r1, r2, , rn)，T的第的第k（1kn）小

15、元素定義為）小元素定義為T按升序排列按升序排列后在第后在第k個位置上的元素。個位置上的元素。給定一個序列給定一個序列T和一個整數(shù)和一個整數(shù)k，尋找，尋找T的第的第k小元素的問題稱為選擇問題）。小元素的問題稱為選擇問題）。將尋找第將尋找第n/2小元素的問題稱為中值問題。小元素的問題稱為中值問題。第五章第五章 減治法減治法選擇問題選擇問題想法想法考慮快速排序的劃分過程，一般情況下，設(shè)待劃分的序列考慮快速排序的劃分過程，一般情況下，設(shè)待劃分的序列為為rirj，選定一個軸值對序列，選定一個軸值對序列rirj進行劃分，使得比軸值進行劃分，使得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位于軸值小的元

16、素都位于軸值的左側(cè)，比軸值大的元素都位于軸值的右側(cè)，假定軸值的最終位置是的右側(cè)，假定軸值的最終位置是s，則：，則：（1）若）若k=s，則，則rs就是第就是第k小元素；小元素；（2）若）若ks，則第，則第k小元素一定在序列小元素一定在序列rs+1 rj中；中；無論哪種情況，或者已經(jīng)得出結(jié)果，或者將選擇問題的查無論哪種情況，或者已經(jīng)得出結(jié)果，或者將選擇問題的查找區(qū)間減少一半（如果軸值恰好是序列的中值）。找區(qū)間減少一半（如果軸值恰好是序列的中值）。 分治法設(shè)計思想？兩者在時間復雜分治法設(shè)計思想？兩者在時間復雜度區(qū)別？度區(qū)別？第五章第五章 減治法減治法選擇問題選擇問題實例實例以以5為軸值劃分序列為軸值

17、劃分序列42，只在右側(cè)查找，只在右側(cè)查找以以4為軸值劃分序列為軸值劃分序列44,軸值第軸值第4小元素小元素5 3 8 1 4 6 9 2 72 3 4 1 5 6 9 8 72 3 4 1 2 4 3 4 3 3 4 找第找第4 4小的元素過程：小的元素過程：第五章第五章 減治法減治法選擇問題選擇問題算法算法1. 設(shè)置初始查找區(qū)間：設(shè)置初始查找區(qū)間：i=1; j=n; 2. 以以ri為軸值對序列為軸值對序列rirj進行一次劃分，得進行一次劃分，得到軸值的位置到軸值的位置s;3. 將軸值位置將軸值位置s與與k比較比較 3.1 如果如果k等于等于s，則將，則將rs作為結(jié)果返回；作為結(jié)果返回； 3.

18、2 否則，如果否則，如果k rj，則完全二叉樹已經(jīng)是堆，篩選，則完全二叉樹已經(jīng)是堆，篩選完畢；完畢； 3.2 否則將否則將ri和和rj交換；令交換；令i=j，轉(zhuǎn)步驟，轉(zhuǎn)步驟2繼續(xù)進繼續(xù)進行篩選；行篩選；第五章第五章 減治法減治法問題描述：假設(shè)有問題描述：假設(shè)有n=2k個選手進行競技淘個選手進行競技淘汰賽，最后決出冠軍的選手，設(shè)計競技淘汰賽，最后決出冠軍的選手，設(shè)計競技淘汰比賽的過程。汰比賽的過程。組合問題中的減治法組合問題中的減治法淘汰賽冠軍問題淘汰賽冠軍問題 第五章第五章 減治法減治法淘汰賽冠軍問題淘汰賽冠軍問題實例實例 第五章第五章 減治法減治法 string Game(string r

19、, int n) i=n; while (i1) i=i/2; for (j=0; ji; j+) if (Comp(rj+i, rj) rj=rj+i; return r0; 淘汰賽冠軍問題淘汰賽冠軍問題算法算法第五章第五章 減治法減治法問題描述：在問題描述：在n枚外觀相同的硬幣中，有枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣較輕。通過一一枚是假幣，并且已知假幣較輕。通過一架來任意比較兩組硬幣，從而得知兩組硬架來任意比較兩組硬幣，從而得知兩組硬幣的重量是否相同，或者哪一組更輕一些，幣的重量是否相同，或者哪一組更輕一些，假幣問題要求設(shè)計一個高效的算法來檢測假幣問題要求設(shè)計一個高效的算法來檢測出這枚假幣。出這枚假幣。T(n)=O(log2n)組合問題中的減治法組合問題中的減治法假幣問題假幣問題 第五章第五章 減治法減治法最自然的想法就是一分為二，也就是把最自然的想法就是一分為二，也就是把n枚硬幣枚硬幣分成兩組，每組有分成兩組，每組有 n/2 枚硬幣，如果枚硬幣，如果n為奇數(shù)，為奇數(shù)，就留下一枚硬幣，然后把兩組硬幣分別放到天平就留下一枚硬幣，