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

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

第二頁(yè)，共六十三頁(yè)，編輯于2023年，星期三3減常數(shù)(如1):每此迭代規(guī)模減小n→n-1第三頁(yè)，共六十三頁(yè)，編輯于2023年，星期三4減因子(如1/2):每此迭代規(guī)模減半n→n/2第四頁(yè)，共六十三頁(yè)，編輯于2023年，星期三5

減可變規(guī)模:每此迭代減小的規(guī)模不同第五頁(yè)，共六十三頁(yè)，編輯于2023年，星期三6減常量：5.1插入排序

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

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

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

5.5減常因子算法5.6減可變規(guī)模算法第六頁(yè)，共六十三頁(yè)，編輯于2023年，星期三75.1插入排序如何用減一法對(duì)一個(gè)數(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]，在這個(gè)有序數(shù)組中處于何處？常用的插入排序有：直接插入排序、折半插入排序它們劃分的依據(jù)是在排好序的序列中尋找插入位置所使用方法的不同。第七頁(yè)，共六十三頁(yè)，編輯于2023年，星期三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ù)=?第八頁(yè)，共六十三頁(yè)，編輯于2023年，星期三9直接插入排序偽代碼ALGORITHMInsertionSort(A[0..n-1])//對(duì)給定序列進(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第九頁(yè)，共六十三頁(yè)，編輯于2023年，星期三10直接插入排序效率分析基本操作:比較比較次數(shù)C(n):

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

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

Θ(V2)

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

Θ(V+E)第十七頁(yè)，共六十三頁(yè)，編輯于2023年，星期三185.2廣度優(yōu)先查找一個(gè)BFS輸出序列是？

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

Θ(V2)

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

Θ(V+E)第十九頁(yè)，共六十三頁(yè)，編輯于2023年，星期三20總結(jié)

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

C1-C3-C4-C5--C2

出棧序列：

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

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

-小蝦-魚-人-虎F魚H人M小蝦S羊W小麥P微生物T虎第二十四頁(yè)，共六十三頁(yè)，編輯于2023年，星期三255.4生成組合對(duì)象的算法1、生成排列排列問題指的是對(duì)于給定的多個(gè)元素求其中各種可能的序列。為了簡(jiǎn)單起見，這里僅僅考慮1到n之間的整數(shù)的排列問題。下面介紹三種生成方法：（1）插入法（2）Johnson-Trotter法（3）字典順序法第二十五頁(yè)，共六十三頁(yè)，編輯于2023年，星期三26插入法生列排列如何用減一法構(gòu)造n規(guī)模與n-1規(guī)模問題之間的關(guān)系？將第n個(gè)數(shù)插入到(n-1)!個(gè)排列的n個(gè)可能位置中去。第二十六頁(yè)，共六十三頁(yè)，編輯于2023年，星期三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}第二十七頁(yè)，共六十三頁(yè)，編輯于2023年，星期三28插入法生列排列-優(yōu)點(diǎn)滿足最小變化的要求第二十八頁(yè)，共六十三頁(yè)，編輯于2023年，星期三29Johnson-Trotter法生成排列其實(shí)有的算法并不需要知道規(guī)模n-1的排列就可以直接得到規(guī)模n的排列結(jié)果，Johnson-Trotter算法就是其中一種。利用這一算法求得的排列序列還是相鄰序列變化最小的一個(gè)序列集合，也就是說下一個(gè)序列與上一個(gè)序列僅僅交換了兩個(gè)元素的位置。第二十九頁(yè)，共六十三頁(yè)，編輯于2023年，星期三30J-T方法舉例在排列的每一分量上畫一個(gè)箭頭。移動(dòng)元素：如果分量k的箭頭指向一個(gè)相鄰的較小元素，則該分量在排列中是移動(dòng)的。求最大的移動(dòng)整數(shù)k，不斷移動(dòng)元素，直到?jīng)]有元素可移動(dòng)為止，掉轉(zhuǎn)所有大于k的整數(shù)方向。例n=3,從123開始：第三十頁(yè)，共六十三頁(yè)，編輯于2023年，星期三31字典順序生成排列盡管Johnson-Trotter算法非常高效，但是似乎不是那么直觀，不太符合人們的思維習(xí)慣。事實(shí)上比較自然的算法稱為“字典排序（lexicographicorder）算法”，它是根據(jù)單詞在字典中的排列順序得到的算法。第三十一頁(yè)，共六十三頁(yè)，編輯于2023年，星期三32字典生成順序舉例例n=3在{1，2，3}中按字典順序選擇：

