第5章_減治法

1、教學(xué)重點(diǎn)教學(xué)重點(diǎn)減治法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的減治思想減治法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的減治思想教學(xué)難點(diǎn)教學(xué)難點(diǎn)二叉查找樹(shù)，堆排序二叉查找樹(shù)，堆排序教學(xué)內(nèi)容教學(xué)內(nèi)容及目標(biāo)及目標(biāo)知識(shí)點(diǎn)知識(shí)點(diǎn)教學(xué)要求教學(xué)要求了解了解理解理解掌握掌握熟練掌握熟練掌握減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想折半查找折半查找二叉查找樹(shù)二叉查找樹(shù)選擇問(wèn)題選擇問(wèn)題插入排序插入排序堆排序堆排序淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題假幣問(wèn)題假幣問(wèn)題學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)第第5章章 減治法減治法 5.1 概述概述 5.2 查找問(wèn)題中的減治法查找問(wèn)題中的減治法5.3 排序問(wèn)題中的減治法排序問(wèn)題中的減治法5.4 組合問(wèn)題中的減治法組合問(wèn)題中的減治法閱讀材料

2、閱讀材料 假幣問(wèn)題的復(fù)雜版本假幣問(wèn)題的復(fù)雜版本5.1 概述概述 分治法：把一個(gè)大問(wèn)題劃分為若干個(gè)子問(wèn)題，分別求分治法：把一個(gè)大問(wèn)題劃分為若干個(gè)子問(wèn)題，分別求解各個(gè)子問(wèn)題，然后將子問(wèn)題的解合并得到解各個(gè)子問(wèn)題，然后將子問(wèn)題的解合并得到原問(wèn)題的解。原問(wèn)題的解。減治法：同樣把一個(gè)大問(wèn)題劃分為若干個(gè)子問(wèn)題，但減治法：同樣把一個(gè)大問(wèn)題劃分為若干個(gè)子問(wèn)題，但無(wú)須分別求解這些子問(wèn)題，只需求解其中的無(wú)須分別求解這些子問(wèn)題，只需求解其中的一個(gè)子問(wèn)題，因而無(wú)需對(duì)子問(wèn)題的解進(jìn)行合一個(gè)子問(wèn)題，因而無(wú)需對(duì)子問(wèn)題的解進(jìn)行合并。退化了的分治法。并。退化了的分治法。減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 減治法將問(wèn)題劃分為若干子問(wèn)

3、題，并且規(guī)模為減治法將問(wèn)題劃分為若干子問(wèn)題，并且規(guī)模為n的的原問(wèn)題的解與較小規(guī)模（通常是原問(wèn)題的解與較小規(guī)模（通常是n/2）的子問(wèn)題的解之）的子問(wèn)題的解之間具有某種確定的關(guān)系：間具有某種確定的關(guān)系：（1）原問(wèn)題的解只存在于其中一個(gè)較小規(guī)模的子問(wèn)題中；原問(wèn)題的解只存在于其中一個(gè)較小規(guī)模的子問(wèn)題中；（2）原問(wèn)題的解與其中一個(gè)較小規(guī)模的解之間有某種對(duì)應(yīng)關(guān)系。原問(wèn)題的解與其中一個(gè)較小規(guī)模的解之間有某種對(duì)應(yīng)關(guān)系。 由于原問(wèn)題的解與較小規(guī)模的子問(wèn)題的解之間存在由于原問(wèn)題的解與較小規(guī)模的子問(wèn)題的解之間存在這種關(guān)系，所以，這種關(guān)系，所以，只需求解其中一個(gè)較小規(guī)模的子問(wèn)只需求解其中一個(gè)較小規(guī)模的子問(wèn)題就可以得到

4、原問(wèn)題的解題就可以得到原問(wèn)題的解。 子問(wèn)題子問(wèn)題 的規(guī)模是的規(guī)模是n/2 子問(wèn)題的解子問(wèn)題的解 原問(wèn)題的解原問(wèn)題的解 原問(wèn)題原問(wèn)題 的規(guī)模是的規(guī)模是n 子問(wèn)題子問(wèn)題 的規(guī)模是的規(guī)模是n/2減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 例：計(jì)算例：計(jì)算an的值，的值，應(yīng)用應(yīng)用減治技術(shù)減治技術(shù)得到如下計(jì)算方法：得到如下計(jì)算方法：應(yīng)用應(yīng)用分治法分治法得到得到an的計(jì)算方法是：的計(jì)算方法是： 1122naanaannnO (log2n)O (n log2n) - -且是奇數(shù)且是奇數(shù)且是偶數(shù)且是偶數(shù)1)(1)(122) 1(22naananaannn減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 111)2/(0)(nnnTnT

5、 所以，通常來(lái)說(shuō)，所以，通常來(lái)說(shuō)，應(yīng)用減治法應(yīng)用減治法處理問(wèn)題的效率是很高的，處理問(wèn)題的效率是很高的，一般是一般是O( (log2n) )數(shù)量級(jí)數(shù)量級(jí)。 減治法只對(duì)一個(gè)子問(wèn)題求解減治法只對(duì)一個(gè)子問(wèn)題求解，并且，并且不需要解的合并不需要解的合并。應(yīng)。應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：用減治法（例如減半法）得到的算法通常具有如下遞推式： 減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 對(duì)比分治法：對(duì)比分治法： 足夠小nnfnTngnT)()2/(2)()(減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子兩個(gè)序列的中位數(shù)兩個(gè)序列的中位數(shù)問(wèn)題描述：一個(gè)長(zhǎng)度為問(wèn)題描述：一個(gè)長(zhǎng)度為n（

6、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ù)。A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，則中位數(shù)為，則中位數(shù)為13減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 想法想法 分別求出兩個(gè)序列的中位數(shù)，記為分別求出兩個(gè)序

