1、數(shù)據(jù)分析與算法設(shè)計(jì)第4章減治法內(nèi) 容 提 要排序拓?fù)渑判?.14.24.34.44.5生成組合對(duì)象的算法減常因子算法 減可變規(guī)模算法2017/10/1824 減治法減治法（Decrease-and-Conquer）：利用一個(gè)問(wèn)題給定實(shí)例的解和同樣問(wèn)題較小實(shí)基本例的解之間的某種關(guān)系，將問(wèn)題的規(guī)模遞減，然后基于小規(guī)模問(wèn)題的解，得到大規(guī)模問(wèn)題的解。可以自頂而下（遞歸），也可以自底而上（非遞歸）3個(gè)主要變種：減常量（如減一：每次迭代規(guī)模減小 n n-1）減常量因子（如減半：每次迭代規(guī)模減半n n/2）(m,減可變規(guī)模（每次迭代減小的規(guī)模不同，如：n) =(n, m mod n)2017/10/1834

2、 減治法減（一）治技術(shù)例：計(jì)算an遞歸方式：非遞歸方式：自底而上，把a(bǔ)自乘n-1次2017/10/1844 減治法減（半）治技術(shù)例：計(jì)算an減（半）治：分治：效率不高2017/10/1854 減治法減可變規(guī)模每次迭代時(shí)，規(guī)模減小的模式都是不同的例：計(jì)算最大公約數(shù)的算法2017/10/1864 減治法4.1排序排序的過(guò)程類(lèi)似玩牌時(shí)整理手中紙牌的過(guò)程基本：每步將一個(gè)待排序的對(duì)象按照其關(guān)鍵字的大小，插到前面已經(jīng)排好序的序列中的適當(dāng)位置，直到全部對(duì)象減一技術(shù)！完畢為止。常用的、鏈表排序有：直接排序、折半排序排序和排序，它們劃分的依據(jù)是在位置所使用方法的不同。排好序的序列中尋找2017/10/1874

3、減治法直接排序2017/10/1884 減治法直接排序舉例待排序序列89,45,68,90,29,34,17過(guò)程:89不需比較45,8945,68,8945,68, 89,9029,45,68, 89,9029,34,45,68 89, 9017,29,34,45,68, 89, 90次數(shù)=n-1=6比較次數(shù)=?2017/10/1894 減治法直接排序的效率分析基本操作：比較的情形：的所有元素，此時(shí)，第i次插每次需比較已入需要比較i個(gè)元素。輸入是一個(gè)嚴(yán)格遞減的序列！2017/10/18104 減治法直接最好的情形：排序的效率分析只需比較1次。每次輸入是一個(gè)已經(jīng)排好序的序列！平均效率：輸入為隨機(jī)

4、無(wú)序的序列！效率快2倍2017/10/18比114 減治法4.2拓?fù)渑判騿?wèn)題：在大學(xué)學(xué)習(xí)的過(guò)程中，各門(mén)課程的學(xué)習(xí)是有先后順序的，有些課程需要先修課程，有些則不需要；有些課程之間有先后的關(guān)系，有些課程則可以并行的進(jìn)行。要求確定一個(gè)學(xué)習(xí)方案使得各門(mén)課程的學(xué)習(xí)能夠有序進(jìn)行。抽象為拓?fù)渑判騿?wèn)題：對(duì)給定的無(wú)環(huán)有向圖，要求按照某種順序列出它的頂點(diǎn)序列，使圖的每一條邊的起點(diǎn)頂點(diǎn)之前。結(jié)束2017/10/18124 減治法算法1：基于DFS頂點(diǎn)變成端點(diǎn)（出棧）的順序執(zhí)行DFS遍歷，將出棧順序倒過(guò)來(lái)就得到了拓?fù)渑判虻囊粋€(gè)解拓?fù)漤樞虿晃ㄒ?017/10/18134 減治法算法2：基于減（一）治技術(shù)拓?fù)漤樞虿晃ㄒ?

5、017/10/18144 減治法4.3生成組合對(duì)象的算法4.3.1 生成排列對(duì)于給定的多個(gè)元素，生成各種可能的排列假設(shè)元素的下標(biāo)為1,n，簡(jiǎn)化為下標(biāo)的排列問(wèn)題介紹三種生成方法：（1）法Johnson-Trotter 法字典順序法2017/10/18154 減治法法生列排列減一法：生成1,n-1的排列，對(duì)每個(gè)排列，插入n，得到1,n的排列。共有n個(gè)位置可，的順序：從右到左從左到右從右到左交替改變方向好處：最小變化相鄰兩個(gè)排列的變化：只需交換某2個(gè)相鄰元素2017/10/18164 減治法Johnson-Trotter 法生成排列其實(shí)有的算法并不需要知道規(guī)模n-1的排列就可以直接得到規(guī)模n的排列結(jié)

