試題選講課件

1、問題選講北京大學(xué) 姚金宇第一部分 基礎(chǔ)算法 車站 這是一個(gè)簡陋的小火車站，整個(gè)車站只由一個(gè)進(jìn)站口，一個(gè)出站口和一個(gè)棧道組成。如右圖?；疖囋谲囌居腥N調(diào)度情況：從進(jìn)站口進(jìn)入棧道從棧道進(jìn)入出站口從進(jìn)站口直接出站。車站其中棧道保證后進(jìn)先出?，F(xiàn)有n輛火車在進(jìn)站口等待出站，排列為1，2，n。你的任務(wù)是計(jì)算一共有多少種不同出站序列。例如n=3時(shí) 進(jìn)站序列為1，2，3。則一種可行的出站序列為3，1，2（調(diào)度方法為3進(jìn)棧，2出站，1出站，3從棧道出站）簡化操作我們將直接出站分成下列兩個(gè)連續(xù)的操作：從進(jìn)站口進(jìn)棧道從棧道進(jìn)出站口三種操作兩種操作之后無論用何種算法，都會(huì)大大提高解決問題的效率。遞推模型設(shè)f(i,j)

2、表示當(dāng)進(jìn)站口有i輛車，棧道中有j輛車，一共有多少種出站方式。f(i,j)=f(i-1, j+1) + f(i, j-1)邊界 f(0,i)=1則f(n,0)即為所求。ANNIVERSARY CAKE給你一個(gè)S*S的方形蛋糕，要求你將其切成n塊，每一塊是ai*ai的方形。要求沒有遺漏。輸入S,n及a1,an，判斷是否能夠得到一種滿足要求的切法。n=16，ai=10分析首先判斷若S*S!=sigam(ai*ai)，則必然無解。否則深度優(yōu)先搜索蛋糕的切法（實(shí)際上是枚舉小蛋糕塊的拼法）。每次找到最左上的一個(gè)空位置，易知這個(gè)位置一定是放置某一個(gè)小蛋糕塊的最左上角。這樣我們只需要再枚舉還未填入的一個(gè)小蛋糕

3、塊，若能夠填入，則繼續(xù)放入后繼續(xù)遞歸；否則判斷其他的小蛋糕塊。最左上角未被填入的空位置（約定判斷順序?yàn)橄壬虾笞螅┡袛嘣撔〉案鈮K能否填入優(yōu)化判斷小蛋糕塊能否放入的時(shí)候，只需要檢查最上邊緣有沒有被放置過蛋糕即可。這是因?yàn)槊看味际琴N著左上邊沿放蛋糕，若當(dāng)前蛋糕不能放置，則它的上邊緣一定有某個(gè)方格以前被放置過蛋糕了。這樣檢查的時(shí)間復(fù)雜度從O(n2)降到了O(n)在搜索的時(shí)候?qū)i進(jìn)行從大到小排序，先判斷大蛋糕，后判斷小蛋糕。在當(dāng)前層的搜索中，對(duì)于當(dāng)前的枚舉的ai，若當(dāng)前曾已經(jīng)枚舉過一個(gè)ak有ak=ai，則對(duì)于ai的枚舉就是重復(fù)的，需要剪枝。問題：還有什么剪枝嗎？求第K小數(shù)長度為n的序列a1,a2,an

4、，求其中的第k小數(shù)。分析可以先排序，然后直接確定第k小數(shù)。至少需要O(nlogn)的時(shí)間復(fù)雜度。其實(shí)我們沒有必要知道所有的有序信息。設(shè)一個(gè)pivot，若n個(gè)數(shù)中:b1,b2,bm都比pivot小;c1,c2,cn-m都不比pivot小則若k=m則第k小的數(shù)在b中否則所求的數(shù)在c中如何分？xpivoti1,jnWhile (i=j)If (aix) j-;If (i=j)Swap ai, aj;i+; j-;a1aj都比pivot小，aj+1an都不比pivot小PIVOT的選擇隨機(jī)在pivot隨機(jī)的情況下，該算法的期望是線性的。如何理解？有沒有最壞情況下是線性的算法？第二部分 字符串算法 最長

