算法課件-第5章-減治法

第5章減治法主要內(nèi)容：

5.1插入排序

5.2深度優(yōu)先查找與廣度優(yōu)先查找

5.3拓?fù)渑判?/p>

5.4生成組合對(duì)象的算法

5.5減常因子算法5.6減可變規(guī)模算法減治法的基本思想將規(guī)模為n的問(wèn)題遞減為規(guī)模為n-1或n/2的子問(wèn)題,反復(fù)遞減后對(duì)子問(wèn)題分別求解,再建立子問(wèn)題的解與原問(wèn)題的解的關(guān)系。減治法有三個(gè)變形:減常數(shù)(如1):每次迭代規(guī)模減1，即n→n-1

減因子(如1/2):每次迭代規(guī)模減半，即n→n/2

減可變規(guī)模:每次迭代減小的規(guī)模不同減（一）治技術(shù)規(guī)模為n的問(wèn)題規(guī)模為n-1的子問(wèn)題子問(wèn)題的解原始問(wèn)題的解例如：f(n)=anf(n)=f(n-1)*an>1f(n)=an=14減（半）治技術(shù)規(guī)模為n的問(wèn)題規(guī)模為n/2的子問(wèn)題子問(wèn)題的解原始問(wèn)題的解an=(an/2)2n是偶數(shù)an=(a(n-1)/2)2*an是奇數(shù)an=an=15.1插入排序插入排序的過(guò)程類(lèi)似玩牌時(shí)整理手中紙牌的過(guò)程。它的基本思想是：每步將一個(gè)待排序的對(duì)象按照其關(guān)鍵字的大小，插到前面已經(jīng)排好序的序列中的適當(dāng)位置，直到全部對(duì)象插入完畢為止。常用的插入排序有：直接插入排序、折半插入排序、鏈表插入排序和希爾排序（縮小增量排序），它們劃分的依據(jù)是在排好序的序列中尋找插入位置所使用方法的不同。直接插入排序偽代碼ALGORITHMInsertionSort(A[0..n-1])//對(duì)給定序列進(jìn)行直接插入排序//輸入：大小為n的無(wú)序序列A//輸出：按非遞減排列的序列Afori←1ton-1do temp←A[i] j←i-1 whilej≥0andA[j]>tempdo A[j+1]←A[j] j←j–1 A[j+1]←temp直接插入排序舉例待排序序列{89,45,68,90,29,34,17}插入過(guò)程:{89}不需比較{45,89}{45,68,89}{45,68,89,90}{29,45,68,89,90}{29,34,45,6889,90}{17,29,34,45,68,89,90}

插入次數(shù)=n-1=6比較次數(shù)=?直接插入排序效率分析基本操作:比較比較次數(shù)C(n):

最壞的情形,每次插入需比較已插入的所有元素,此時(shí),第i次插入比較i個(gè)元素,故思考題思考：當(dāng)n=1時(shí)，問(wèn)題的解如何？當(dāng)n>1時(shí)，問(wèn)題的解與n=1時(shí)有什么關(guān)系？運(yùn)送一個(gè)士兵需要4次橫渡，故總共需要4n次橫渡。思考題參考5.4.2節(jié)生成子集5.2深度優(yōu)先和廣度優(yōu)先查找1、深度優(yōu)先查找可以從任何頂點(diǎn)開(kāi)始訪問(wèn)圖的頂點(diǎn)，每次迭代時(shí)，處理與當(dāng)前頂點(diǎn)相鄰的未訪問(wèn)頂點(diǎn)。用棧來(lái)跟蹤深度優(yōu)先查找的操作最方便。DFS的偽代碼（1）PseudocodeforDepth-first-searchofgraphG=(V,E)：DFS(G)count:=0

未訪問(wèn)的頂點(diǎn)標(biāo)記為0foreachvertexv∈Vdoifv的標(biāo)記為0dfs(v)dfs(v)count:=count+1

頂點(diǎn)v

