算法設(shè)計與分析減治法

關(guān)于算法設(shè)計與分析減治法第一頁，共六十三頁，2022年，8月28日2減治法的基本思想將規(guī)模為n的問題遞減為規(guī)模為n-1或n/2的子問題,反復(fù)遞減后對子問題分別求解,再建立子問題的解與原問題的解的關(guān)系。

第二頁，共六十三頁，2022年，8月28日3減常數(shù)(如1):每此迭代規(guī)模減小n→n-1第三頁，共六十三頁，2022年，8月28日4減因子(如1/2):每此迭代規(guī)模減半n→n/2第四頁，共六十三頁，2022年，8月28日5

減可變規(guī)模:每此迭代減小的規(guī)模不同第五頁，共六十三頁，2022年，8月28日6減常量：5.1插入排序

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

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

5.4生成組合對象的算法

5.5減常因子算法5.6減可變規(guī)模算法第六頁，共六十三頁，2022年，8月28日75.1插入排序如何用減一法對一個數(shù)組A[0..n-1]排序？也就是如何建立n規(guī)模與n-1規(guī)模之間的關(guān)系？假設(shè)n-1規(guī)模的數(shù)組A[0..n-2]已經(jīng)解決，則需要考慮元素A[n-1]，在這個有序數(shù)組中處于何處？常用的插入排序有：直接插入排序、折半插入排序它們劃分的依據(jù)是在排好序的序列中尋找插入位置所使用方法的不同。第七頁，共六十三頁，2022年，8月28日8直接插入排序舉例待排序序列{89,45,68,90,29,34,17}插入過程:{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ù)=?第八頁，共六十三頁，2022年，8月28日9直接插入排序偽代碼ALGORITHMInsertionSort(A[0..n-1])//對給定序列進(jìn)行直接插入排序//輸入：大小為n的無序序列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第九頁，共六十三頁，2022年，8月28日10直接插入排序效率分析基本操作:比較比較次數(shù)C(n):

最壞的情形是嚴(yán)格遞減的數(shù)組每次插入,需比較已插入的所有元素,此時,第i次插入比較i個元素,故第十頁，共六十三頁，2022年，8月28日11最好的情況？升序排列每次插入只需比較一次第十一頁，共六十三頁，2022年，8月28日12平均效率的精確分析基于對無序元素的研究，對于隨機(jī)序列的數(shù)組，第十二頁，共六十三頁，2022年，8月28日13評價插入排序最差Θ(n2)最優(yōu)Θ(n)平均Θ(n2)合并排序最差Θ(nlog2n)快速排序最優(yōu)Θ(nlog2n)最差Θ(n2)平均Θ(1.38nlog2n)選擇排序 Θ(n2)冒泡排序 Θ(n2)遇到基本有序數(shù)組表現(xiàn)優(yōu)異性能，可結(jié)合快速排序第十三頁，共六十三頁，2022年，8月28日145.2深度優(yōu)先查找一個DFS輸出序列是？

a-c-d-f-b-e-g-h-i-j第十四頁，共六十三頁，2022年，8月28日15在數(shù)據(jù)結(jié)構(gòu)中如何表示圖？第十五頁，共六十三頁，2022年，8月28日16在深度優(yōu)先遍歷時需要使用到什么輔助結(jié)構(gòu)？寫出出棧和入棧的過程第十六頁，共六十三頁，2022年，8月28日17深度優(yōu)先搜索的效率與圖的表示有關(guān)嗎？對鄰接矩陣表示的圖：遍歷的效率為

Θ(V2)

對鄰接鏈表表示的圖：遍歷的效率為

Θ(V+E)第十七頁，共六十三頁，2022年，8月28日185.2廣度優(yōu)先查找一個BFS輸出序列是？

a-c-d-e-f-b-g-h-j-i在廣度優(yōu)先遍歷時需要使用到什么輔助結(jié)構(gòu)？第十八頁，共六十三頁，2022年，8月28日19廣度優(yōu)先搜索的效率與圖的表示有關(guān)嗎？對鄰接矩陣表示的圖：遍歷的效率為

Θ(V2)