5、重復(fù)子串對(duì)于串S，若它存在一個(gè)子串T，T在S中至少出現(xiàn)兩次，則我們稱T是S的一個(gè)重復(fù)子串。求長度為n的串S的最長重復(fù)子串例如S=abcdacdac，則最長重復(fù)子串為cdac預(yù)備知識(shí)后綴串最長公共前綴串的模式匹配算法模式匹配的KMP算法字母樹第一種解法nexti的含義對(duì)每一個(gè)S的后綴S(pn)，求next數(shù)組，取出maxnexti-1就是該后綴的最長前綴重復(fù)串。算法的時(shí)間復(fù)雜度O(n2)第二種解法最長重復(fù)子串，必然是某兩個(gè)后綴串的最長公共前綴。將所有的后綴串建成一棵字母樹，即可求出任兩個(gè)后綴的最長公共前綴 a b b a a S=aba 該算法的時(shí)間復(fù)雜度也是O(n2)更好的算法本題可以用更高級(jí)

6、的數(shù)據(jù)結(jié)構(gòu)解決后綴數(shù)組后綴樹運(yùn)用它們可以得到O(nlogn)甚至O(n)的算法第三部分 數(shù)學(xué)問題SPECIAL SUBSET給定集合M=1，2，n，取出M的所有不包含相鄰自然數(shù)的子集合例如1,3就是一個(gè)符合要求的而1,3,4就不是對(duì)于每一個(gè)這樣的子集合Si，求它的元素之積Ti。例如對(duì)于Si=1,3,Ti=1*3=3輸出所有Ti的平方和例子n=4M=1,2,3,4S:1,2,3,4,1,3,2,4,1,4T:1,2,3,4,3,8,4T2:1,4,9,16,9,64,16輸出1+4+9+16+9+64+16=119當(dāng)問題的規(guī)模為N時(shí)第一種情況S集合只包含n，T=n*n第二種情況S集合包含n和其他

7、的數(shù)，則“其他的數(shù)”最大是n-2。第三種情況S集合不包含n，則“其他的數(shù)”最大是n-1n=4的情況4:4*41,4, 2, 4:(1*4)2 * (2*4)2=(1*1+2*2)*4*41231,3: (n=3的情況)抽象設(shè)Fi表示n=i時(shí)的平方和Fi=i*i +Fi-2*i*i +Fi-1O(n)的遞推算法CALLING EXTRATERRESTRIAL INTELLIGENCE AGAIN 給定三個(gè)整數(shù)m,a,b，求兩個(gè)正整數(shù)p, q滿足：p和q都是素?cái)?shù)p*q = ma/b = p/q = 1在滿足1-3的前提下，p*q最大數(shù)據(jù)范圍：4 m = 100000 ； 1 = a = b = 1

8、000.輸入文件包含有不超過2000組數(shù)據(jù)?；舅悸访杜e較小的素?cái)?shù)p，這樣q是滿足下面兩個(gè)情況下的最大的素?cái)?shù)：q=m/pq=p*b/a我們需要解決兩個(gè)子問題：找出素?cái)?shù)找出素?cái)?shù)序列中滿足要求的最大數(shù)素?cái)?shù)(PRIME)大于1的正整數(shù)p被稱作素?cái)?shù)，如果p僅有的正因子是1和p素?cái)?shù)判定理論：如果n是合數(shù)，則他必有一個(gè)小于或等于sqrt(n)的約數(shù)。操作：枚舉2至sqrt(n)的所有整數(shù)，判斷其中有無p的約數(shù)。時(shí)間復(fù)雜度：O(sqrt(n)ERAOSTHENES篩法（篩選法）問題：如何求2-n中所有的素?cái)?shù)？篩選法：建立一個(gè)表，給每個(gè)值標(biāo)記true從2到n枚舉每一個(gè)整數(shù)p，如果當(dāng)前p的標(biāo)記為true，則p為