7、列的中位數(shù)，記為a和和b；比較比較a和和b，有下列三種情況：，有下列三種情況： a = b：則：則a即為兩個(gè)序列的中位數(shù)；即為兩個(gè)序列的中位數(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è)元素，則較小者即為所求。減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 對(duì)于兩個(gè)給定的序列對(duì)于兩個(gè)給定的序列A=

8、11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列，求序列A和和B的中位數(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之間之

9、間舍棄舍棄13之前元素，之前元素，13,15舍棄舍棄15之后元素，之后元素，10,156分別求中位數(shù)分別求中位數(shù)13,1510,1571013，結(jié)果在，結(jié)果在10, 13之間之間舍棄舍棄13之后元素，之后元素，13舍棄舍棄10之前元素，之前元素，158長(zhǎng)度為長(zhǎng)度為1，較小者為所求，較小者為所求1315減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 算法算法5.1：兩個(gè)序列中位數(shù)：兩個(gè)序列中位數(shù)SearchMid輸入：兩個(gè)長(zhǎng)度為輸入：兩個(gè)長(zhǎng)度為n的有序序列的有序序列A和和B輸出：序列輸出：序列A和和B的中位數(shù)的中位數(shù)1. 循環(huán)直到序列循環(huán)直到序列A和序列和序列B均只有一個(gè)元素均只有一個(gè)元素 1.1 a = 序

10、列序列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，則在序列，則在序列A中舍棄中舍棄a之后的元素，在序列之后的元素，在序列B中中舍棄舍棄b之前的元素，轉(zhuǎn)步驟之前的元素，轉(zhuǎn)步驟1； 2. 序列序列A和序列和序列B均只有一個(gè)元素，返回較小者；均只有一個(gè)元素，返回較小者；減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想 算法分析算法分析 由于每次求兩個(gè)序列的中位數(shù)后，得到由于每次求兩個(gè)序列的中位數(shù)后，得到的兩個(gè)子序列的長(zhǎng)度都是上一

11、個(gè)序列的一半，故循的兩個(gè)子序列的長(zhǎng)度都是上一個(gè)序列的一半，故循環(huán)共執(zhí)行環(huán)共執(zhí)行l(wèi)og2n次，時(shí)間復(fù)雜性為次，時(shí)間復(fù)雜性為O( log2n)。算法除簡(jiǎn)單變量外沒(méi)有額外開(kāi)辟臨時(shí)空間，故空間算法除簡(jiǎn)單變量外沒(méi)有額外開(kāi)辟臨時(shí)空間，故空間復(fù)雜性為復(fù)雜性為O(1)。第第5章章 減治法減治法 5.1 概述概述 5.2 查找問(wèn)題中的減治法查找問(wèn)題中的減治法5.3 排序問(wèn)題中的減治法排序問(wèn)題中的減治法5.4 組合問(wèn)題中的減治法組合問(wèn)題中的減治法閱讀材料閱讀材料 假幣問(wèn)題的復(fù)雜版本假幣問(wèn)題的復(fù)雜版本5.2 查找問(wèn)題中的減治法查找問(wèn)題中的減治法 5.2.1 折半查找折半查找 5.2.2 二叉查找樹(shù)二叉查找樹(shù)基本思想

12、：基本思想：(1)(1)取中間記錄作為比較對(duì)象取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；相等，則查找成功；(2)(2)若給定值小于中間記錄的關(guān)鍵碼，則若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的在中間記錄的左半?yún)^(qū)左半?yún)^(qū)繼續(xù)查找；繼續(xù)查找；(3)(3)若給定值大于中間記錄的若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)右半?yún)^(qū)繼續(xù)查找。繼續(xù)查找。重復(fù)上述過(guò)程，直到成功，或所查找的區(qū)域無(wú)記錄，查找失重復(fù)上述過(guò)程，直到成功，或所查找的區(qū)域無(wú)記錄，查找失敗。敗。 折半查找折半查找 r1 rmid- -1 rmid rmid+

