ACM基礎(chǔ)算法入門(mén)

1、ACM基礎(chǔ)算法入門(mén).基礎(chǔ)動(dòng)態(tài)規(guī)劃.基礎(chǔ)的“窮竭搜索”.貪心的三種區(qū)間問(wèn)題.數(shù)論那些事.二分的另類法 引言n算法簡(jiǎn)單但思想及其重要n介紹的算法都堪稱為經(jīng)典中的經(jīng)典基礎(chǔ)動(dòng)態(tài)規(guī)劃n多階段決策過(guò)程最優(yōu)化的數(shù)學(xué)方法三要素：-階段-決策-狀態(tài)動(dòng)態(tài)規(guī)劃的適用范圍n最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）當(dāng)前狀態(tài)依賴于前面的狀態(tài)得到，是前面狀態(tài)的完美總結(jié)n無(wú)后效性（不成環(huán)）經(jīng)典模型n數(shù)塔模型n背包問(wèn)題n區(qū)間最大和模型n最長(zhǎng)非降子序列模型n最長(zhǎng)公共子序列n數(shù)字歸并（區(qū)間dp）n旅行商問(wèn)題（狀態(tài)壓縮）n求解從頂?shù)较陆?jīng)過(guò)節(jié)點(diǎn)的最大值是多少解題思路n列狀態(tài) v I j 表示走到第i層的第j個(gè)節(jié)點(diǎn)的最大值n分階段 每一個(gè)層就是一個(gè)階段

2、n狀態(tài)轉(zhuǎn)移方程（決策）V i-1 j += V I j v I j + 1 ? V I j : v I j + 1 ;單調(diào)遞增非降子序列n給定一整型數(shù)列a1,a2.,an（0n=100000），找出單調(diào)遞增最長(zhǎng)子序列，并求出其長(zhǎng)度。n如：1 9 10 5 11 2 13的最長(zhǎng)單調(diào)遞增子序列是1 9 10 11 13，長(zhǎng)度為5。解題思路n定義狀態(tài)dp【i】以i為結(jié)束節(jié)點(diǎn)最長(zhǎng)單調(diào)子序列長(zhǎng)度n階段每一個(gè)點(diǎn)選擇過(guò)程即階段轉(zhuǎn)移方程：Dp【i】= max（dp【1（i-1）】） + 1想想有沒(méi)有更好的方法？dp總結(jié)n模型匹配法n三要素法 先確定階段（數(shù)塔問(wèn)題）先確定狀態(tài)（一般題目都是）先確定決策（背包問(wèn)題

3、）貪心的三種區(qū)間問(wèn)題n選擇不相交區(qū)間n區(qū)間選點(diǎn)n區(qū)間覆蓋選擇不相交區(qū)間n 數(shù)軸上有數(shù)軸上有n個(gè)開(kāi)區(qū)間（個(gè)開(kāi)區(qū)間（ai,bi），選擇盡量多個(gè)區(qū)間，），選擇盡量多個(gè)區(qū)間，n使得這些區(qū)間兩兩沒(méi)有公共點(diǎn)。使得這些區(qū)間兩兩沒(méi)有公共點(diǎn)?！痉治觥?首先明確一個(gè)問(wèn)題：假設(shè)有兩個(gè)區(qū)間x,y,區(qū)間x完全包含y。那么，選x是不劃算的，因?yàn)閤和y最多只能選一個(gè)，選x不如選y，這樣不僅區(qū)間數(shù)目不會(huì)減少，而且給其他區(qū)間留出了更多的位置。接下來(lái)，按照bi從小到大的順序?qū)λ袇^(qū)間排序。會(huì)場(chǎng)安排問(wèn)題n 先對(duì)n個(gè)區(qū)間按照bi從小到大的順序排序，如果nbi相同，則ai按照從大到小的順序排序。然后從前往后n掃描每個(gè)區(qū)間，找出所有的符

4、合條件的區(qū)間。n 注意：排序后第一個(gè)區(qū)間一定會(huì)選，因?yàn)樗淖⒁猓号判蚝蟮谝粋€(gè)區(qū)間一定會(huì)選，因?yàn)樗腷i最小，最小，n它不影響后面區(qū)間的選取，而且如果不選此區(qū)間，最它不影響后面區(qū)間的選取，而且如果不選此區(qū)間，最終終n求出的區(qū)間數(shù)目會(huì)變少。求出的區(qū)間數(shù)目會(huì)變少。區(qū)間選點(diǎn)問(wèn)題n 數(shù)軸上有數(shù)軸上有n個(gè)閉區(qū)間個(gè)閉區(qū)間ai, bi。取盡量少的點(diǎn)，使得每個(gè)。取盡量少的點(diǎn)，使得每個(gè)n區(qū)間內(nèi)都至少有一個(gè)點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）。區(qū)間內(nèi)都至少有一個(gè)點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）?！痉治觥?如果區(qū)間i內(nèi)已經(jīng)有一個(gè)點(diǎn)被取到，我們稱此區(qū)間已經(jīng)被滿足。受上一題的啟發(fā)，我們先討論區(qū)間包含的情況。由于小區(qū)間被滿