對鄰接鏈表表示的圖：遍歷的效率為

Θ(V+E)第十九頁，共六十三頁，2022年，8月28日20總結(jié)

DFSBFS數(shù)據(jù)結(jié)構(gòu)臨時棧(stack)隊列(queue)頂點(diǎn)順序的種類兩種順序一種順序鄰接鏈表的效率鄰接矩陣的效率應(yīng)用判斷是否有環(huán)判斷是否連通求關(guān)節(jié)點(diǎn)判斷是否有環(huán)判斷是否連通求最短路徑Θ(V+E)Θ(V+E)Θ(V2)Θ(V2)第二十頁，共六十三頁，2022年，8月28日215.3拓?fù)渑判蛟诖髮W(xué)學(xué)習(xí)的過程中，各門課程的學(xué)習(xí)是有先后順序的，有些課程需要先修課程，有些則不需要；有些課程之間有先后的關(guān)系，有些課程則可以并行的進(jìn)行。問題要求確定一個學(xué)習(xí)方案使得各門課程的學(xué)習(xí)能夠有序進(jìn)行。拓?fù)渑判騿栴}：對給定的無環(huán)有向圖，要求按照某種順序列出它的頂點(diǎn)序列，使圖的每一條邊的起點(diǎn)總在結(jié)束頂點(diǎn)之前。第二十一頁，共六十三頁，2022年，8月28日22Example:Orderthemfromlowertohigher,consistentwithfoodchainF魚H人M小蝦S羊W小麥P微生物T虎第二十二頁，共六十三頁，2022年，8月28日23求拓?fù)湫蛄械姆椒?方法1、應(yīng)用DFS的出棧次序。DFS序列：

C1-C3-C4-C5--C2

出棧序列：

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

C2-C1-C3-C4-C5思考為什么這個算法是有效的？C1C3C2C5C4第二十三頁，共六十三頁，2022年，8月28日24求拓?fù)湫蛄械姆椒?方法2、如何用減一法？N規(guī)模和n-1規(guī)模如何建立聯(lián)系？容易得到一個拓?fù)湫蛄校篜-W-S-M-F-H-T即：微生物-小麥-羊-

-小蝦-魚-人-虎F魚H人M小蝦S羊W小麥P微生物T虎第二十四頁，共六十三頁，2022年，8月28日255.4生成組合對象的算法1、生成排列排列問題指的是對于給定的多個元素求其中各種可能的序列。為了簡單起見，這里僅僅考慮1到n之間的整數(shù)的排列問題。下面介紹三種生成方法：（1）插入法（2）Johnson-Trotter法（3）字典順序法第二十五頁，共六十三頁，2022年，8月28日26插入法生列排列如何用減一法構(gòu)造n規(guī)模與n-1規(guī)模問題之間的關(guān)系？將第n個數(shù)插入到(n-1)!個排列的n個可能位置中去。第二十六頁，共六十三頁，2022年，8月28日27插入法生列排列舉例：求n=3的排列方法：在n=2的排列中插入3，在n=1的排列中插入2。構(gòu)造過程（從底向上）：在1中從右到左插入2得到12，21在12中從右到左插入3得到123，132，312在21中從右到左插入3得到213，231，321

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

123

132

213

231

312

321第三十二頁，共六十三頁，2022年，8月28日33基本思想：從右到左掃描一個當(dāng)前排列，尋找第一對連續(xù)的元素ai和ai+1，ai<ai+1ai+1及后面的元素什么特點(diǎn)？在ai+1及后面的元素中尋找大于ai的最小數(shù)字放到i的位置上ai，ai+1。an按升序從i+1位置排到n第三十三頁，共六十三頁，2022年，8月28日342、生成子集考慮如何用減一法生成規(guī)模為n的集合的所有子集？如何建立n規(guī)模和n-1規(guī)模的關(guān)系在n-1規(guī)模集合的所有子集中添加第n個元素第三十四頁，共六十三頁，2022年，8月28日35減治法生成冪集例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第三十五頁，共六十三頁，2022年，8月28日36位串法生成冪集這是一個直接解決該問題的方法，可以對較小的集合生成冪集例n=3,元素為{a1,a2,a3}方法：每一個子集與一個3位二進(jìn)制串b1b2b3對應(yīng)，ai屬于該子集時，bi=1,否則bi=0二進(jìn)制串：000,001,010,011,100,101,110,111對應(yīng)子集：

