試題選講課件

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

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

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

4、，求其中的第k小數(shù)。分析可以先排序，然后直接確定第k小數(shù)。至少需要O(nlogn)的時間復(fù)雜度。其實我們沒有必要知道所有的有序信息。設(shè)一個pivot，若n個數(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的選擇隨機在pivot隨機的情況下，該算法的期望是線性的。如何理解？有沒有最壞情況下是線性的算法？第二部分 字符串算法 最長

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

6、的數(shù)據(jù)結(jié)構(gòu)解決后綴數(shù)組后綴樹運用它們可以得到O(nlogn)甚至O(n)的算法第三部分 數(shù)學問題SPECIAL SUBSET給定集合M=1，2，n，取出M的所有不包含相鄰自然數(shù)的子集合例如1,3就是一個符合要求的而1,3,4就不是對于每一個這樣的子集合Si，求它的元素之積Ti。例如對于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當問題的規(guī)模為N時第一種情況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時的平方和Fi=i*i +Fi-2*i*i +Fi-1O(n)的遞推算法CALLING EXTRATERRESTRIAL INTELLIGENCE AGAIN 給定三個整數(shù)m,a,b，求兩個正整數(shù)p, q滿足：p和q都是素數(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ù)。基本思路枚舉較小的素數(shù)p，這樣q是滿足下面兩個情況下的最大的素數(shù)：q=m/pq=p*b/a我們需要解決兩個子問題：找出素數(shù)找出素數(shù)序列中滿足要求的最大數(shù)素數(shù)(PRIME)大于1的正整數(shù)p被稱作素數(shù)，如果p僅有的正因子是1和p素數(shù)判定理論：如果n是合數(shù)，則他必有一個小于或等于sqrt(n)的約數(shù)。操作：枚舉2至sqrt(n)的所有整數(shù)，判斷其中有無p的約數(shù)。時間復(fù)雜度：O(sqrt(n)ERAOSTHENES篩法（篩選法）問題：如何求2-n中所有的素數(shù)？篩選法：建立一個表，給每個值標記true從2到n枚舉每一個整數(shù)p，如果當前p的標記為true，則p為

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

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

11、科學、工程技術(shù)、社會科學等領(lǐng)域中有著廣泛的應(yīng)用矩陣定義由mn個數(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個A相乘只有方陣的冪才有意義AkAl = Ak+l, (Ak)l = Akl矩陣的冪跟數(shù)的冪性質(zhì)很相似聯(lián)想：如何求(A)k回到原問題直接計算A*B，然后再與C進行逐一元素的比對，這樣的時間復(fù)雜度是O(n3)聯(lián)想到素數(shù)判定的偽素數(shù)測試（必要條

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

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

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

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