算法設(shè)計(jì)與分析 第5章 減治法

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

2、solution變變 治治 法法 概概 述述減治是基于變治的思想。減治是基于變治的思想。邏輯等價(jià)邏輯等價(jià)子問(wèn)題子問(wèn)題的規(guī)模是的規(guī)模是n/2子問(wèn)題的解子問(wèn)題的解原問(wèn)題的解原問(wèn)題的解原問(wèn)題原問(wèn)題的規(guī)模是的規(guī)模是n（1） 原問(wèn)題的原問(wèn)題的解只存在于其中解只存在于其中一個(gè)較小規(guī)模的一個(gè)較小規(guī)模的子問(wèn)題中子問(wèn)題中;（2） 原問(wèn)題的原問(wèn)題的解與其中一個(gè)較解與其中一個(gè)較小規(guī)模的解之間小規(guī)模的解之間存在某種確定的存在某種確定的對(duì)應(yīng)關(guān)系。對(duì)應(yīng)關(guān)系。1 1 減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想對(duì)于給定的整數(shù)對(duì)于給定的整數(shù)a和非負(fù)整數(shù)和非負(fù)整數(shù)n，計(jì)算，計(jì)算an的值的值應(yīng)用減治技術(shù)得到如下計(jì)算方法：應(yīng)用減治技術(shù)得到如下

3、計(jì)算方法：且是奇數(shù)且是偶數(shù)1)(1)(122)1(22naananaannn1122naanaannn應(yīng)用分治技術(shù)得到如下計(jì)算方法：應(yīng)用分治技術(shù)得到如下計(jì)算方法：應(yīng)用分治法（例如二分法）得到的算法通常具有應(yīng)用分治法（例如二分法）得到的算法通常具有如下遞推式：如下遞推式： 分治法和減治法區(qū)別分治法和減治法區(qū)別應(yīng)用減治法（例如減半法）得到的算法通常具有應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：如下遞推式： 111)2/(0)(nnnTnT足夠小nnfnTngnT)()2/(2)()(2 2一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子兩個(gè)序列的中位數(shù)兩個(gè)序列的中位數(shù)問(wèn)題描述：一個(gè)長(zhǎng)度為問(wèn)題描述：一個(gè)長(zhǎng)度

4、為n（n1）的升序序列）的升序序列S，處在第，處在第n/2個(gè)位置的數(shù)稱為序列個(gè)位置的數(shù)稱為序列S的中位的中位數(shù)數(shù) 。兩個(gè)序列的中位數(shù)是他們所有元素的升。兩個(gè)序列的中位數(shù)是他們所有元素的升序序列的中位數(shù)?，F(xiàn)有兩個(gè)等長(zhǎng)升序序列序序列的中位數(shù)。現(xiàn)有兩個(gè)等長(zhǎng)升序序列A和和B，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列的中位數(shù)?？赡芨咝У乃惴?，找出兩個(gè)序列的中位數(shù)。想法：想法：分別求出兩個(gè)序列的中位數(shù)，記為分別求出兩個(gè)序列的中位數(shù)，記為a和和b；比；比較較a和和b，有下列三種情況：，有下列三種情況： a = b：則：則a即為兩個(gè)序列的中位數(shù)；即為兩個(gè)序

5、列的中位數(shù)； a b：則中位數(shù)只能出現(xiàn)在：則中位數(shù)只能出現(xiàn)在b和和a之間，在序列之間，在序列A中舍棄中舍棄a之后的元素得到序列之后的元素得到序列A1，在序列，在序列B中舍棄中舍棄b之前的元素得到序列之前的元素得到序列B1；在在A1和和B1中分別求出中位數(shù)，重復(fù)上述過(guò)程，直中分別求出中位數(shù)，重復(fù)上述過(guò)程，直到兩個(gè)序列中只有一個(gè)元素，則較小者即為所求。到兩個(gè)序列中只有一個(gè)元素，則較小者即為所求。2 2一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子兩個(gè)序列的中位數(shù)兩個(gè)序列的中位數(shù)對(duì)于兩個(gè)給定的序列對(duì)于兩個(gè)給定的序列A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列，求序列A和和B

6、的中位數(shù)的過(guò)程。的中位數(shù)的過(guò)程。步步驟驟操作說(shuō)明操作說(shuō)明序列序列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ù)分別求中位數(shù)11,13,1510,15,2051315，結(jié)果在，結(jié)果在11, 15之間之間舍棄舍棄13之前元素，之前元素，13,15舍棄舍棄15之后元素，之后元素，10,156分別求中位數(shù)