5、足時(shí)大區(qū)間一定也被滿足。所以在區(qū)間包含的情況下，大區(qū)間不需要考慮。 因此，我們把所有區(qū)間按b從小到大排序（b相同時(shí)a從大到小排序），則如果出現(xiàn)區(qū)間包含的情況，小區(qū)間一定排在前面。第一個(gè)區(qū)間應(yīng)該選取哪一個(gè)點(diǎn)呢？正確的貪心策略是：取最后一個(gè)點(diǎn)。如下圖。解題思路n根據(jù)剛才的討論，所有需要考慮的區(qū)間的a也是遞增的，n我們把它畫(huà)成上圖的形式。如果第一個(gè)區(qū)間不選最后一個(gè)點(diǎn)，n而是去中間的，如灰色點(diǎn)，那么把它移動(dòng)到最后一個(gè)點(diǎn)后，n被滿足的區(qū)間增加了，而且原先被滿足的區(qū)間現(xiàn)在一定被滿n足。這樣才能保證選取的點(diǎn)最少。區(qū)間覆蓋問(wèn)題n 數(shù)軸上有數(shù)軸上有n個(gè)閉區(qū)間個(gè)閉區(qū)間ai, bi，選擇盡量少的區(qū)間覆蓋，選擇盡量少

6、的區(qū)間覆蓋n一條指定線段一條指定線段s, t。【分析】 本題的突破口仍然是區(qū)間包含和排序掃描，不過(guò)要先進(jìn)行一次預(yù)處理。每個(gè)區(qū)間在s,t外的部分都應(yīng)該預(yù)先被切掉，因?yàn)樗鼈兊拇嬖谑呛翢o(wú)意義的。例如要覆蓋線段3,5，閉區(qū)間0,1的存在無(wú)意義。在預(yù)處理后，在相互包含的情況下，小區(qū)間顯然不應(yīng)該被考慮。解題思路n 把各區(qū)間按照a從小到大順序。如果區(qū)間1的起點(diǎn)不是s，n則無(wú)解，即s,t無(wú)法被完全覆蓋（因?yàn)槠渌麉^(qū)間的起點(diǎn)更大，n不可能覆蓋到s點(diǎn)），否則選擇起點(diǎn)在s的最長(zhǎng)區(qū)間。選擇此n區(qū)間ai,bi后，新的起點(diǎn)應(yīng)該被設(shè)置為bi,并且忽略所有區(qū)間在nbi之前的部分，就像預(yù)處理一樣。雖然貪心策略比上面的題n復(fù)雜，但

7、是仍然只需要一次掃描。如下圖5所示。s為當(dāng)前有n效起點(diǎn)（此前部分已被覆蓋），則應(yīng)該選擇區(qū)間2。s窮竭搜索是指將所有的可能性羅列出來(lái)，在其中尋找答案的方法。概念：這里，我們主要介紹：深度優(yōu)先搜索寬度優(yōu)先搜索基礎(chǔ)的“窮竭搜索”深度優(yōu)先搜索n深度優(yōu)先搜索（DFS，Depth-First Search）是搜索的手段之一。n它從某個(gè)狀態(tài)開(kāi)始，不斷地轉(zhuǎn)移狀態(tài)直到無(wú)法轉(zhuǎn)移，然后回退到前一步的狀態(tài)，繼續(xù)轉(zhuǎn)移到其他狀態(tài)，如此不斷重復(fù)，直至找到最終的解。n根據(jù)深度優(yōu)先搜索的特點(diǎn)，采用遞歸函數(shù)實(shí)現(xiàn)比較簡(jiǎn)單。 例題n給定整數(shù) a1,a2,a3,.,an, 判斷是否可以從中選出若干個(gè)數(shù)，使他們的和恰好為k。n限制條件：

8、n1=n20n-108=ai=108n-108=k只需1次轉(zhuǎn)移就可到達(dá)的所有狀態(tài)-只需2次轉(zhuǎn)移就可到達(dá)的狀態(tài)-.，這樣的順序進(jìn)行搜索。對(duì)于同一狀態(tài)，寬度優(yōu)先搜索只經(jīng)過(guò)一次，因此復(fù)雜度為O（狀態(tài)數(shù)*轉(zhuǎn)移的方式）。n根據(jù)寬度優(yōu)先搜索的特點(diǎn)，采用隊(duì)列進(jìn)行實(shí)現(xiàn)。例題：n水池?cái)?shù)目n南陽(yáng)理工學(xué)院校園里有一些小河和一些湖泊，現(xiàn)在，我們把它們通一看成水池，假設(shè)有一張我們學(xué)校的某處的地圖，這個(gè)地圖上僅標(biāo)識(shí)了此處是否是水池，現(xiàn)在，你的任務(wù)來(lái)了，請(qǐng)用計(jì)算機(jī)算出該地圖中共有幾個(gè)水池。n輸入m行每行輸入n個(gè)數(shù)，表示此處有水還是沒(méi)水n（1表示此處是水池，0表示此處是地面） n0m100n0n100n輸入：n3 4n1 0