6、果，Johnson-Trotter算法就是其中一種。利用這一算法求得的排列序列還是相鄰序列變化最小的一個(gè)序列集合，也就是說(shuō)下一個(gè)序列與上一個(gè)序列僅僅交換了兩個(gè)元素的位置 。2017/10/18174 減治法Johnson-Trotter 方法在排列的每一分量上畫(huà)一個(gè)箭頭。移動(dòng)元素：如果分量k 的箭頭指向一個(gè)相鄰的較小元素，則該分量在排列中是移動(dòng)的。2017/10/18184 減治法J-T方法舉例例n=3,從123開(kāi)始：符合最小變化要求2017/10/18194 減治法字典順序生成排列盡管Johnson-Trotter算法非常高效，但是似乎不是那么直觀，不太符合人們的思維習(xí)慣。事實(shí)上比較自然的算

7、法稱(chēng)為“字典排序（lexicographic order）算法”，它是根據(jù)單詞在字典中的排列順序得到的算法。2017/10/18204 減治法字典生成順序舉例例n=3，在1，2，3中按字典順序選擇：123，132，213，231，312，3212017/10/18214 減治法字典序排列生成算法2017/10/18224 減治法4.3.2生成子集集合A的“冪集”：以A的所有子集為元素組成的集合。減（一）治技術(shù)生成子集2017/10/18234 減治法位串法生成冪集例n=3，元素為a1,a2,a3方法： 每一個(gè)子集與一個(gè)3位二進(jìn)制串b1b2b3對(duì)應(yīng)，ai屬于該子集時(shí)，bi=1，否則 bi=0二進(jìn)

8、制串：000, 001, 010,對(duì)應(yīng)子集：011,100,101,110,111 ,a3,a2, a2,a3,a1, a1,a3, a1,a2, a1,a2,a3比特串的其他順序擠壓序最小變化：相鄰比特串只變化一個(gè)比特（碼）2017/10/18244 減治法碼生成算法2017/10/18254 減治法4.4 減常因子法4.4.1 折半查找通過(guò)比較查找鍵K 和數(shù)組中間元素Am來(lái)完成查找工作。如果它們相等，算法結(jié)束。否則，如果K Am . 則對(duì)數(shù)組的后半部分執(zhí)行該操作。例：K702017/10/18264 減治法折半查找偽代碼2017/10/18274 減治法折半查找效率分析基本操作：三路比較情

9、況：平均效率：精確公式：2017/10/18284 減治法4.4.2問(wèn)題有n個(gè)金幣，其中一個(gè)是。這個(gè)的重量比真幣的重量要輕一點(diǎn)，所有n-1個(gè)金幣的重量是一樣的?，F(xiàn)在你有一架天平，設(shè)計(jì)高效的算法（用最少的使用天平次數(shù)）找出那個(gè)金幣。2017/10/18294 減治法問(wèn)題解法1、用減治法（減半）把n個(gè)硬幣分為兩堆，每堆n/2個(gè)稱(chēng)一次，可確定在哪一堆效率分析：類(lèi)似折半查找W(1)=0W(n)=W(n/2)+1解得 W(n)= log2n2017/10/18304 減治法問(wèn)題解法2、用減治法（減n/3）把n個(gè)硬幣分為三堆，每堆n/3（或+1）個(gè)，每次稱(chēng)任意二堆， 可確定在哪一堆效率分析： (log3n

10、)比減半法更好2017/10/18314 減治法問(wèn)題實(shí)例：n=9用方法1（減半法）需要稱(chēng)用方法2（減n/3法）需要稱(chēng)過(guò)程：3次。2次。將9個(gè)金幣分為3個(gè)組，每組3個(gè)金幣。將其中的兩組放在天平的兩邊，如果有一邊輕，說(shuō)明說(shuō)明在有金幣就在這個(gè)組里。如果兩邊一樣重，金幣在第三個(gè)組里。的組中，拿出兩個(gè)金幣，放在天平的兩邊，如果有一個(gè)輕，則這個(gè)輕的就是兩個(gè)一樣重，則剩下的一個(gè)就是，如果。2017/10/18324 減治法4.4.3俄式乘法/農(nóng)夫法設(shè)n、m是整數(shù)，以n為實(shí)例規(guī)模的度量。若n為偶數(shù)，則nm=(n/2) 2m若n為奇數(shù)，則nm=(n-1)/2) 2m+m以1m=m為算法停止的條件。2017/10

11、/18334 減治法俄式乘法舉例: 5065若采用二進(jìn)制表達(dá)，主要操作是移位和相加，適合機(jī)器實(shí)現(xiàn)2017/10/18344 減治法4.4.4斯問(wèn)題Josephus problem斯是公元1世紀(jì)的猶太歷史學(xué)家，他了反抗羅馬人的，但是失敗了。他和40名猶太士兵被羅馬人圍困在一個(gè)山洞中。這40個(gè)士兵寧死不屈，決定殺身成仁。但斯不想，但又不便公開(kāi)，于是提出一個(gè)方法：41個(gè)人站成一個(gè)圈，從（1號(hào)）開(kāi)始報(bào)數(shù)（1,2,1,2），凡數(shù)到2的人就讓大家成全他升天。這樣下去直到剩下最后一個(gè)人，這個(gè)人就。斯選擇了最后個(gè)，一起投降羅馬。者的位置，說(shuō)服倒數(shù)第22017/10/18354 減治法斯問(wèn)題斯問(wèn)題的一般提法：設(shè)