7、分別求中位數(shù)13,1510,1571013，結(jié)果在，結(jié)果在10, 13之間之間舍棄舍棄13之后元素，之后元素，13舍棄舍棄10之前元素，之前元素，158長(zhǎng)度為長(zhǎng)度為1，較小者為所求，較小者為所求13152 2一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子兩個(gè)序列的中位數(shù)兩個(gè)序列的中位數(shù)1. 循環(huán)直到序列循環(huán)直到序列A和序列和序列B均只有一個(gè)元素均只有一個(gè)元素 1.1 a = 序列序列A的中位數(shù)；的中位數(shù)； 1.2 b = 序列序列B的中位數(shù)；的中位數(shù)； 1.3 比較比較a和和b，執(zhí)行下面三種情況之一：，執(zhí)行下面三種情況之一： 1.3.1 若若a=b，則返回，則返回a，算法結(jié)束；，算法結(jié)束； 1.3.2 若若ab

8、，則在序列，則在序列A中舍棄中舍棄a之后的元素，之后的元素，在序列在序列B中舍棄中舍棄b之前的元素，轉(zhuǎn)步驟之前的元素，轉(zhuǎn)步驟1； 2. 序列序列A和序列和序列B均只有一個(gè)元素，返回較小者；均只有一個(gè)元素，返回較小者；2 2一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子兩個(gè)序列的中位數(shù)兩個(gè)序列的中位數(shù)查找問(wèn)題中的減治法查找問(wèn)題中的減治法折半查找折半查找問(wèn)題描述：應(yīng)用折半查找方法在一個(gè)有序序列中問(wèn)題描述：應(yīng)用折半查找方法在一個(gè)有序序列中查找值為查找值為k的記錄。若查找成功，返回記錄的記錄。若查找成功，返回記錄k在序在序列中的位置，若查找失敗，返回失敗信息。列中的位置，若查找失敗，返回失敗信息。 折半查找折半查找想法

9、想法折半查找利用了記錄序列有序的特點(diǎn)，其查找過(guò)程是：取折半查找利用了記錄序列有序的特點(diǎn)，其查找過(guò)程是：取有序序列的中間記錄作為比較對(duì)象，若給定值與中間記錄有序序列的中間記錄作為比較對(duì)象，若給定值與中間記錄相等，則查找成功；若給定值小于中間記錄，則在中間記相等，則查找成功；若給定值小于中間記錄，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄，則在中間錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直到查找成記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)記錄，查找失敗。功，或所查找的區(qū)域無(wú)記錄，查找失敗。 r1 rmid-1 r

10、mid rmid+1 rn 如果krmid查找這里k（mid=(1+n)/2）折半查找折半查找實(shí)例實(shí)例在有序表在有序表 7, 14, 18, 21, 23, 29, 31, 35, 38 中查找值為中查找值為18的的過(guò)程如下：過(guò)程如下： 1. low=1；high=n； /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間2. 測(cè)試查找區(qū)間測(cè)試查找區(qū)間low，high是否存在，若不是否存在，若不存在，則查找失?。环駝t存在，則查找失敗；否則3. 取中間點(diǎn)取中間點(diǎn)mid=(low+high)/2; 比較比較k與與rmid，有以下三種情況：有以下三種情況： 3.1 若若krmid，則，則low=mid+1；查找在右；

11、查找在右半?yún)^(qū)進(jìn)行，轉(zhuǎn)半?yún)^(qū)進(jìn)行，轉(zhuǎn)2； 3.3 若若k=rmid，則查找成功，返回記錄在，則查找成功，返回記錄在表中位置表中位置mid；折半查找折半查找算法算法查找問(wèn)題中的減治法查找問(wèn)題中的減治法二叉查找樹二叉查找樹在一個(gè)無(wú)序序列中執(zhí)行查找操作，可以在一個(gè)無(wú)序序列中執(zhí)行查找操作，可以將無(wú)序序列建立一棵二叉查找樹，然后將無(wú)序序列建立一棵二叉查找樹，然后在二叉查找樹中查找值為在二叉查找樹中查找值為k的記錄，若查的記錄，若查找成功，返回記錄找成功，返回記錄k的存儲(chǔ)地址，若查找的存儲(chǔ)地址，若查找失敗，返回空指針。失敗，返回空指針。二叉查找樹定義？二叉查找樹定義？二叉查找樹查找二叉查找樹查找想法想法由二叉

12、查找樹的定義，在二叉查找樹由二叉查找樹的定義，在二叉查找樹root中查找中查找給定值給定值k的過(guò)程是：的過(guò)程是：若若root是空樹，則查找失敗；是空樹，則查找失?。蝗羧鬹根結(jié)點(diǎn)的值，則查找成功；根結(jié)點(diǎn)的值，則查找成功；若若k根結(jié)點(diǎn)的值，則在根結(jié)點(diǎn)的值，則在root的右子樹上查找；的右子樹上查找；上述過(guò)程一直持續(xù)到查找成功或者待查找的子樹上述過(guò)程一直持續(xù)到查找成功或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗。為空，如果待查找的子樹為空，則查找失敗。 二叉查找樹二叉查找樹=平衡二叉樹？平衡二叉樹？在二叉查找樹中查找關(guān)鍵字值為在二叉查找樹中查找關(guān)鍵字值為35，95的過(guò)程：的過(guò)程：50302