9、素?cái)?shù)若當(dāng)前p為素?cái)?shù)，則將n以內(nèi)的p*p , p*(p+1),都標(biāo)記為false（被篩去）偽素?cái)?shù)測(cè)試費(fèi)馬小定理 如果p是一個(gè)素?cái)?shù)，則對(duì)于任意的a,若(a,p)=1，則 ap-1=1(mod p)n是一個(gè)正整數(shù)，若an-1=1(mod n)，我們說n是基于a的一個(gè)偽素?cái)?shù)。偽素?cái)?shù)測(cè)試若一個(gè)數(shù)是偽素?cái)?shù)，則它幾乎肯定是素?cái)?shù)；若一個(gè)數(shù)不是偽素?cái)?shù)，則它一定不是素?cái)?shù)。我們可以通過多次選取基數(shù)a（通常選取2,3,5,7進(jìn)行測(cè)試)，如果n都是偽素?cái)?shù)，則它幾乎可以肯定是素?cái)?shù)了?；氐皆瓎栴}篩選法求1-MAXM的素?cái)?shù)表的時(shí)間復(fù)雜度為O(n*ln(n)對(duì)于每一個(gè)詢問，枚舉p，在素?cái)?shù)表里面二分查找最大的滿足兩個(gè)條件的素?cái)?shù)即

10、可。枚舉p的時(shí)間復(fù)雜度為O(sqrt(n)二分查找q的時(shí)間復(fù)雜度為O(log2m)，其中m為素?cái)?shù)表的規(guī)模。關(guān)于二分在問題不好直接得到答案的時(shí)候，枚舉答案再進(jìn)行判斷往往是一個(gè)有效的辦法。這時(shí)候往往就要用到二分法典型例子：解奇數(shù)次的一元方程MATRIX MULTIPLICATION給定三個(gè)n*n的矩陣A，B，C判斷A*B是否等于C？關(guān)于矩陣矩陣的概念由英國數(shù)學(xué)家Sylvester于1850年首先提出1858年 英國數(shù)學(xué)家Cayley建立了矩陣運(yùn)算規(guī)則矩陣是一個(gè)強(qiáng)有力的工具，它能夠把一組相互獨(dú)立的數(shù)用一張數(shù)表的形式聯(lián)系起來，看成一個(gè)整體，并用它來參與運(yùn)算。用矩陣描述一個(gè)復(fù)雜物體是非常緊湊的矩陣在自然

11、科學(xué)、工程技術(shù)、社會(huì)科學(xué)等領(lǐng)域中有著廣泛的應(yīng)用矩陣定義由mn個(gè)數(shù)排成m行、n列的矩陣陣列：稱為 m 行 n 列矩陣，簡記為mn矩陣，A=稱 為 A 的第 i 行第 j 列元素。矩陣乘法_定義設(shè)A為ms矩陣，B為sn矩陣A與B的乘積為一mn矩陣C，定義如下：N階方陣的冪定義A1 = A, A2 = AA, A3 = A2A, , Ak = Ak-1AAk即為k個(gè)A相乘只有方陣的冪才有意義AkAl = Ak+l, (Ak)l = Akl矩陣的冪跟數(shù)的冪性質(zhì)很相似聯(lián)想：如何求(A)k回到原問題直接計(jì)算A*B，然后再與C進(jìn)行逐一元素的比對(duì)，這樣的時(shí)間復(fù)雜度是O(n3)聯(lián)想到素?cái)?shù)判定的偽素?cái)?shù)測(cè)試（必要條

12、件測(cè)試?。┘僭O(shè)有一個(gè)隨機(jī)的n*1的矩陣X，若A*B=C則必然有X*(A*B)=X*CX*(A*B)=(X*A)*B=Y*B，Y=X*A也是一個(gè)n*1的矩陣！計(jì)算X*A,Y*B,X*C的時(shí)間復(fù)雜度都是O(n2)問題的解決我們可以隨機(jī)產(chǎn)生k個(gè)X矩陣，進(jìn)行上述的測(cè)試。若全部滿足，則我們可以“幾乎”肯定A*B=C了。算法的時(shí)間復(fù)雜度O(n2)擴(kuò)展問題給定三個(gè)n*n的矩陣A,B,CA*B要么等于C，要么與C矩陣有一個(gè)元素不相同。判斷A*B是否等于C，若不相等，找出那個(gè)不相同元素的位置FLAVIUS JOSEPHUS RELOADED對(duì)于如下遞推方程：F1=C (CN)Fi=(aFi-1+b) mod N

