算法設計與分析減治法

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

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

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

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

5.3拓撲排序

5.4生成組合對象的算法

5.5減常因子算法5.6減可變規(guī)模算法第六頁，共六十三頁，編輯于2023年，星期三75.1插入排序如何用減一法對一個數組A[0..n-1]排序？也就是如何建立n規(guī)模與n-1規(guī)模之間的關系？假設n-1規(guī)模的數組A[0..n-2]已經解決，則需要考慮元素A[n-1]，在這個有序數組中處于何處？常用的插入排序有：直接插入排序、折半插入排序它們劃分的依據是在排好序的序列中尋找插入位置所使用方法的不同。第七頁，共六十三頁，編輯于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}

插入次數=n-1=6比較次數=?第八頁，共六十三頁，編輯于2023年，星期三9直接插入排序偽代碼ALGORITHMInsertionSort(A[0..n-1])//對給定序列進行直接插入排序//輸入：大小為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第九頁，共六十三頁，編輯于2023年，星期三10直接插入排序效率分析基本操作:比較比較次數C(n):

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

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

Θ(V2)

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

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

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

Θ(V2)

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

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

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

C1-C3-C4-C5--C2

出棧序列：

C5-C4-C3-C1-C2拓撲排序：

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

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

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

123

132

213

231

312

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

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

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

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

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

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

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

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

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

解得W(n)=log3n結果比減半法更好。是否分堆數越多越好？第四十頁，共六十三頁，編輯于2023年，星期三412、俄式乘法/俄國農民法非主流算法設n、m是整數，以n為實例規(guī)模的度量。若n為偶數，則

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

n·m=((n-1)/2)·2m+m以1·m=m為算法停止的條件。第四十一頁，共六十三頁，編輯于2023年，星期三42俄國農民法舉例:50×65nm分析.50652513012260+13065203104012080+10402080+2080

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

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

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

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

L(1,m)＝1

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

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

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

第五十二頁，共六十三頁，編輯于2023年，星期三53數組{4,1,10,9,7,12,8,2,15},求中值元素即求第k=9/2=5小的元素。使用快速排序中的分區(qū)算法先數組{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第五十三頁，共六十三頁，編輯于2023年，星期三54效率分析平均情況下：和快速排序比要高效嚴格的數學分析表明，平均情況下的效率和每次都消減一半情況下的效率是完全相同的。每次都消減一半的遞推式是？C(n)=C(n/2)+(n+1)第五十四頁，共六十三