13、1 rn （mid=( (1+n) )/2）如果如果 krmid 查找這里查找這里特點(diǎn)：每次與中間記錄比較特點(diǎn)：每次與中間記錄比較 k 問(wèn)題問(wèn)題 ：在有序表中查找值為在有序表中查找值為k k的記錄的記錄例：查找值為例：查找值為14的記錄的過(guò)程的記錄的過(guò)程0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 31141814714low=2mid=2 14=14算法算法5.1折半查找折半查找輸入：有序序列輸入：有序序列r1,

14、r2,rn，待查值，待查值k輸出：若成功返回記錄輸出：若成功返回記錄k的位置，否則返回失敗標(biāo)志的位置，否則返回失敗標(biāo)志0 1. low=1；high=n； /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間 2. 測(cè)試查找區(qū)間測(cè)試查找區(qū)間low，high是否存在，若不存在，則查找失敗；是否存在，若不存在，則查找失?。?否則否則 3. 取中間點(diǎn)取中間點(diǎn)mid=( (low+high) )/2; 比較比較k與與rmid，有以下三種情況：，有以下三種情況： 3.1 若若krmid，則，則 low=mid+1；查找在右半?yún)^(qū)進(jìn)行，轉(zhuǎn)；查找在右半?yún)^(qū)進(jìn)行，轉(zhuǎn)2； 3.3 若若k=rmid，則查找成功，返回記錄在表中位置，則

15、查找成功，返回記錄在表中位置mid；折半查找折半查找 算法分析算法分析 用判定樹(shù)描述折半查找的判定過(guò)程。每個(gè)結(jié)用判定樹(shù)描述折半查找的判定過(guò)程。每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序序列中的一個(gè)記錄，結(jié)點(diǎn)值為該記錄在有序點(diǎn)對(duì)應(yīng)有序序列中的一個(gè)記錄，結(jié)點(diǎn)值為該記錄在有序序列中的位置。長(zhǎng)度為序列中的位置。長(zhǎng)度為n的判定樹(shù)的構(gòu)造方法為：的判定樹(shù)的構(gòu)造方法為： （1）當(dāng)）當(dāng)n=0時(shí)，判定樹(shù)為空；時(shí)，判定樹(shù)為空；（2）當(dāng)）當(dāng)n0時(shí)，時(shí)， 根結(jié)點(diǎn)：根結(jié)點(diǎn)：是有序表中序號(hào)為是有序表中序號(hào)為mid=(n+1)/2的記錄；的記錄； 左子樹(shù)：左子樹(shù)：是有序表是有序表r1 rmid-1對(duì)應(yīng)的判定樹(shù)；對(duì)應(yīng)的判定樹(shù)； 右子樹(shù)：右子樹(shù)：是與是與

16、rmid+1 rn相對(duì)應(yīng)的判定樹(shù)相對(duì)應(yīng)的判定樹(shù)折半查找折半查找 6312548111079 查找查找k k過(guò)程：過(guò)程：從根結(jié)點(diǎn)從根結(jié)點(diǎn)該記錄結(jié)點(diǎn)的路徑；該記錄結(jié)點(diǎn)的路徑； 和和K K值的比較次數(shù)：值的比較次數(shù)：等于該記錄結(jié)點(diǎn)在樹(shù)中的等于該記錄結(jié)點(diǎn)在樹(shù)中的層數(shù)層數(shù)。具有。具有n個(gè)結(jié)點(diǎn)的判定數(shù)的深度為個(gè)結(jié)點(diǎn)的判定數(shù)的深度為 。1log2n折半查找折半查找 5.2 查找問(wèn)題中的減治法查找問(wèn)題中的減治法 5.2.1 折半查找折半查找 5.2.2 二叉查找樹(shù)二叉查找樹(shù)二叉查找樹(shù)二叉查找樹(shù)BST 二叉查找樹(shù)二叉查找樹(shù)BST 由由二叉排序樹(shù)的定義二叉排序樹(shù)的定義，在二叉排序樹(shù)，在二叉排序樹(shù)root中查找給定

17、值中查找給定值k的的過(guò)程是：過(guò)程是： 若若root是空樹(shù)，則查找失??；是空樹(shù)，則查找失?。?若若k根結(jié)點(diǎn)的值，則查找成功；根結(jié)點(diǎn)的值，則查找成功； 否則，若否則，若k根結(jié)點(diǎn)的值根結(jié)點(diǎn)的值，則在，則在root左子樹(shù)上查找左子樹(shù)上查找； 否則，在否則，在root的的右子樹(shù)上查找右子樹(shù)上查找； 上述過(guò)程一直持續(xù)到上述過(guò)程一直持續(xù)到k被找到被找到或者或者待查找的子樹(shù)為空待查找的子樹(shù)為空，如，如果待查找的子樹(shù)為空，果待查找的子樹(shù)為空，則查找失敗則查找失敗。v二叉排序樹(shù)的二叉排序樹(shù)的查找效率查找效率就在于只需要就在于只需要查找兩個(gè)子樹(shù)之一查找兩個(gè)子樹(shù)之一。 58427090634555836710二叉查找