標(biāo)記為countforeachvertexwadjacenttovdoifwismarkedwith0dfs(w)DFS的偽代碼（2）ALGORITHMDFS(G)//對(duì)給定圖使用深度優(yōu)先搜索進(jìn)行遍歷;//輸入：圖的鄰接表表示結(jié)點(diǎn)個(gè)數(shù)為N;//輸出：各個(gè)結(jié)點(diǎn)輸出順序數(shù)組fori←0toN-1do VisitArray[i]←0//訪問(wèn)數(shù)組初始為0count←0fori←0toN-1do ifVisitArray[i]=0 dfs(V)//調(diào)用子函數(shù)dfs進(jìn)行深度優(yōu)先遍歷dfs(V)//使用深度優(yōu)先搜索對(duì)鄰接表進(jìn)行遍歷//輸入：結(jié)點(diǎn)V的鄰接表;//輸出：各個(gè)結(jié)點(diǎn)輸出順序數(shù)組count←count+1;VisitArray[V]←count//記錄訪問(wèn)的次序tmp←V.linkwhiletmp≠Nulldo ifVisitArray[tmp.vertex]≠0dfs(tmp.vertex)深度優(yōu)先舉例abefcdgh一個(gè)DFS輸出序列：

a-b-f-e-g-c-d-h深度優(yōu)先搜索的效率與圖的表示有關(guān)對(duì)鄰接矩陣表示的圖：遍歷的效率為

Θ(V2)對(duì)鄰接鏈表表示的圖：遍歷的效率為

Θ(V+E)2、廣度優(yōu)先查找可以從任何頂點(diǎn)開(kāi)始訪問(wèn)圖的頂點(diǎn)，每次迭代時(shí)，處理所有與當(dāng)前頂點(diǎn)相鄰的未訪問(wèn)頂點(diǎn)。用隊(duì)列來(lái)跟蹤廣度優(yōu)先查找的操作較方便。BFS的偽代碼（1）BFS(G)count:=0標(biāo)記每個(gè)頂點(diǎn)v=0foreachvertexv∈Vdobfs(v)bfs(v)count:=count+1標(biāo)記v=count初始化頂點(diǎn)序列vwhile序列非空doa:=frontofqueueforeachvertexwadjacenttoadoifwismarkedwith0count:=count+1markwwithcountaddwtotheendofthequeueremoveafromthefrontofthequeueBFS的偽代碼（2）ALGORITHMBFS(G)//輸入：圖的鄰接表表示結(jié)點(diǎn)個(gè)數(shù)為N；//輸出：各個(gè)結(jié)點(diǎn)輸出順序數(shù)組fori←0toN-1do VisitArray[i]←0 //訪問(wèn)數(shù)組初始為0count←0fori←0toN-1doifVisitArray[i]=0bfs(V)//調(diào)用子函數(shù)bfs進(jìn)行廣度優(yōu)先遍歷

ALGORITHMbfs(V)//使用廣度優(yōu)先搜索對(duì)鄰接表進(jìn)行遍歷//輸入：結(jié)點(diǎn)V的鄰接表；//輸出：各個(gè)結(jié)點(diǎn)輸出順序數(shù)組count←count+1;VisitArray[V]←count //記錄訪問(wèn)的次序Queue.Enqueue(V) //把源結(jié)點(diǎn)加入到隊(duì)列中whilenotQueue.Emptydo tmp←Queue.Dequeue//取隊(duì)頭結(jié)點(diǎn)掃描判斷

whiletmp≠Nulldo ifVisitArray[tmp.vertex]=0 count←count+1 Queue.Enqueue(tmp)//把未訪問(wèn)的結(jié)點(diǎn)加入到

VisitArray[tmp.vertex]←count//記錄訪問(wèn)次序

tmp←tmp.link //訪問(wèn)鄰接表下一個(gè)結(jié)點(diǎn)BFS舉例一個(gè)BFS的輸出序列：

a-b-e-f-g-c-h-dabefcdghDFS與BFS的比較

DFSBFS數(shù)據(jù)結(jié)構(gòu)臨時(shí)棧(stack)隊(duì)列(queue)邊類(lèi)型樹(shù)與回邊(backedges)樹(shù)與交叉邊(crossedges)鄰接鏈表的效率鄰接矩陣的效率應(yīng)用判斷是否有環(huán)判斷是否連通求關(guān)節(jié)點(diǎn)(articulationpoints)判斷是否有環(huán)判斷是否連通求最短路徑(minimum-edgepaths)Θ(V+E)Θ(V+E)Θ(V2)Θ(V2)5.3拓?fù)渑判蛟诖髮W(xué)學(xué)習(xí)的過(guò)程中，各門(mén)課程的學(xué)習(xí)是有先后順序的，有些課程需要先修課程，有些則不需要；有些課程之間有先后的關(guān)系，有些課程則可以并行的進(jìn)行。問(wèn)題要求確定一個(gè)學(xué)習(xí)方案使得各門(mén)課程的學(xué)習(xí)能夠有序進(jìn)行。拓?fù)渑判騿?wèn)題：對(duì)給定的無(wú)環(huán)有向圖，要求按照某種順序列出它的頂點(diǎn)序列，使圖的每一條邊的起點(diǎn)總在結(jié)束頂點(diǎn)之前。求拓?fù)湫蛄械姆椒?方法1、應(yīng)用DFS的出棧次序。DFS序列：