13、08090858840353250302080908588403532二叉查找樹查找二叉查找樹查找實(shí)例實(shí)例簡(jiǎn)述查找過(guò)程？簡(jiǎn)述查找過(guò)程？BiNode * SearchBST( (BiNode *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) ); 二叉查找樹查找二叉查找樹查找

14、算法算法查找問(wèn)題中的減治法查找問(wèn)題中的減治法選擇問(wèn)題選擇問(wèn)題問(wèn)題描述：設(shè)無(wú)序序列問(wèn)題描述：設(shè)無(wú)序序列T=(r1, r2, , rn)，T的第的第k（1kn）小元素定義為）小元素定義為T按升序排列按升序排列后在第后在第k個(gè)位置上的元素。個(gè)位置上的元素。給定一個(gè)序列給定一個(gè)序列T和一個(gè)整數(shù)和一個(gè)整數(shù)k，尋找，尋找T的第的第k小元素的問(wèn)題稱為選擇問(wèn)題）。小元素的問(wèn)題稱為選擇問(wèn)題）。將尋找第將尋找第n/2小元素的問(wèn)題稱為中值問(wèn)題。小元素的問(wèn)題稱為中值問(wèn)題。選擇問(wèn)題選擇問(wèn)題想法想法考慮快速排序的劃分過(guò)程，一般情況下，設(shè)待劃分的序列考慮快速排序的劃分過(guò)程，一般情況下，設(shè)待劃分的序列為為rirj，選定一個(gè)軸

15、值對(duì)序列，選定一個(gè)軸值對(duì)序列rirj進(jìn)行劃分，使得比軸值進(jìn)行劃分，使得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位于軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位于軸值的右側(cè)，假定軸值的最終位置是的右側(cè)，假定軸值的最終位置是s，則：，則：（1）若）若k=s，則，則rs就是第就是第k小元素；小元素；（2）若）若ks，則第，則第k小元素一定在序列小元素一定在序列rs+1 rj中；中；無(wú)論哪種情況，或者已經(jīng)得出結(jié)果，或者將選擇問(wèn)題的查無(wú)論哪種情況，或者已經(jīng)得出結(jié)果，或者將選擇問(wèn)題的查找區(qū)間減少一半（如果軸值恰好是序列的中值）。找區(qū)間減少一半（如果軸值恰好是序列的中值）。 分治法設(shè)計(jì)思想？?jī)烧?/p>

16、在時(shí)間復(fù)雜分治法設(shè)計(jì)思想？?jī)烧咴跁r(shí)間復(fù)雜度區(qū)別？度區(qū)別？選擇問(wèn)題選擇問(wèn)題實(shí)例實(shí)例以以5為軸值劃分序列為軸值劃分序列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小的元素過(guò)程：小的元素過(guò)程：選擇問(wèn)題選擇問(wèn)題算法算法1. 設(shè)置初始查找區(qū)間：設(shè)置初始查找區(qū)間：i=1; j=n; 2. 以以ri為軸值對(duì)序列為軸值對(duì)序列rirj進(jìn)行一次劃分，得進(jìn)行一次劃分，得到軸值的位置到軸值的位置s;3. 將軸值位置將軸值位置s與與k比較比較

17、 3.1 如果如果k等于等于s，則將，則將rs作為結(jié)果返回；作為結(jié)果返回； 3.2 否則，如果否則，如果k rj，則完全二叉樹已經(jīng)是堆，篩選，則完全二叉樹已經(jīng)是堆，篩選完畢；完畢； 3.2 否則將否則將ri和和rj交換；令交換；令i=j，轉(zhuǎn)步驟，轉(zhuǎn)步驟2繼續(xù)進(jìn)繼續(xù)進(jìn)行篩選；行篩選；問(wèn)題描述：假設(shè)有問(wèn)題描述：假設(shè)有n=2k個(gè)選手進(jìn)行競(jìng)技淘個(gè)選手進(jìn)行競(jìng)技淘汰賽，最后決出冠軍的選手，設(shè)計(jì)競(jìng)技淘汰賽，最后決出冠軍的選手，設(shè)計(jì)競(jìng)技淘汰比賽的過(guò)程。汰比賽的過(guò)程。組合問(wèn)題中的減治法組合問(wèn)題中的減治法淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題 淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題實(shí)例實(shí)例 string Game(string r

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