18、樹(shù)二叉查找樹(shù)BST 查找查找58與與95記錄的示例記錄的示例二叉排序樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為：二叉排序樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為：struct BiNode int data; /結(jié)點(diǎn)的值，假設(shè)查找集合的元素為整型結(jié)點(diǎn)的值，假設(shè)查找集合的元素為整型 BiNode *lchild, *rchild; /指指向左向左、右子樹(shù)右子樹(shù)的指針的指針 ;算法算法5.2二叉排序樹(shù)的查找二叉排序樹(shù)的查找 BiNode * SearchBST(BiNode * root, int k) if (root= =NULL) return NULL； else if (root-data=k) return root; else if (

19、kdata) return SearchBST(root-lchild, k); else return SearchBST(root-rchild, k); C+描述二叉查找樹(shù)二叉查找樹(shù)BSTBST 建立二叉查找樹(shù)算法建立二叉查找樹(shù)算法BiNode* InsertBST(BiNode* root, int data) if(root=NULL) root=new BiNode; root-data=data;/申請(qǐng)一個(gè)新結(jié)點(diǎn)申請(qǐng)一個(gè)新結(jié)點(diǎn) root-lchild=root-rchild=NULL;/葉子結(jié)點(diǎn)葉子結(jié)點(diǎn) return root; if(datadata)root-lchild=I

20、nsertBST(root-lchild, data); elseroot-rchild=InsertBST(root-rchild, data);return root;二叉查找樹(shù)二叉查找樹(shù)BSTBST BiNode* createBST(int a, int n) /建立二叉查找樹(shù)建立二叉查找樹(shù) BiNode* T=NULL; for(int i=0; in; i+)T=InsertBST(T, ai); /在二叉查找樹(shù)在二叉查找樹(shù) T中插入中插入ai return T;二叉查找樹(shù)二叉查找樹(shù)BSTBST 二叉查找樹(shù)二叉查找樹(shù)BSTBST 按按63,90,55,58,70,42,10,45,

21、83,67順序構(gòu)造的二叉排序樹(shù)順序構(gòu)造的二叉排序樹(shù)58427090634555836710二叉查找樹(shù)二叉查找樹(shù)BSTBST 1log2n問(wèn)題問(wèn)題 設(shè)無(wú)序序列設(shè)無(wú)序序列 T =(r1, r2, , rn)，T 的第的第k（1kn）小元素定義為小元素定義為T(mén) 按升序排列后在第按升序排列后在第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)題。 5.2.3 5.2.3 選擇問(wèn)題選擇問(wèn)題想法想法 固然可將固

22、然可將T排序后取第排序后取第k個(gè)元素，但排序算法最好時(shí)間個(gè)元素，但排序算法最好時(shí)間是是O(nlog2n)，如應(yīng)用減治技術(shù)，可將算法平均時(shí)間性能提高，如應(yīng)用減治技術(shù)，可將算法平均時(shí)間性能提高到到O(n)?？紤]?？紤]快速排序快速排序中的劃分過(guò)程，一般情況下，設(shè)待劃中的劃分過(guò)程，一般情況下，設(shè)待劃分的序列為分的序列為ri rj，選定一個(gè)軸值將序列，選定一個(gè)軸值將序列ri rj進(jìn)行劃分，使進(jìn)行劃分，使得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位得比軸值小的元素都位于軸值的左側(cè)，比軸值大的元素都位于軸值的右側(cè)，假定軸值的最終位置是于軸值的右側(cè)，假定軸值的最終位置是s，則：，則：（1）若）若k=s

23、，則，則rs就是第就是第k小元素；小元素；（2）若）若ks，則第，則第k小元素一定在序列小元素一定在序列rs+1 rj中；中；無(wú)論上面哪種情況，或者已經(jīng)得到結(jié)果，或者將選擇問(wèn)無(wú)論上面哪種情況，或者已經(jīng)得到結(jié)果，或者將選擇問(wèn)題的查找區(qū)間減少一半（如果軸值恰好是序列的中值）題的查找區(qū)間減少一半（如果軸值恰好是序列的中值）5.2.3 5.2.3 選擇問(wèn)題選擇問(wèn)題 ri rk rs- -1 rs rs+1 rj 均均rs 軸值軸值 均均rs ri rs- -1 rs rs+1 rk rj 均均rs 軸值軸值 均均rs(a) 若若ks，則，則rk在右半?yún)^(qū)在右半?yún)^(qū)選擇問(wèn)題的例子選擇問(wèn)題的例子: :查找第查