123

132

213

231

312

321第三十二頁(yè)，共六十三頁(yè)，編輯于2023年，星期三33基本思想：從右到左掃描一個(gè)當(dāng)前排列，尋找第一對(duì)連續(xù)的元素ai和ai+1，ai<ai+1ai+1及后面的元素什么特點(diǎn)？在ai+1及后面的元素中尋找大于ai的最小數(shù)字放到i的位置上ai，ai+1。an按升序從i+1位置排到n第三十三頁(yè)，共六十三頁(yè)，編輯于2023年，星期三342、生成子集考慮如何用減一法生成規(guī)模為n的集合的所有子集？如何建立n規(guī)模和n-1規(guī)模的關(guān)系在n-1規(guī)模集合的所有子集中添加第n個(gè)元素第三十四頁(yè)，共六十三頁(yè)，編輯于2023年，星期三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第三十五頁(yè)，共六十三頁(yè)，編輯于2023年，星期三36位串法生成冪集這是一個(gè)直接解決該問題的方法，可以對(duì)較小的集合生成冪集例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}第三十六頁(yè)，共六十三頁(yè)，編輯于2023年，星期三375.5減常因子法已有例子折半查找、用平方求冪注意：不要指望有許多這種類型的例子，因?yàn)檫@種算法的效率常常是對(duì)數(shù)的，速度非?？欤⒉粫?huì)時(shí)常出現(xiàn)，不以2為因子化簡(jiǎn)的情況更是少之又少。第三十七頁(yè)，共六十三頁(yè)，編輯于2023年，星期三381、假幣問題

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

考慮用蠻力法，如何解？時(shí)間效率類型是？減治法？可類比于折半查找。第三十八頁(yè)，共六十三頁(yè)，編輯于2023年，星期三39假幣問題解法1、用減治法(減半）

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

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

解得W(n)=log2n第三十九頁(yè)，共六十三頁(yè)，編輯于2023年，星期三40假幣問題解法2、用減治法(減n/3）

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

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

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

=3250整個(gè)算法只包括折半加倍相加優(yōu)勢(shì)？第四十二頁(yè)，共六十三頁(yè)，編輯于2023年，星期三43

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

約瑟夫斯問題的一般提法：設(shè)有n個(gè)以1、2、…、n編號(hào)的人，按編號(hào)順序圍成一圈，從1號(hào)開始報(bào)數(shù)，每數(shù)到m就淘汰一人，問最后被淘汰的人是幾號(hào)呢？令L(n,m)為上述最后被淘汰的人的號(hào)碼，即幸存者的初始位置。則可以將最初的約瑟夫斯問題寫成L(41,3)＝31。第四十四頁(yè)，共六十三頁(yè)，編輯于2023年，星期三45減治法的體現(xiàn)在于，整個(gè)圓圈走一遍后，規(guī)模減小1／m如m=2，走一圈后生成同樣問題的規(guī)模減1/2的實(shí)例m=3，走一圈后生成同樣問題的規(guī)模減1/3的實(shí)例考慮m=2時(shí)，如何得到幸存者的初始位置？當(dāng)n為偶數(shù)時(shí)，某人前一輪的位置=新位置×2-1為什么？幸存者的初始位置L(n,2)=2L(n/2,2)-1當(dāng)n為奇數(shù)時(shí)，L(n,2)=2L((n-1)/2,2)+1解這兩個(gè)遞推式獲得幸存者的初始位置的表達(dá)式。第四十五頁(yè)，共六十三頁(yè)，編輯于2023年，星期三46約瑟夫斯問題分析還可使用前向替代法，找出一個(gè)模式即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。第四十六頁(yè)，共六十三頁(yè)，編輯于2023年，星期三47約瑟夫斯問題分析當(dāng)m＝3、4、…時(shí)，有沒有公式呢？但存在一個(gè)L(n,m)遞推公式：

L(1,m)＝1

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

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

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

第五十二頁(yè)，共六十三頁(yè)，編輯于2023年，星期三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}

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