13、求F的循環(huán)節(jié)長度a, b, N=109，保證循環(huán)節(jié)長度不超過106在跑圈的時(shí)候如果和同時(shí)起跑A的速度為1，B的速度為2則會(huì)在時(shí)間之后再次追上我們把這個(gè)原理運(yùn)用到求循環(huán)節(jié)的問題中來追趕法Function：f(x)return (a*x+b)%Nx=y=Crepeatx=f(f(x)y=f(y)Until (x=y)循環(huán)出來之后所找到的點(diǎn)一定是圈上的點(diǎn)（為什么？）追趕法的時(shí)間復(fù)雜度是O(L)第四部分 圖論問題AIRLINE COMPANY有一個(gè)n個(gè)節(jié)點(diǎn)的連通無向圖，有m條邊?，F(xiàn)在需要你給這m條邊編號(hào)1-m。滿足對(duì)于同一個(gè)點(diǎn)，它的所有連邊的標(biāo)號(hào)的最大公約數(shù)為1。請(qǐng)你找出這樣任意一組滿足要求的解。問題

14、：一定有解嗎？如果不連通，一定有解碼？歐拉路問題歐拉路：遍歷每一條邊一次且僅一次的路歐拉回路問題：如何判斷一個(gè)圖存在歐拉路？歐拉回路？如何求一個(gè)圖的歐拉路？哈密頓路問題哈密頓路：經(jīng)過每個(gè)節(jié)點(diǎn)一次且僅一次的路徑。帶權(quán)哈密頓路：兩個(gè)節(jié)點(diǎn)之間的邊有權(quán)值。路徑上各條邊的權(quán)值和為該路徑的總權(quán)值。最優(yōu)哈密頓路：總權(quán)值最小的哈密頓路。哈密頓路問題(2)求最優(yōu)哈密頓路目前還未找到多項(xiàng)式復(fù)雜度的算法。如果采用盲目搜索，枚舉所有的路徑，理論時(shí)間復(fù)雜度是O(n!)對(duì)于n比較小的情況，我們可以嘗試動(dòng)態(tài)規(guī)劃。哈密頓路問題(3)用一個(gè)集合z表示當(dāng)前路徑訪問過的點(diǎn)集合。設(shè)f(Z,i)表示經(jīng)過點(diǎn)集Z，最后一個(gè)到達(dá)節(jié)點(diǎn)i的最優(yōu)

15、哈密頓路的總權(quán)值（i屬于Z)。f(Z,i)=minf(Z,j)+w(j,i)其中Z=Z-j我們可以用二進(jìn)制數(shù)實(shí)現(xiàn)Z集合。算法的時(shí)間復(fù)雜度為O(2nn2)第五部分 其他JOSEPHUS問題編號(hào)為1到N的N個(gè)人圍成一圈，從第一個(gè)人開始，1、2報(bào)數(shù)，報(bào)2的人出圈，直至圈中只剩下一個(gè)人。求最后剩下的人的編號(hào)。例如N=5時(shí)，出圈的順序是2，4，1，5，最后剩下的人是3。一般約瑟夫問題的解法：線性表模擬。時(shí)間復(fù)雜度O(nm)本題的特殊性：m=2第一圈報(bào)完數(shù)后，編號(hào)為偶數(shù)的人就全部出圈了。此時(shí)圈中剩下n/2個(gè)人。若n是偶數(shù)，此時(shí)又從編號(hào)為1的人開始報(bào)1；若n是奇數(shù)，編號(hào)為1的人出圈，從編號(hào)為3的人開始報(bào)1。第二圈與第一圈有類似性！如何利用？分析1232k+12k452k-1 2k-2當(dāng)n=2k+1時(shí)：在編號(hào)為1的人出圈之后，如果把剩下k個(gè)人的編號(hào)整除2，就轉(zhuǎn)換成了編號(hào)為1到k的k個(gè)人出圈報(bào)數(shù)。1232k2k-1452k-2 2k-3當(dāng)n=2k時(shí)：如果把剩下k個(gè)人的編號(hào)加1再整除2，就轉(zhuǎn)換成了編號(hào)為1到k的k個(gè)人出圈報(bào)數(shù)。分析分析設(shè)f(i)表示編號(hào)為1到i的i個(gè)人圍成一圈報(bào)數(shù)，最后剩下的人的編號(hào)。f(1)=1f(2k)=2*f(k)-1f(2k+1)=2*f(k)+1所求答案：f(n)擴(kuò)展尋找最小的K