24、找第4小元素小元素5 3 8 1 4 6 9 2 7以以5為軸值劃分序列為軸值劃分序列42，只在右側(cè)查找，只在右側(cè)查找以以4為軸值劃分序列為軸值劃分序列44，軸值即為第，軸值即為第4小元素小元素 2 3 4 1 5 6 9 8 7 2 3 4 1 1 2 4 3 4 3 3 4 5.2.3 5.2.3 選擇問(wèn)題選擇問(wèn)題算法算法選擇問(wèn)題選擇問(wèn)題輸入：無(wú)序序列輸入：無(wú)序序列r ，位置，位置k輸出：返回第輸出：返回第k小的元素值小的元素值 1. i=1; j=n; /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間 2. 以以ri為軸值對(duì)序列為軸值對(duì)序列rirj進(jìn)行一次劃分，得到軸進(jìn)行一次劃分，得到軸值的位置值的位

25、置s; 3. 將軸值位置將軸值位置s與與k比較比較 3.1 如果如果k=s，則將，則將rs作為結(jié)果返回；作為結(jié)果返回； 3.2 否則，如果否則，如果ks，則，則j=s-1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2； 3.3 否則，否則，i=s+1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2；5.2.3 5.2.3 選擇問(wèn)題選擇問(wèn)題最好情況最好情況：每次劃分的軸值恰好是序列的中值，則可以保證處每次劃分的軸值恰好是序列的中值，則可以保證處理的區(qū)間比上一次減半，由于在一次劃分后，只需處理一個(gè)子理的區(qū)間比上一次減半，由于在一次劃分后，只需處理一個(gè)子序列，所以，比較次數(shù)的遞推式是：序列，所以，比較次數(shù)的遞推式是： ( )(2)( )( )T nT nO