,{a3},{a2},{a2,a3},{a1},{a1,a3},{a1,a2},{a1,a2,a3}第三十六頁，共六十三頁，2022年，8月28日375.5減常因子法已有例子折半查找、用平方求冪注意：不要指望有許多這種類型的例子，因為這種算法的效率常常是對數(shù)的，速度非?？?，并不會時常出現(xiàn)，不以2為因子化簡的情況更是少之又少。第三十七頁，共六十三頁，2022年，8月28日381、假幣問題

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

考慮用蠻力法，如何解？時間效率類型是？減治法？可類比于折半查找。第三十八頁，共六十三頁，2022年，8月28日39假幣問題解法1、用減治法(減半）

把n個硬幣分為兩堆，每堆n/2個，每次稱一堆。請寫出遞推式易見W(1)=0

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

解得W(n)=log2n第三十九頁，共六十三頁，2022年，8月28日40假幣問題解法2、用減治法(減n/3）

把n個硬幣分為三堆，每堆n/3個，每次稱任意二堆。易見W(1)=0

W(n)=W(n/3)+a

解得W(n)=log3n結(jié)果比減半法更好。是否分堆數(shù)越多越好？第四十頁，共六十三頁，2022年，8月28日412、俄式乘法/俄國農(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為算法停止的條件。第四十一頁，共六十三頁，2022年，8月28日42俄國農(nóng)民法舉例:50×65nm分析.50652513012260+13065203104012080+10402080+2080

=3250整個算法只包括折半加倍相加優(yōu)勢？第四十二頁，共六十三頁，2022年，8月28日43

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

約瑟夫斯問題的一般提法：設(shè)有n個以1、2、…、n編號的人，按編號順序圍成一圈，從1號開始報數(shù)，每數(shù)到m就淘汰一人，問最后被淘汰的人是幾號呢？令L(n,m)為上述最后被淘汰的人的號碼，即幸存者的初始位置。則可以將最初的約瑟夫斯問題寫成L(41,3)＝31。第四十四頁，共六十三頁，2022年，8月28日45減治法的體現(xiàn)在于，整個圓圈走一遍后，規(guī)模減小1／m如m=2，走一圈后生成同樣問題的規(guī)模減1/2的實(shí)例m=3，走一圈后生成同樣問題的規(guī)模減1/3的實(shí)例考慮m=2時，如何得到幸存者的初始位置？當(dāng)n為偶數(shù)時，某人前一輪的位置=新位置×2-1為什么？幸存者的初始位置L(n,2)=2L(n/2,2)-1當(dāng)n為奇數(shù)時，L(n,2)=2L((n-1)/2,2)+1解這兩個遞推式獲得幸存者的初始位置的表達(dá)式。第四十五頁，共六十三頁，2022年，8月28日46約瑟夫斯問題分析還可使用前向替代法，找出一個模式即L(n,2)有什么規(guī)律？L(2,2)=1=2×0+12=21＋0L(3,2)=3=2×1+13=21＋1L(4,2)=1=2×0+14=22＋0L(5,2)=3=2×1+15=22＋1L(6,2)=5=2×2+16=22＋2L(7,2)=7=2×3+17=22＋3…………L(13,2)=11=2×5+113=23＋5L(n,2)＝2b＋1n=2a＋b(而a必須盡可能大)

例如當(dāng)n=100，則100可以寫成25＋68，也可以寫成26＋36，但是不能再寫成27的了，所以，a=6，而b=36。第四十六頁，共六十三頁，2022年，8月28日47約瑟夫斯問題分析當(dāng)m＝3、4、…時，有沒有公式呢？但存在一個L(n,m)遞推公式：

L(1,m)＝1

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

n+1)第四十七頁，共六十三頁，2022年，8月28日48約瑟夫問題集第一題：猴子選大王。題目：有M個猴子圍成一圈，每個有一個編號，編號從1到M。打算從中選出一個大王。經(jīng)過協(xié)商，決定選大王的規(guī)則如下：從第一個開始，每隔N個，數(shù)到的猴子出圈，最后剩下來的就是大王。要求：從鍵盤輸入M，N，編程計算哪一個編號的猴子成為大王。第二題：設(shè)有N個人圍成一圏，并且按照順時針方向從1到N編號，由第S個人開始進(jìn)行從1到M報數(shù)，報數(shù)到第M個人時，此人出圏，再從下一個人重新開始從1到M報數(shù)，如此進(jìn)行下去，直到所有的人都出圏為止?，F(xiàn)在要求編程按照出圏的順序，打印這N個人的順序表。第四十八頁，共六十三頁，2022年，8月28日49第三題：貍捉兔子圍繞著山頂有１０個洞，狐貍要吃兔子，兔子說：“可以，但必須找到我，我就藏身于這十個洞中，你從１０號洞出發(fā)，先到１號洞找，第二次隔１個洞找，第三次隔２個洞找，以后如此類推，次數(shù)不限?！钡倧脑绲酵磉M(jìn)進(jìn)出出了１０００次，仍沒有找到兔子。問兔子究竟藏在哪個洞里？第四十九頁，共六十三頁，2022年，8月28日50第四題：慈善的約瑟夫你一定聽說過約瑟夫問題吧？即從N個人找出唯一的幸存者。現(xiàn)在老約瑟夫?qū)⒔M織一個皆大歡喜的新游戲，假設(shè)N個人站成一圈，從第1人開始交替的去掉游戲者，但只是暫時去掉，直到最后剩下唯一的幸存者為止。幸存者選出后，所有比幸存者號碼高的人每人得到1個金幣，永久性離開。其余剩下的將重復(fù)以上的游戲過程，比幸存者號碼主的人每人得到1個金幣后離開。經(jīng)過這們的過程后，一旦人數(shù)不再減少，則最后剩下的那些人將得到2個金幣。請你計算一下老約瑟夫一共要付出多少錢？輸入：N輸出：金幣數(shù)。第五十頁，共六十三頁，2022年，8月28日51第五題：50枚棋子圍成圓圈，編上號碼1，2，3，…每隔一枚棋子取出一枚，要求最后留下的一枚棋子的號碼是42，那該從幾號棋子開始取呢？第六題：變形猴子選大王題目：有n個猴子選大王，選舉辦法如下：從頭到尾1，2，3報數(shù)，凡報到3的退出，余下的從尾到頭1，2，3報數(shù)，凡報3的退出。。。。如此類推，當(dāng)剩下兩只猴子時，取這時報1的為王，若想當(dāng)猴王，請問當(dāng)初應(yīng)站在什么位置？第五十一頁，共六十三頁，2022年，8月28日525.6減可變規(guī)模算法1、計算中值和選擇問題選擇問題：求一個n數(shù)組的第k個最小元素。一些特殊的情況

k=1k=nk=n/2，該元素被稱為中值例如，數(shù)組{4,1,10,9,7,12,8,2,15},求第5小的元素你能想到什么方法？排序

第五十二頁，共六十三頁，2022年，8月28日53數(shù)組{4,1,10,9,7,12,8,2,15},求中值元素即求第k=9/2=5小的元素。使用快速排序中的分區(qū)算法先數(shù)組{4,1,10,9,7,12,8,2,15}分區(qū),中軸=4{1,2}，{4}，{9,7,12,8,10,15},s=3因s<k,在{9,7,12,8,10,15}中找

{8,7},{9},{12,10,15},s=6因s>k,在{8,7}中找

{7},{8}

此時，s=k=5,中值是8第五十三頁，共六十三頁，2022年，8月28日54效率分析平均情況下：和快速排序比要高效嚴(yán)格的數(shù)學(xué)分析表明，平均情況下的效率和每次都消減一半情況下的效率是完全相同的。每次都消減一半的遞推式是？C(n)=C(n/2)+(n+1)第五十四頁，