C1-C3-C4-C5--C2

出棧序列：

C5-C4-C3-C1-C2拓?fù)渑判颍?/p>

C2-C1-C3-C4-C5注：1、注意遍歷到死端點(diǎn)時(shí)的出棧次序

2、拓?fù)渑判虿晃ㄒ籆1C3C2C5C4求拓?fù)湫蛄械姆椒?方法2、減治法，每次選擇沒(méi)有輸入的點(diǎn)。容易得到一個(gè)拓?fù)湫蛄校篜-W-S-M-F-H-T即：微生物-小麥-羊-

-小蝦-魚(yú)-人-虎F魚(yú)H人M小蝦S羊W小麥P微生物T虎本節(jié)作業(yè)思考題：習(xí)題5.1-1,5.1-7,5.2-10,5.3-3,5.3-9作業(yè)：習(xí)題5.1-4，5.2-1，5.3-15.4生成組合對(duì)象的算法1、生成排列排列問(wèn)題指的是對(duì)于給定的多個(gè)元素求其中各種可能的序列。為了簡(jiǎn)單起見(jiàn)，這里僅僅考慮1到n之間的整數(shù)的排列問(wèn)題。下面介紹三種生成方法：（1）插入法（2）Johnson-Trotter法（3）字典順序法插入法生列排列舉例：求n=3的排列方法（自頂向下）：

在n=2的排列中插入3，在n=1的排列中插入2。自底向上生成排列的過(guò)程：在1中從右到左插入2得到12，21在12中從右到左插入3得到123，132，312在21中從右到左插入3得到213，231，321

于是得{123，132，312，213，231，321}Johnson-Trotter法生成排列其實(shí)有的算法并不需要知道規(guī)模n-1的排列就可以直接得到規(guī)模n的排列結(jié)果，Johnson-Trotter算法就是其中一種。利用這一算法求得的排列序列還是相鄰序列變化最小的一個(gè)序列集合，也就是說(shuō)下一個(gè)序列與上一個(gè)序列僅僅交換了兩個(gè)元素的位置。J-T方法舉例在排列的每一分量上畫(huà)一個(gè)箭頭。求最大的移動(dòng)整數(shù)k，不斷移動(dòng)元素，直到?jīng)]有元素可移動(dòng)為止，掉轉(zhuǎn)所有大于k的整數(shù)方向。移動(dòng)元素：如果分量k的箭頭指向一個(gè)相鄰的較小元素，則該分量在排列中是移動(dòng)的。例n=3,從123開(kāi)始：字典順序生成排列盡管Johnson-Trotter算法非常高效，但是似乎不是那么直觀，不太符合人們的思維習(xí)慣。事實(shí)上比較自然的算法稱(chēng)為“字典排序（lexicographicorder）算法”，它是根據(jù)單詞在字典中的排列順序得到的算法。字典生成順序舉例例n=3在{1，2，3}中按字典順序選擇：

123

132

213

231

312

3212、生成子集集合A的“冪集”是指以集合A的所有子集為元素組成的集合。降低規(guī)模的減治法可以用來(lái)求冪集。

減治法的缺點(diǎn)也是在求解規(guī)模為n的問(wèn)題時(shí)，需要得到規(guī)模為n-1的問(wèn)題的解。這一過(guò)程是可以避免的，使用位串法求解集合冪集就是其中的一種解決方案。減治法生成冪集例n=3方法：在n=2的冪集中加入元素3，在n=1的冪集中加入元素2，在n=0的冪集中加入元素1

,{1}//n=1

,{1},{2},{1,2}//加入元素2,{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}//加入元素3位串法生成冪集例n=3,元素為{a1,a2,a3}方法：每一個(gè)子集與一個(gè)3位二進(jìn)制串b1b2b3對(duì)應(yīng)，ai屬于該子集時(shí)，bi=1,否則bi=0二進(jìn)制串：000,001,010,011,100,101,110,111對(duì)應(yīng)子集：

,{a3},{a2},{a2,a3},{a1},{a1,a3},{a1,a2},{a1,a2,a3}我們可以產(chǎn)生從0到2n-1的二進(jìn)制數(shù)來(lái)生成長(zhǎng)度為n的所有二進(jìn)制串5.5減常因子法1、假幣問(wèn)題