26、 nO n最壞情況最壞情況：每次劃分的軸值恰好是序列中的最大值或最小值，每次劃分的軸值恰好是序列中的最大值或最小值，則處理區(qū)間只能比上一次減少則處理區(qū)間只能比上一次減少1個(gè)，所以，比較次數(shù)的遞推式是：個(gè)，所以，比較次數(shù)的遞推式是：平均情況平均情況：假設(shè)每次劃分的軸值是劃分序列中的一個(gè)隨機(jī)位置：假設(shè)每次劃分的軸值是劃分序列中的一個(gè)隨機(jī)位置的元素，則處理區(qū)間按照一種隨機(jī)的方式減少，可以證明，算的元素，則處理區(qū)間按照一種隨機(jī)的方式減少，可以證明，算法的平均時(shí)間是法的平均時(shí)間是O(n) 。 )2()()1()(nOnOnTnT - - 5.2.3 5.2.3 選擇問(wèn)題選擇問(wèn)題第第5章章 減治法減治法

27、5.1 概述概述 5.2 查找問(wèn)題中的減治法查找問(wèn)題中的減治法5.3 排序問(wèn)題中的減治法排序問(wèn)題中的減治法5.4 組合問(wèn)題中的減治法組合問(wèn)題中的減治法閱讀材料閱讀材料 假幣問(wèn)題的復(fù)雜版本假幣問(wèn)題的復(fù)雜版本5.3 排序問(wèn)題中的減治法排序問(wèn)題中的減治法 5.3.1 插入排序插入排序5.3.2 堆排序堆排序每次將無(wú)序區(qū)第每次將無(wú)序區(qū)第1條記錄插入到有序區(qū)適當(dāng)位置。初條記錄插入到有序區(qū)適當(dāng)位置。初始取第始取第1條記錄為有序區(qū)，其它記錄為無(wú)序區(qū)。隨著條記錄為有序區(qū)，其它記錄為無(wú)序區(qū)。隨著排序進(jìn)行，有序區(qū)不斷擴(kuò)大，無(wú)序區(qū)不斷縮小。最終排序進(jìn)行，有序區(qū)不斷擴(kuò)大，無(wú)序區(qū)不斷縮小。最終無(wú)序區(qū)為空，有序區(qū)包含了全

28、部記錄，排序結(jié)束。無(wú)序區(qū)為空，有序區(qū)包含了全部記錄，排序結(jié)束。 有序區(qū)也可從排序表的尾部生成有序區(qū)也可從排序表的尾部生成 。在插入第在插入第 i（i1）個(gè)記錄時(shí)，前面的）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序個(gè)記錄已經(jīng)排好序。 有序序列有序序列無(wú)序序列無(wú)序序列r1r2ri-1rirnri+1r1r2ri-1rirnri+1（1）如何構(gòu)造初始的有序序列？）如何構(gòu)造初始的有序序列？( (待排序序列第一個(gè)記錄）待排序序列第一個(gè)記錄）（2）如何查找待插入記錄的插入位置）如何查找待插入記錄的插入位置?需解決的關(guān)鍵問(wèn)題需解決的關(guān)鍵問(wèn)題? 初始：（初始：（49）38 13 76 27 49 （38 49）

29、13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）自右向左順自右向左順序查找插入序查找插入的位置的位置r 0 1 2 3 4 5 6211825221025*212125插入排序插入排序i = 218221025*25i = 318221025*2225222110252115102525*2521151025*252118151018181025*i = 418i = 61825*i = 5r0的作用的作用?暫存單元暫存單元監(jiān)視哨監(jiān)視哨25void InsertS

30、ort(int r,int n) /設(shè)置監(jiān)視哨設(shè)置監(jiān)視哨for(int i=2;i=n;i+)/進(jìn)行進(jìn)行n-1次插入，依次插入次插入，依次插入 /r2,r3,rn r0=ri; /r0是監(jiān)視哨是監(jiān)視哨 /順序比較和移動(dòng)，查找順序比較和移動(dòng)，查找ri的插入位置的插入位置 for(int j=i-1;r0rj;j-) rj+1=rj; /記錄后移，繼續(xù)向前搜索記錄后移，繼續(xù)向前搜索 rj+1=r0; /插入插入ri r0為為監(jiān)視哨監(jiān)視哨（Sentinel），省略下標(biāo)越界檢查），省略下標(biāo)越界檢查“j1”：一旦越界，：一旦越界，j=01，循環(huán)，循環(huán)條件條件r0 n/2 的結(jié)點(diǎn)都是葉子，以這些結(jié)點(diǎn)為根的

31、的結(jié)點(diǎn)都是葉子，以這些結(jié)點(diǎn)為根的子樹(shù)均已是堆。（即葉子已是堆）子樹(shù)均已是堆。（即葉子已是堆）q依次將以序號(hào)為依次將以序號(hào)為 n/2 ， n/2 1,1的結(jié)點(diǎn)作的結(jié)點(diǎn)作為根的子樹(shù)都調(diào)整為堆。為根的子樹(shù)都調(diào)整為堆。q按該次序調(diào)整各結(jié)點(diǎn)時(shí)，其左、右子樹(shù)均已是堆。按該次序調(diào)整各結(jié)點(diǎn)時(shí)，其左、右子樹(shù)均已是堆。堆排序堆排序 1 19 98 810106 616162 211114 45 5n=10，故從第，故從第 10/2 5個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行調(diào)整個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行調(diào)整 1 19 98 810106 616162 211115 54 41 19 98 810106 611112 216165 54 41 19 9

32、8 810106 611112 216165 54 41 19 98 810106 6111116162 25 54 41 19 98 810106 62 2161611115 54 416169 98 810106 62 21 111115 54 416169 98 810106 62 211111 15 54 416169 98 81 16 62 2111110105 54 4堆排序堆排序 堆調(diào)整堆調(diào)整篩選法篩選法 關(guān)鍵問(wèn)題：完全二叉樹(shù)中，根結(jié)點(diǎn)的左右子關(guān)鍵問(wèn)題：完全二叉樹(shù)中，根結(jié)點(diǎn)的左右子樹(shù)均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完全二叉樹(shù)樹(shù)均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完全二叉樹(shù)成為一個(gè)堆？成為

33、一個(gè)堆？ (a) 28與與35交換交換(b) 28與與32交換交換(c) 將將28篩到葉子篩到葉子283218201218201235321820123535283228堆排序堆排序 qRi左、右子樹(shù)是堆，子樹(shù)的根為各自子樹(shù)中關(guān)鍵字最大者，左、右子樹(shù)是堆，子樹(shù)的根為各自子樹(shù)中關(guān)鍵字最大者，q將將Ri和其左、右孩子中關(guān)鍵字最大者進(jìn)行比較。和其左、右孩子中關(guān)鍵字最大者進(jìn)行比較。若若Ri最大，則無(wú)需調(diào)整，以其為根的子樹(shù)已是堆；最大，則無(wú)需調(diào)整，以其為根的子樹(shù)已是堆；否則，將否則，將Ri和具有最大關(guān)鍵字的左孩子和具有最大關(guān)鍵字的左孩子R2i或右孩子或右孩子R2i+1進(jìn)行交換。進(jìn)行交換。q交換后以交換后

34、以R2i和和R2i+1為根的子樹(shù)可能不再是堆，但其左、為根的子樹(shù)可能不再是堆，但其左、右子樹(shù)仍然是堆，于是重復(fù)上述過(guò)程，右子樹(shù)仍然是堆，于是重復(fù)上述過(guò)程，將子樹(shù)調(diào)整為堆將子樹(shù)調(diào)整為堆，如此逐層遞推下去，最多可能一直調(diào)整到樹(shù)葉。如此逐層遞推下去，最多可能一直調(diào)整到樹(shù)葉。q這一過(guò)程就像過(guò)篩子一樣，把較小的關(guān)鍵字篩下去，而將最大這一過(guò)程就像過(guò)篩子一樣，把較小的關(guān)鍵字篩下去，而將最大關(guān)鍵字一層層地選擇上來(lái)。關(guān)鍵字一層層地選擇上來(lái)。 堆調(diào)整堆調(diào)整篩選法篩選法19 98 810106 62 21611115 54 4大根堆大根堆16169 98 810106 62 21 111115 54 416169

35、98 810106 62 211111 15 54 416169 98 81 16 62 2111110105 54 4 設(shè)要篩選結(jié)點(diǎn)的編號(hào)為設(shè)要篩選結(jié)點(diǎn)的編號(hào)為k，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為n，并，并且結(jié)點(diǎn)且結(jié)點(diǎn)k的左右子樹(shù)均是堆（即的左右子樹(shù)均是堆（即rk+1 rn滿足堆的條件滿足堆的條件) ) 算法算法5.3篩選法調(diào)整堆篩選法調(diào)整堆 1. 設(shè)置設(shè)置i和和j，分別指向當(dāng)前要篩選的結(jié)點(diǎn)和要篩選結(jié)點(diǎn)的左孩子；，分別指向當(dāng)前要篩選的結(jié)點(diǎn)和要篩選結(jié)點(diǎn)的左孩子； 2. 若結(jié)點(diǎn)若結(jié)點(diǎn)i已是葉子，則篩選完畢；否則，比較要篩選結(jié)點(diǎn)的左右已是葉子，則篩選完畢；否則，比較要篩選結(jié)點(diǎn)的左

36、右 孩子結(jié)點(diǎn)，并將孩子結(jié)點(diǎn)，并將j指向關(guān)鍵碼較大的結(jié)點(diǎn)；指向關(guān)鍵碼較大的結(jié)點(diǎn)； 3. 將要篩選結(jié)點(diǎn)將要篩選結(jié)點(diǎn)i的關(guān)鍵碼與結(jié)點(diǎn)的關(guān)鍵碼與結(jié)點(diǎn)j的關(guān)鍵碼進(jìn)行比較，有以下兩種的關(guān)鍵碼進(jìn)行比較，有以下兩種情況：情況： 3.1 如果結(jié)點(diǎn)如果結(jié)點(diǎn)i的關(guān)鍵碼大，則完全二叉樹(shù)已經(jīng)是堆；的關(guān)鍵碼大，則完全二叉樹(shù)已經(jīng)是堆； 3.2 否則將否則將ri與與rj交換；令交換；令i=j，轉(zhuǎn)步驟，轉(zhuǎn)步驟2繼續(xù)進(jìn)行篩選；繼續(xù)進(jìn)行篩選；時(shí)間性能是時(shí)間性能是O(log2n)。 堆調(diào)整堆調(diào)整篩選法篩選法算法算法5.4篩選法調(diào)整堆篩選法調(diào)整堆 void SiftHeap( (int r , int k, int n) ) i=k;

37、 j=2*i; /置置i為要篩的結(jié)點(diǎn)，為要篩的結(jié)點(diǎn)，j為為i的左孩子的左孩子 while ( (j=n) ) /篩選還沒(méi)有進(jìn)行到葉子篩選還沒(méi)有進(jìn)行到葉子 if ( (jn & rjrj) ) /根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者 break; else rirj; /將根結(jié)點(diǎn)與結(jié)點(diǎn)將根結(jié)點(diǎn)與結(jié)點(diǎn)j交換交換 i=j; j=2*i; /被篩結(jié)點(diǎn)位于原來(lái)結(jié)點(diǎn)被篩結(jié)點(diǎn)位于原來(lái)結(jié)點(diǎn)j的位置的位置 C+描述堆調(diào)整堆調(diào)整篩選法篩選法16169 98 81 16 62 2111110105 54 4交換交換篩選篩選交換交換篩選篩選4 49 98 81 16 62 2111

38、110105 5161611119 98 81 16 62 210104 45 516162 29 98 81 16 6111110104 45 51616經(jīng)過(guò)跟剛才一樣的步驟經(jīng)過(guò)跟剛才一樣的步驟堆排序堆排序交換交換篩選篩選交換交換篩選篩選10109 98 81 16 611115 54 42 216161 19 98 810106 611115 54 42 216169 98 81 110106 611115 54 42 216161 18 89 910106 611115 54 42 21616交換交換篩選篩選交換交換篩選篩選8 86 69 910101 111115 54 42 2161

39、61 16 69 910108 811115 54 42 216166 61 19 910108 811115 54 42 216162 21 19 910108 811115 54 46 61616交換交換篩選篩選交換交換篩選篩選5 51 19 910108 811114 42 26 616162 21 19 910108 811114 45 56 616164 41 19 910108 811112 25 56 616161 14 49 910108 811112 25 56 61616交換交換2 24 49 910108 811111 15 56 616161 14 49 910108

40、811112 25 56 61616第第5章章 減治法減治法 5.1 概述概述 5.2 查找問(wèn)題中的減治法查找問(wèn)題中的減治法5.3 排序問(wèn)題中的減治法排序問(wèn)題中的減治法5.4 組合問(wèn)題中的減治法組合問(wèn)題中的減治法閱讀材料閱讀材料 假幣問(wèn)題的復(fù)雜版本假幣問(wèn)題的復(fù)雜版本5.4 組合問(wèn)題中的減治法組合問(wèn)題中的減治法 5.4.1 淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題 5.4.2 假幣問(wèn)題假幣問(wèn)題淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題問(wèn)題問(wèn)題 假設(shè)有假設(shè)有n=2k個(gè)選手進(jìn)行個(gè)選手進(jìn)行競(jìng)技淘汰賽競(jìng)技淘汰賽，最后決出冠，最后決出冠軍的選手，請(qǐng)?jiān)O(shè)計(jì)淘汰賽的過(guò)程。軍的選手，請(qǐng)?jiān)O(shè)計(jì)淘汰賽的過(guò)程。想法想法 分治法是將所有選手分成兩部