9、 0 0 n0 0 1 1n1 1 1 0n輸出：n2輸入：5 51 1 1 1 00 0 1 0 10 0 0 0 01 1 1 0 00 0 1 1 1輸出：3解題過(guò)程n本題是簡(jiǎn)單的搜索問(wèn)題，采用深度優(yōu)先遍歷可以解決，根據(jù)題目要求，假設(shè)從任意一點(diǎn)值為1的出發(fā)，將這點(diǎn)的坐標(biāo)上下左右全部用0替換，1次DFS后與初始動(dòng)這個(gè)1連接的1全部被替換成0，因此，直到圖中不再存在1為至，總共進(jìn)行的DFS的次數(shù)就是最后的結(jié)果咯！那么，根據(jù)題目要求，有4個(gè)方向，時(shí)間復(fù)雜度為O(4*n*m)。數(shù)論那些事n數(shù)學(xué)，特別是數(shù)論與計(jì)算機(jī)科學(xué)有著密切的聯(lián)系，所以也常被選作題材。雖然數(shù)學(xué)問(wèn)題大多需要使用特定方法求解，但其中

10、有幾個(gè)基礎(chǔ)算法扮演著重要的角色。數(shù)論基礎(chǔ)n輾轉(zhuǎn)相除法n有關(guān)素?cái)?shù)的基礎(chǔ)算法n快速冪1、求最大公約數(shù)2、擴(kuò)展歐幾里得3、ax+by=gcd(a,b)1、埃氏篩法2、區(qū)間篩法輾轉(zhuǎn)相除法n擴(kuò)展歐幾里得n 雙六n一個(gè)雙六上面有向前向后無(wú)限延續(xù)的格子，每個(gè)格子都寫(xiě)有整數(shù)。其中0號(hào)格子是起點(diǎn)，1號(hào)格子是終點(diǎn)。而骰子上只有 a , b , -a , -b 四個(gè)整數(shù)，所以根據(jù) a 和 b 的值的不同，有可能無(wú)法到達(dá)終點(diǎn)。n格子如下：n -4 -3 -2 -1 0 1 2 3 4 n擲出四個(gè)整數(shù)各多少次可以到達(dá)終點(diǎn)？輸出任意一組解。n1= a , b b。n1，顯然當(dāng) b=0，gcd（a，b）=a。此時(shí) x=1，

11、y=0；n2，ab!=0 時(shí)n設(shè) ax1+by1=gcd(a,b);nbx2+(a mod b)y2=gcd(b,a mod b);n根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);n則:ax1+by1=bx2+(a mod b)y2;n即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;n根據(jù)恒等定理得：x1=y2; y1=x2-(a/b)*y2;n這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.n上面的思想是以遞歸定義的，因?yàn)?gcd 不斷的遞歸求解一定會(huì)有個(gè)時(shí)候 b=0，所以遞歸可以結(jié)束。埃氏篩

12、法n給定整數(shù)n，請(qǐng)問(wèn)n以內(nèi)多少個(gè)素?cái)?shù)nn=106n輸入n25n輸出n9解題思路n要枚舉n以內(nèi)素?cái)?shù)，可以用埃氏篩法n列出2以后的所有序列：n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25n標(biāo)出序列中的第一個(gè)素?cái)?shù)，也就是2，序列變成：n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 252n將剩下序列中，劃摽2的倍數(shù)，序列變成：n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2

13、4 25n 4 6 8 10 12 14 16 18 20 22 24 （劃出的數(shù)）n如果現(xiàn)在這個(gè)序列中最大數(shù)小于最后一個(gè)標(biāo)出的素?cái)?shù)的平方，那么剩下的序列中所有的數(shù)都是素?cái)?shù)，否則回到第二步。n本例中，因?yàn)?5大于2的平方，我們返回第二步：n剩下的序列中第一個(gè)素?cái)?shù)是3，將主序列中3的倍數(shù)劃出，主序列變成：n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25n 4 6 8 9 10 12 14 15 16 18 20 21 22 24 （劃出的數(shù)）n我們得到的素?cái)?shù)有：2，3n25仍然大于3的平方，所以我們還要返回第二步：n現(xiàn)在序列中第一個(gè)素?cái)?shù)是5，同樣將序列中5的倍數(shù)劃出，主序列成了：n2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25n 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 （劃出的數(shù)）n我們得到的素?cái)?shù)有：2 3 5 。n因?yàn)?5等于5的平方，跳出循環(huán).n結(jié)論：去掉數(shù)字，2到25之間的素?cái)?shù)是：2 3 5 7 11 13 17 19 23?？偨Y(jié)n算法競(jìng)賽是展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神和在壓力下編寫(xiě)程序、分析和解決問(wèn)題