有n個(gè)金幣，其中一個(gè)是假幣。這個(gè)假幣的重量比真幣的重量要輕一點(diǎn)，所有n-1個(gè)金幣的重量是一樣的。現(xiàn)在你有一架天平，設(shè)計(jì)高效的算法（用最少的使用天平次數(shù)）找出那個(gè)假的金幣。

假幣問(wèn)題解法1、用減治法（減半）

把n個(gè)硬幣分為兩堆，每堆n/2個(gè)，每次稱(chēng)兩堆。易見(jiàn)W(1)=0

W(n)=W(n/2)+1

解得W(n)=log2n假幣問(wèn)題解法2、用減治法(減n/3）

把n個(gè)硬幣分為三堆，每堆n/3個(gè)，每次稱(chēng)任意二堆。易見(jiàn) W(1)=0 當(dāng)n=1

W(n)=W(n/3)+1 當(dāng)n>1

解得W(n)=O(log3n)，結(jié)果比減半法更好。假幣問(wèn)題實(shí)例：n=9用方法1（減半法）需要稱(chēng)3次。用方法2（減n/3法）需要稱(chēng)2次。

過(guò)程：

將9個(gè)金幣分為3個(gè)組，每組3個(gè)金幣。

將其中的兩組放在天平的兩邊，如果有一邊輕，說(shuō)明假的金幣就在這個(gè)組里。如果兩邊一樣重，說(shuō)明假的金幣在第三個(gè)組里。

在有假幣的組中，拿出兩個(gè)金幣，放在天平的兩邊，如果有一個(gè)輕，則這個(gè)輕的就是假幣，如果兩個(gè)一樣重，則剩下的一個(gè)就是假幣。2、俄式乘法/俄國(guó)農(nóng)民法

設(shè)n、m是整數(shù)，以n為實(shí)例規(guī)模的度量。若n為偶數(shù)，則

n·m=(n/2)·2m若n為奇數(shù)，則

n·m=((n-1)/2)·2m+m以1·m=m為算法停止的條件。俄國(guó)農(nóng)民法舉例:50×65nm分析.506550×65=25×13025130+13025×130=12×260+1301226065203104012080=3250

3、約瑟夫斯問(wèn)題約瑟夫斯是公元1世紀(jì)的猶太歷史學(xué)家，他領(lǐng)導(dǎo)了反抗羅馬人的武裝起義，但是失敗了。他和四十名猶太士兵被羅馬人圍困在一個(gè)山洞中。這四十個(gè)士兵寧死不屈，決定殺身成仁。但約瑟夫斯不想，但又不便公開(kāi)反對(duì)，于是提出一個(gè)方法，就是四十一個(gè)人站成一個(gè)圈，從某人開(kāi)始數(shù)起，凡數(shù)到三的人就讓大家成全他升天，這樣下去直到剩下最后一個(gè)人，這個(gè)人就自殺。大家都沒(méi)有意見(jiàn)，于是約瑟夫斯就挑選了第31號(hào)的位置。結(jié)果所有人都死了，剩下他一個(gè)活下來(lái)投降了羅馬人。這也是約瑟夫斯問(wèn)題的最初提法。約瑟夫斯問(wèn)題

約瑟夫斯問(wèn)題的一般提法：設(shè)有n個(gè)以1、2、…、n編號(hào)的人，按編號(hào)順序圍成一圈，從1號(hào)開(kāi)始報(bào)數(shù)，每數(shù)到m就淘汰一人，問(wèn)最后被淘汰的人是幾號(hào)呢？令L(n,m)為上述最后被淘汰的人的號(hào)碼，則可以將最初的約瑟夫斯問(wèn)題寫(xiě)成L(41,3)＝31。對(duì)于具體不同的n、m，求其計(jì)算公式。約瑟夫斯問(wèn)題分析當(dāng)m＝2時(shí)，公式是：L(n,2)＝2b＋1。

其中b是這樣得出的，把n寫(xiě)成2a＋b，而a必須盡可能大。例如當(dāng)n=100，則100可以寫(xiě)成25＋68，也可以寫(xiě)成26＋36，但是不能再寫(xiě)成27的了，所以，a=6，而b=36。

L(6,2)=2×2+1=5,//6=22+2,b=2L(7,2)=2×3+1=7,//7=22+3

,b=3

L(13,2)=2×5+1=11,//13=23+5,b=5約瑟夫斯問(wèn)題分析當(dāng)m＝3、4、…時(shí)，有沒(méi)有公式呢？但存在一個(gè)L(n,m)遞推公式：

L(1,m)＝1

L(k＋1,m)≡L(k,m)＋mmod

(n+1)減可變規(guī)模算法歐幾里得算法計(jì)算中值和選擇問(wèn)題插值查找二叉查找樹(shù)的查找和插入拈游戲計(jì)算中值和選擇問(wèn)題選擇問(wèn)題是求一個(gè)n個(gè)數(shù)列表的第k個(gè)最小元素的問(wèn)題。這個(gè)數(shù)字被稱(chēng)為第k個(gè)順序統(tǒng)計(jì)量

k＝1或者k＝n的情況，就是求列表的最小或最大元素時(shí)，要求找出這樣一個(gè)元素，該元素比列表中的一半元素大，比另一半元素小，這個(gè)值被稱(chēng)為中值。計(jì)算中值和選擇問(wèn)題方法：

利用快速排序的分區(qū)方法，將數(shù)組分成兩部分，分割點(diǎn)的下標(biāo)為s，右邊部分大于樞軸值p，左邊部分小于樞軸值p。若s=k則結(jié)束；若s>k，則在左邊繼續(xù)找第k小的元素；若s<k，則在右邊繼續(xù)找第k-s小的元素；計(jì)算中值和選擇問(wèn)題例1找到下面9個(gè)數(shù)的中值：4，1，10，9，7，12，8，2，15，那么k=54 110 9 7 12 8 2 152 14 9 7 12 8 10 15S＝3<K＝5，所以處理右邊部分

9 7 12 8 10 15 8 7 9 12 10 15S＝6>K＝5，所以處理左邊部分

7 8中值＝8

插值查找插值查找用于查找有序數(shù)組不同于折半查找總是把查找鍵和給定有序數(shù)組的中間元素進(jìn)行比較（每次規(guī)模消減一半）插入查找為了找到用來(lái)和查找鍵進(jìn)行比較的數(shù)組元素，考慮了查找鍵的值精確地說(shuō)，如果某次迭代處理的是數(shù)組位于最左邊元素A[l]和最右邊元素A[r]之間的一部分，該算法假設(shè)數(shù)組的值是線(xiàn)性遞增的（該假設(shè)的精確度會(huì)影響算法的效率，但不會(huì)影響算法的正確性）插值查找值下標(biāo)lxrA[l]vA[r]二叉查找樹(shù)的查找和插入二叉查找樹(shù)：每個(gè)節(jié)點(diǎn)一個(gè)元素，并使得對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)，所有左子樹(shù)的元素都小于子樹(shù)根節(jié)點(diǎn)的元素，所有右子樹(shù)的元素都大于子樹(shù)根節(jié)點(diǎn)的元素。查找元素v：如果子樹(shù)為空，查找失敗如果不為空，則把v和該樹(shù)的根K(r)比較相等就是找到了