41、分，每部分決出分治法是將所有選手分成兩部分，每部分決出勝者后，讓這些勝者再進(jìn)行比賽，最后決出冠軍。勝者后，讓這些勝者再進(jìn)行比賽，最后決出冠軍。減治法：將所有選手分成減治法：將所有選手分成n/2組，每組兩個(gè)選手比賽，組，每組兩個(gè)選手比賽，敗者被淘汰，然后再將剩余選手分成敗者被淘汰，然后再將剩余選手分成n/4組，每組兩個(gè)組，每組兩個(gè)選手進(jìn)行比賽，選手進(jìn)行比賽，直到剩余最后兩個(gè)選手決出冠軍。直到剩余最后兩個(gè)選手決出冠軍。12( )2 ( /2) 12nT nT nnT（n）=O(n)算法算法5.8淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題 string Game(string r , int n) i=n; wh

42、ile (i1) i=i/2; for (j=0; ji; j+) if (Comp(rj+i, rj) rj=rj+i; /勝者放在勝者放在 rj 中中, j=0,1,2,i/2 -1 return r0; C+描述淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題算法分析算法分析 因?yàn)橐驗(yàn)閚=2k，所以，外層的，所以，外層的while循環(huán)共循環(huán)共執(zhí)行執(zhí)行k次，在每一次執(zhí)行時(shí)，內(nèi)層的次，在每一次執(zhí)行時(shí)，內(nèi)層的for循環(huán)的執(zhí)行循環(huán)的執(zhí)行次數(shù)分別是次數(shù)分別是n/2，n/4，1，而函數(shù)，而函數(shù)comp可以在可以在常數(shù)時(shí)間內(nèi)完成，因此，算法常數(shù)時(shí)間內(nèi)完成，因此，算法5.8的執(zhí)行時(shí)間為：的執(zhí)行時(shí)間為：)(1)211 (2)