12、有n個(gè)以1、2、n的人，按順序圍成一圈，從1號(hào)開(kāi)始報(bào)數(shù)，每數(shù)到m就淘汰一人，問(wèn)最后被淘汰的人是幾號(hào)呢？令L(n, m)為上述最后被淘汰的人的號(hào)碼，則可斯問(wèn)題寫(xiě)成L(41, 2)19。以將最初的對(duì)于具體不同的n、m，求其計(jì)算公式。2017/10/18364 減治法斯問(wèn)題分析當(dāng)m2時(shí)，應(yīng)用減治法：n為偶數(shù)：J(2k) = 2J(k) 1n為奇數(shù)：J(2k+1) = 2J(k) + 1根據(jù)遞推公式求解閉合表達(dá)式？其他方法？2017/10/18374 減治法斯問(wèn)題分析當(dāng)m2時(shí)，公式是：L(n,2)2b1。其中b是這樣得出的，把n寫(xiě)成2ab，而a必須盡可能大。例如當(dāng)n=100，則100可以寫(xiě)成2568，

13、也可以寫(xiě)成2636，但是不能再寫(xiě)成27的了，所以，a=6，而b=36。L(6,2)=22+1=5,L(13,2)= 25+1=11,L(41,2)= 29+1=19,/ 6=22+2, b=2/ 13=23+5, b=5/ 41=25+9, b=92017/10/18384 減治法斯問(wèn)題分析當(dāng)m3、4、時(shí)，有沒(méi)有公式呢？但存在一個(gè)L(n,m) 遞推公式：L(1,m)1L(k1,m) (L(k,m)m) mod (k+1)減（一）治的！2017/10/18394 減治法4.5減可變規(guī)模算法4.5.1計(jì)算中值和選擇問(wèn)題選擇問(wèn)題：求一個(gè)n元數(shù)組的第k個(gè)最小元素（順序統(tǒng)計(jì)量）當(dāng)k=n/2時(shí)，該元素被稱(chēng)

14、為中值。先全部排好序，再選擇？沒(méi)有必要方法：利用快速排序的分區(qū)方法，將數(shù)組分成兩部分，一部分大于值p， 一部分小于值p， 分割點(diǎn)s。若s = （k-1），則結(jié)束若s （k-1），則在左邊繼續(xù)找若s （k-1），則在右邊繼續(xù)找2017/10/18404 減治法2017/10/18414 減治法2017/10/18424 減治法2017/10/18434 減治法4.5.2插值查找原理：是查找有序數(shù)組的一種算法。設(shè)某次迭代處理的是數(shù)組最左邊元素Al和最右邊元素Ar之間的部分，要查找的鍵值為v。寫(xiě)出過(guò)點(diǎn)(l,Al)和點(diǎn)(r,Ar)的直線方程，取 y=v，求出橫坐標(biāo)x，比較Ax與v的值，決定是停止，還是

15、在l與x-1之間或x+1與r之間繼續(xù)查找。與折半查找比較根據(jù)查找鍵值，估計(jì)可能位置類(lèi)似本查名字、查字典2017/10/18444 減治法插值查找的效率average case: C(n) log2 log2 n + 1worst case: C(n) = nPreferable to binary search only for VERY large arrays and/or expensive comparisons2017/10/18454 減治法4.5.3二叉查找樹(shù)查找和所謂的二叉查找樹(shù)，它或者是一棵空樹(shù)，或者滿足以下的性質(zhì)：每個(gè)結(jié)點(diǎn)作為搜索對(duì)象，它的關(guān)鍵字是互不相同的對(duì)于樹(shù)上的所有結(jié)

16、點(diǎn)，如果它有樹(shù)，那么樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字都小于該結(jié)點(diǎn)的關(guān)鍵字。對(duì)于樹(shù)上的所有結(jié)點(diǎn)，如果它有右子樹(shù)，那么右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字都大于該結(jié)點(diǎn)的關(guān)鍵字。2017/10/18464 減治法二叉查找樹(shù)的算法與分析Algorithm BTS(x, v)/Searches for node with key equal to v in BST rooted at node xif x = NILreturn -1else ifelse ifv = K(x)v K(x)return xreturn BTS(left(x), v)else return BTS(right(x), v)Efficiencywo

17、rst case:C(n) = naverage case: C(n) 2ln n 1.39log2n2017/10/18474 減治法2017/10/18484 減治法4.5.4le Nim拈（Nim）OnThere is a pile of n chips. Two players take turn byremoving from thleeast 1 and at most m chips.(The Thenumber of chips taken can vary from move to move.)winner is the playert takes the last chip

18、.Who wins thegame the player movingmake the best movesor second, if both player sible?Its a good idea toyze this and similar games“backwards”, i.e., starting with n = 0, 1, 2, 2017/10/18494 減治法Onle Nim with m = 4Vertex numbers indicate n, the number of chipshle.Thelosingition for the player to move are circled.Only