v<K(r)則在左子樹(shù)中查找

v>K(r)則在右子樹(shù)中查找二叉查找樹(shù)的查找和插入一棵查找樹(shù)的規(guī)模的最佳度量就是樹(shù)的高度最壞情況就是當(dāng)這棵樹(shù)是單支樹(shù)時(shí)是Θ(n)平均效率為Θ(logn)，更精確來(lái)說(shuō)，查找一棵由n個(gè)隨機(jī)鍵構(gòu)造起來(lái)的二叉查找樹(shù)所需的鍵值比較次數(shù)大約是二叉搜索樹(shù)算法：ALGORITHMBstSearch(R,k)//二叉搜索樹(shù)上搜索算法的遞歸實(shí)現(xiàn)//輸入：以R為根的二叉搜索樹(shù)，待搜索值k//輸出：搜索成功時(shí)，返回k在樹(shù)中的位置，否則返回空值ifR=NullreturnNullelseifR.data>k returnBstSearch(R.leftChild,k)elseifA.data<k returnBstSearch(R.rightChild,k)ElsereturnRALGORITHMBstSearch2(R,k)//二叉搜索樹(shù)上搜索算法的迭代實(shí)現(xiàn)//輸入：以R為根的二叉搜索樹(shù)，待搜索值k//輸出：搜索成功時(shí)，返回k在樹(shù)中的位置，否則返回空值tmp←Rwhiletmp≠Nulldo iftmp.data=kreturntmp elseiftmp.data>k tmp←tmp.leftChild else tmp←tmp.rightChildreturnNull拈游戲單堆棋子版本有一堆n

個(gè)棋子兩個(gè)玩家輪流從堆中拿走最小1個(gè)