43、(1nOnnnnTkkii-淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題5.4 組合問(wèn)題中的減治法組合問(wèn)題中的減治法 5.4.1 淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題 5.4.2 假幣問(wèn)題假幣問(wèn)題假幣問(wèn)題假幣問(wèn)題? ? 問(wèn)題問(wèn)題 在在n枚枚外觀相同的硬幣中，外觀相同的硬幣中，有一枚是假幣有一枚是假幣，并且并且已知假幣較輕已知假幣較輕?？梢酝ㄟ^(guò)一架天平來(lái)任意比?？梢酝ㄟ^(guò)一架天平來(lái)任意比較兩組硬幣，從而得知兩組硬幣的重量是否相同，較兩組硬幣，從而得知兩組硬幣的重量是否相同，或者哪一組更輕一些，但不知道輕多少，或者哪一組更輕一些，但不知道輕多少，假幣問(wèn)假幣問(wèn)題是要求設(shè)計(jì)一個(gè)高效的算法來(lái)檢測(cè)出這枚假幣題是要求設(shè)計(jì)一個(gè)高效的算法來(lái)檢測(cè)出這枚假幣。 2n假幣問(wèn)題假幣問(wèn)題 在假幣問(wèn)題中，在假幣問(wèn)題中，每次用天平比較后每次用天平比較后，只需解決一只需解決一個(gè)規(guī)模減半的問(wèn)題個(gè)規(guī)模減半的問(wèn)題，所以，所以，它屬于