1、201 7- 201 8NOI P實用算法51.模擬方a.用數(shù)學量和圖形描述問b.模擬計算過c.模擬時的優(yōu)d.高精度計算算匚中玉計算機學會20172.排序算法與算法時空復雜a.簡單排序算b. 快速排序、堆排c.算法時空復雜d. 時空的簡單優(yōu)化方e.線性時間排f. 歸并排9g.合理選用排序算3. 搜10a.復雜的模擬問題與利用相似10b. 函數(shù)的遞歸調(diào)10c.棧與深度優(yōu)先搜11d. 深度優(yōu)先搜索的優(yōu)12e.隊列與廣度優(yōu)先搜12f. 廣度優(yōu)先搜索的優(yōu)12134. 貪心方14a .工程計劃模14b. 部分背包與每步最14c. 構(gòu)造貪心算15155.動態(tài)規(guī)16a.另一種形式的工程計16b. 記憶化搜1

2、6c .數(shù)字三角形：遞推地思考問17d. 石子合并：狀態(tài)的確17e. 街道問題：狀態(tài)量維數(shù)的確定與無后效18f. 0-1 背包：巧妙地選取狀態(tài)19g. Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方20h. 最長非降子序列模20i. 構(gòu)造動態(tài)規(guī)劃算21j. 動態(tài)規(guī)劃、遞推、廣度優(yōu)先搜索的區(qū)別與轉(zhuǎn)21216.常用數(shù)學方.222a.排列組.22b. 遞推與通項的選237. 分26a .子問題與母問題的相似26b. 二分查.26c. 分析算.26d.最長非降子序列的二分298. 圖論思30a. 圖論基.30b. 圖的表示方30c .經(jīng)典圖論算30d. 構(gòu)造圖論模3233附件：關(guān)鍵路徑算法、篝火晚會問題解法源

3、文331. 模擬方法a. 用數(shù)學量和圖形描述問題 計算機處理的是數(shù)學量。若要用計算機解決實際問題，需要把實際問題抽象為數(shù)學 量，或者數(shù)字。比如， 記事本把文字按 ASCII 碼表轉(zhuǎn)換為數(shù)字儲存起來，極品飛車把賽車的性能表示為數(shù) 字，來權(quán)衡賽車的 好壞。一個漂亮的算法，需要用數(shù)學量表示出來。任務(wù)：現(xiàn)有兩個軟件工程的制作任務(wù)，你的團隊可以接手其中任意一個?，F(xiàn)要在兩 個中選擇一個，需要 考慮制作成本，制作成功的可能性，可獲得經(jīng)濟收益的多少，對你的團隊知名度的 影響等等因素。你 如何量化地分析和解決這個問題？ 提示：需要把每一項都轉(zhuǎn)化為數(shù)值，必要時加入權(quán)值、計算期望。如果只考慮以上 四個因素，可以得到

4、 以下數(shù)學式 綜合收益=制作成功的概率 *（可獲得經(jīng)濟收益 -制作成本）*經(jīng)濟效益的權(quán)值 +團隊知名度的影響 * 社會 效益的權(quán)值 其中概率和兩個權(quán)值是需要估計的值。有時，我們需要用更直觀的圖形來描述實際問題。圖論就是一個絕佳的方法。圖是一種表示離散量間關(guān)系的形式，它也是一種思想， 常被用于建模。同時， 前人也為我們提供了很多現(xiàn)成的圖論算法，能夠解決很多常見問題，這些將在之后 被提到。矩陣也是一種常見的方法。有時矩陣被表示成三角形的形式，比如 矩陣常常和數(shù)學有關(guān)， 在計算機計算時常常利用矩陣的遞推式。這也將在后面被提到。b. 模擬計算過程 模擬方法是最常見、最直接的算法構(gòu)建方法。楊輝三角”gc

5、d(a,b) )任務(wù)：編程實現(xiàn)歐幾里得算法(輾轉(zhuǎn)相除法，求兩個數(shù)的最大公約數(shù) 提示： 歐幾里得算法原理： gcd(a,b)=gcd(b,amodb)歐幾里得算法的圖形描述|16863|16863|2 |42|1. 寫下兩個數(shù) 2. 將兩數(shù)相除，余數(shù)寫在較大的數(shù)下面1|4221|1|4221|2整除|16863|2|16863|23.將每列最下面的數(shù)相除，余數(shù)寫在被除數(shù)下面 4.重復步驟 3直至整除，此時最后寫下的余數(shù)即為 開始時兩數(shù)的最大公約數(shù) 這是一個簡單的模擬算法，實際過程中，量間的關(guān)系往往比這復雜得多，因而，模 擬算法可以是很復雜 的。有些模擬算法還涉及到圖形和其他復雜的數(shù)據(jù)結(jié)構(gòu)，這需要

6、我們熟練地運用語言， 巧妙地把其他關(guān)系轉(zhuǎn) 化為數(shù)學量間關(guān)系。c. 模擬時的優(yōu)化 如果處理不當，模擬方法寫出的程序會非常長。這要求我們在模擬是將相似的步驟 合為一體，適時利用 函數(shù)簡化程序。/* 實現(xiàn)時，若將左邊一列數(shù)最下面的記為以上面的歐幾里得算法為例：L1000 、右邊一列數(shù)記為 R1000 ，顯然是不明智的，為只有每列最后一個數(shù)會在以后的計算中用到*/* 實現(xiàn)方法一：及每一列最后一個數(shù)分別為L、R。輸入即可是L、R,返回gcd(L,R)*/intEuclid_1(intL,intR) for(;)L=L%R;if(L=0)returnR;R=R%L;if(R=0)returnL;/* 我們

7、發(fā)現(xiàn)有兩步是相似的。因而我們可以把它簡化為實現(xiàn)方法二 */ intEuclid_2(intL,intR)intt;for(;) t=R;R=L%R;L=t;if(R=0)returnL;/* 甚至我們可以寫成遞歸形式。以下是實現(xiàn)方法三 */ intEuclid_3(intL,intR) if(L%R=0)returnR;elsereturnEuclid_3(R,L%R);這個實例主要體現(xiàn)模擬算法的簡化過程。雖然在這樣小的程序段中，這樣的簡化作 用不大，但遇到復雜 的模擬問題，這種利用相似性的簡化便非常有用了。應(yīng)當重視這樣的代碼優(yōu)化。d. 高精度計算算法 競賽中經(jīng)常會用上一些很大的數(shù)，超出長整型

8、的數(shù)值范圍。這時我們需要使用高精 度計算算法。這種算 法可以把數(shù)值范圍增加到我們想要的程度。高精度函數(shù)往往包括加、減、乘、輸入、輸出五種。實現(xiàn)高精度計算時，常常使用模擬算法模擬小學豎式運算。我們把一個高精度數(shù)表示為一個數(shù)組 H ，數(shù)組中的某一個數(shù)相當于高精度數(shù)的某一位。要注意的是，輸出時往往要求以十進制形式輸出。因而，高精度數(shù)每一位都應(yīng)便于 直接輸出。這樣，每一位上的最大數(shù)都應(yīng)是10八n-1。簡單地說，若把H定為unsigned型，高精度數(shù) 每一位上最大數(shù) 最好為 9999 。這樣既能盡量利用儲存空間，又便于輸出。另外，高精度數(shù)有時會用到負數(shù)。在補碼的體系中，仍然可以按正數(shù)的方法處理負 數(shù)，但

9、是要特別注意 輸出時的問題，和對溢出的防止。任務(wù)：實現(xiàn)高精度運算加法，從末提示：設(shè)計函數(shù)unsigned*HAdd(unsignedN1,unsignedN2,unsignedAns)位起相加，注意是否進位。顯然，減法作為加法的逆運算，也很容易實現(xiàn)。另一種聰明的辦法是，對減數(shù)每一 位取補碼，在做加法5即可。請讀者自行實現(xiàn)高精度減法。高精度乘法困難一些。我推薦的方法是，先考慮多位高精度數(shù)乘一位高精度數(shù)的過 程。多位高精度數(shù)乘 多位高精度數(shù)可以轉(zhuǎn)化為多位高精度數(shù)乘另一高精度數(shù)每一位，再將結(jié)果相加的過 程。下面給出多位 高精度數(shù)乘一位高精度數(shù)的源代碼：/*N1 為多位高精#defineH_Bit25

10、6/* 定義常數(shù)：高精度數(shù)位數(shù) */ unsigned*HTimesInt(unsignedN1,intN2,unsignedAns)度數(shù)，N2為高精度數(shù)的一位，An s為另一高精度數(shù)，用于儲存結(jié)果 */ /*這里允許N1與Ans相同*/ unsignedi,up=0;unsignedlongtemp;for(i=H_Bit-1;i<=H_Bit;i-) temp=N1i*N2+up;up=temp/10000;Ansi=(unsigned)(temp%10000);returnAns;/* 函數(shù)返回作為答案的高精度數(shù)首地址，這樣更便于高精度運算函數(shù)的使用，例如連乘可以寫成HTi

11、mesInt(HTimesInt(N1,N2,Ans),N3,Ans)*/高精度數(shù)的輸入輸出需要專門的函數(shù)。針對不同語言的不同特點，可以比較容易地 寫出這兩個函數(shù)。但 要注意輸出非首位數(shù)位上的 “0” 。習題模擬方法的習題6感謝深藍評測系統(tǒng)提供習題2. 排序算法與算法時空復雜度a. 簡單排序算法簡單排序算法包括冒泡排序、插入排序、選擇排序。這三種算法容易理解、編寫方 便，適用于數(shù)據(jù)規(guī)模 較小的情形。冒泡排序( BubbleSort )的基本思路是：(以從小到大排序為例)從前到后逐個比 較相鄰兩數(shù)，若前 數(shù)大于后數(shù)，就將兩數(shù)交換。不斷重復這一過程，直至全部數(shù)字已按從小到大排好?？紤]到實用性的問題

12、，插入排序和選擇排序這里不再介紹。對于NOIP提高組而言，這些算法時間復雜度過高，很難應(yīng)付較大的數(shù)據(jù)規(guī)模。建議 盡量不要采用簡單 排序算法，除非你十分確信數(shù)據(jù)規(guī)模在可承受范圍之內(nèi)。b. 快速排序、堆排序 快速排序和堆排序是比簡單排序快的排序算法，在競賽中常常被采用。這里，我們 介紹快速排序算法。堆排序的實現(xiàn)不作介紹，若想了解，可咨詢谷歌或百度?？焖倥判? QuickSort )基于分治思想。它的基本思路是：(以從小到大排序為例) 取一個數(shù)作為標 記元素，將比它大的數(shù)放在它右側(cè)，比它小的數(shù)放在它左側(cè)，再通過遞歸的方法， 將左側(cè)的數(shù)用以上 的方法排好，右側(cè)的數(shù)也用以上的方法排好即可。面這個視頻能很

13、直觀地比較冒泡排序 (BubbleSort )和快速排序 (QuickSort )： 在數(shù)據(jù)規(guī)模很大時，平均情況下快排比冒泡快很多。 在處理NOIP提高組含排序的問 題時，一般要選擇 快速排序或堆排序。面將介紹快速排序的實現(xiàn)(以從小到大排序為例)?？炫胚\用分治思想，因而要用函數(shù)的遞歸調(diào)用來實現(xiàn)：voidQuickSort(inta,intst,intstp)/ 這里也可以定義成 voidQuickSort（int*st,intlen)。為了便于理解，我使用前一種寫法。intmid;mid=partition(a,st,stp);/partition()用于確定標記元素的位置。if(l<m

14、id-1)QuickSort(a,st,mid-1);if(mid+1<r)QuickSort(a,mid+1,stp);現(xiàn)在的關(guān)鍵問題在于如何寫 partition（）寫法一：對于數(shù)列 567538162 1.取首個元素做標記元素，取出它，令指針 p 指向最右邊的數(shù)的右邊67538162p-5；否5；否2.將p向左移動到小于標記元素的數(shù)（或空缺處）為止。若指向空缺，貝y跳到貝將該數(shù)和 p 移到 空缺處 p-26753816_3. 將P向右移動到大于標記元素的數(shù)（或空缺處）為止。若指向空缺，貝y跳到貝將該數(shù)和 p 移到 空缺處 2_753816p-64. 重復 2和3。2p-17538_

15、66 21_538p-766721p-35_87665.把標記元素放入空格處2135p-58766寫法二：寫法二比寫法一短一些，但理論上講，寫法二要慢一些（因為所作賦值運 算多一些）。下面給出源代碼與分析：voidQuickSort(longa,longst,longstp)/ 這里將 partition()結(jié)合進QuickSort()中l(wèi)ongt,n,l,r;n=ast;l=st+1;r=stp;/ 從右找，找到一個小于標記元素的數(shù)for(;)for(;al<=n&&l<=stp;l+);for(;ar>=n&&r>st;r-);/ 從

16、左找，找到一個大于標記元素的數(shù)if(l>=r) break ;/ 如果 l在 r 右側(cè)，則跳出t=al;al=ar;ar=t;/ 交換，使小于標記元素的在左，大于標記元素的在右ast=ar; / 取出最右側(cè)的小于標記元素的數(shù)寫入空缺ar=n; / 空缺處放入標記元素if(r-st>1)QuickSort(a,st,r-1);if(stp>l)QuickSort(a,l,stp);以上快排實現(xiàn)方法的最差情形是排列整齊的情況，這時它的運行效率會很低。為了 解決排列整齊的情形， 我們可以使用隨機快速排序法，即隨機選取一個數(shù)作為標記元素（實現(xiàn)時，將其與 第一個數(shù)交換即可）。c. 算法

17、時空復雜度 為了描述一個算法的優(yōu)劣，我們引入算法時間復雜度和空間復雜度的概念。時間復雜度：一個算法主要運算的次數(shù)，用 O（） 表示。通常表示時間復雜度時，我們只保留影響最大的項，并忽略該項的系數(shù)。例如主要運算為賦值的算法，賦值做了 3n八3+n八2+8次，則認為它的復雜度為0（n八3）;若主要運算為比較，比較做了 4*2八n+2*n八4+700次，由于數(shù)據(jù)很大時，指數(shù)級增長的25影響 最大，我們認為它 的時間復雜度為0（2八n）。常見的時間復雜度有下列幾個：0（n） 貪心算法多數(shù)情況下為此時間復雜度0（nlbn）有時帶有分治思想的算法的時間復雜度（注Ibn表示以2為底的n的對數(shù)）0（n 八2）

18、有時動態(tài)規(guī)劃的時間復雜度0（n 八3）有時動態(tài)規(guī)劃的時間復雜度0（2八 n）有時搜索算法的時間復雜度0（n!） 有時搜索算法的時間復雜度 有時時間復雜度中含有兩個或多個字母，比如遍歷一個 m*n 的矩陣，時間復雜度為0（m*n） 。要注意的是，時間復雜度相同的兩個算法，它的實際執(zhí)行時間可能會有數(shù)倍的差距， 因而實現(xiàn)時要特別 注意細節(jié)處的優(yōu)化。8N0IP提高組執(zhí)行時限常常為1s。一般認為，將數(shù)據(jù)規(guī)模代入到時間復雜度，若所得值小于或接近于1000000 ，就是絕對安全的、不超時的。例如，0(n八2)的動態(tài)規(guī)劃算法，可承受的數(shù)據(jù)規(guī)模是 nW 1000 ; 0(2八n)的搜索算法，可承受的數(shù)據(jù)規(guī) 模是

19、nW20 ; 0(n!)的搜索算法，可承受的數(shù)據(jù)規(guī)模是nW9。實際上，以現(xiàn)在的 CPU 運行速度， 5000000 也應(yīng)該不成問題?？臻g復雜度：一個算法消耗儲存空間(內(nèi)存)的大小，用 0()表示。空間復雜度的表示規(guī)則與時間復雜度類似。在實際應(yīng)用時，空間的占用是需要特別注意的問題。太大的數(shù)組經(jīng)常是開不出來的， 即使開出來了，遍 歷的時間消耗也是驚人的。面我們簡單地分析一下簡單排序算法、快速排序、堆排序的時空復雜度。這三種算法都是基于比較的排序算法，以比較次數(shù)作為主要運算。簡單排序算法最差時需做n“2次比較，平均情況下時間復雜度通常被認為是0(n 八2)?？焖倥判蜃畈顣r需做n八2次比較，可以證明平

20、均情況下需做nlbn次比較，時間復雜 度是 0(nibn)。堆排序時間復雜度是 0(nibn) ?？臻g上，三者都不需要額外開辟暫存數(shù)組，快排遞歸調(diào)用時需要使用稍多一些的儲 存空間。綜合來看，快速排序、堆排序優(yōu)于簡單排序算法。另外，可以證明基于比較的排序算法時間復雜度下界為 O（nlbn） 。d. 時空的簡單優(yōu)化方法 時間上的優(yōu)化在于少做運算、做耗時短的運算等。有幾個規(guī)律需要注意： 整型運算耗時遠低于實型運算耗時。+ 、 - 運算非?？欤p法是將減數(shù)取補碼后與被減數(shù)相加，其中位運算更快一些，但 是減法也比加法稍 慢些。）*運算比加法慢得多 / 運算比乘法慢得多 比較運算慢于四則運算賦值運算慢于比

21、較運算（因為要寫內(nèi)存）這些規(guī)律我們可以從宏觀上把握。事實上，究竟做了幾步運算、幾次賦值、變量在內(nèi)存還是緩存等多數(shù)由編譯器、系統(tǒng)決定。但是，少做運算（尤其在循環(huán)體、遞歸體中）一定能很大程度節(jié)省時間。面來舉一個例子：計算組合數(shù)C(m,n)n件物品取出m件的組合數(shù)。C(m,n) 可用公式直接計算。 C(m,n)=n!/(n-m)!m!)C(m,n)=n(n-1)(n-2)(nm+1)/(n-m)!。顯然，有時所作的乘法少很多，會快一些?？墒沁@樣算真的最快嗎？另一條思路是 C(m,n)=C(m,n-1)+C(m-1,n-1)，遞推下去，直到可利用C(1,k)=k=C(k-1,k) 為止。我覺得這種只用

22、加法的運算會快些，盡管加法多一些。(我沒試驗過，你可以去試一下。)空間上的優(yōu)化主要在于減小數(shù)組大小、降低數(shù)組維數(shù)等。常用的節(jié)省內(nèi)存的方法有：壓縮儲存 例：數(shù)組中每個數(shù)都只有 0、1兩種可能，則可以按位儲存，空間壓縮為原來的八分之一。覆蓋舊數(shù)據(jù) 例：矩陣中每一行的值只與上一行有關(guān)，輸出只和最末行有關(guān)，則可將奇數(shù)行儲存在第一行，偶數(shù)行儲存在第二行，降低空間復雜度。要注意的是，對空間的優(yōu)化即使不改變復雜度、只是改變n的系數(shù)也是極有意義的?？臻g復雜度有時對時間也有影響，要想方設(shè)法進行優(yōu)化。e. 線性時間排序基于比較的排序算法時間復雜度下界為 O(nlbn) 。因而，若還要降低復雜度，要放棄基于比較的排

23、序9算法。有一類排序算法叫做線性時間排序，它們的時間復雜度為O(n) 。下面介紹一種。計數(shù)排序思路：開辟暫存數(shù)組b , bk表示欲排序數(shù)組a中k出現(xiàn)的次數(shù)(需要遍歷 a )，最后遍歷b，可將a排好。這種想法非常簡單，實現(xiàn)也很容易。事實證明，在 a 取值范圍很小（如整型范圍） 時，它是很高效的 排序算法，比快排快不少?？墒?a 取值范圍較大（如長整型范圍）時，它的執(zhí)行時 間會變長，而且 數(shù)組 b 有時開不出來。實際上計數(shù)排序時間復雜度為 O（n+m） ，空間復雜度也為 O（n+m） ，m 表示 a 取值 范圍。若 m 很大， 則也不能在時限內(nèi)執(zhí)行完。f. 歸并排序 有一種排序時極為常見的情形：有

24、一張成績表，記錄著許多學生的成績，要將他們 按成績排序，但成績 相同者的相對順序不能改變。換句話說，ABCDE五人，A、C、D成績相同，顯然排序完之后會排在一起，現(xiàn)在的 要求是：他們排在一 起的順序也必須是ACD，不能是ADC、CAD- 這樣的實際問題涉及到排序的穩(wěn)定性。排序的穩(wěn)定性：一個排序算法，若可使排序前后關(guān)鍵字相同的項相對順序不變，則 稱該排序算法是穩(wěn)定 的排序算法。面我們來考察常見排序算法的穩(wěn)定性。在編寫合理的情況下，簡單排序算法是穩(wěn)定的；快速排序、堆排序是不穩(wěn)定的（你 可以好好想想這是為 什么）。在NOIP中，往往排序是沒有附帶其他項目的，也就不要求排序穩(wěn)定?？焖倥判?、堆 排序仍然

25、是最佳選 擇?？墒怯袥]有時間復雜度為 O（nlbn） 的穩(wěn)定的排序算法呢？有的。歸并排序基于分治思想：把要排序的數(shù)組平分兩半，對兩部分分別排序（遞歸地） 后再合并起來。合并 時，將一個數(shù)組按順序插入另一個數(shù)組中，需要開辟一個暫存數(shù)組。利用空間優(yōu)化， 可只用開辟一個 與原數(shù)組等大的數(shù)組。歸并排序的源代碼會放在本章的附件中。請讀者自己研究。歸并排序的優(yōu)缺點都很明顯。 無論情形如何，它的比較次數(shù)、賦值次數(shù)都穩(wěn)定在 nlbn ， 沒有最差情況， 運行時間與快速排序、堆排序相當。而且，它是穩(wěn)定的排序算法。但是，它的內(nèi)存占用回達到快速排序、堆排序的兩倍，競賽時使用容易造成內(nèi)存超 出限制。NOIP初賽曾考察

26、過歸并排序。問題大意是：找出一個算法，使五個數(shù)在n次比較（兩兩比較）后一定 能排定次序，求n的最小值。在快速排序、堆排序的最差情況下，需要 10 次、 9次比較?？墒牵褂脷w并排序只需要7次！記?。簹w并 排序沒有最差情況。g. 合理選用排序算法面是本章講過的排序算法的優(yōu)缺點比較：（這里只講最主要的） 排序算法時間復雜度優(yōu)點缺點簡單排序0(n八2)編寫方便執(zhí)行時間長 快排0(nibn)執(zhí)行時間短很差情況下執(zhí)行時間長、占用內(nèi)存多 堆排序 0(nlbn) 執(zhí)行時間短編寫有點麻煩，有較差的情況 計數(shù)排序 0(n+m) 編寫方便，取值范圍小時很高效取值范圍大時效率低、易超內(nèi)存 限制 歸并排序 0(nib

27、n) 穩(wěn)定的排序算法，無較差情況占用內(nèi)存很大 競賽中首選快速排序、堆排序。但有時也應(yīng)比較各排序的優(yōu)缺點，依實際合理選用。習題 排序的習題 感謝深藍評測系統(tǒng)提供習題103. 搜索a. 復雜的模擬問題與利用相似性 在講模擬方法時我們講過利用相似性來簡化算法?，F(xiàn)在，我們繼續(xù)關(guān)注這個問題。搜索算法是一種 “模擬”思維的算法，比較接近平常的思維。與模擬算法相比，它 更深刻地利用了相似性。為了更好地說明，下面舉一個例子： 有一把有n位字母的密碼鎖，每一位上的字母都可從a到Z選取?，F(xiàn)密碼被遺忘，開鎖 時，請給出一個 方便的方法，使每個字母組合都被嘗試過。最容易想至y的方法便是，按 aaaa , aaab ,

28、 aaac , ，aaaz , aaba , -ZZ zy ZZ Z這樣的字典序來嘗試。我們可以這樣考慮：先選定第一位，再選定第二位，直到選定第n位，形成一個完整的字母組合。具體地，在每一位的選取時，都從a開始，到后面位的字母組合全部嘗試過，再跳到 下一個字母；若（非 首位）已經(jīng)跳到z而還需再跳一個字母時，就跳到a，同時讓它的前一位跳到下一個 字母。例如， n=3 時，形成的字母組合的順序是aaa-aaa b-aab c-aac z-aaz ba-aba b-abb z-abz ca-aca zz-azz baa-baa zz-bzz caa-caa zzz-zzz以上描述的是一種常見的遍歷方

29、法。我們注意到，選定每一位的過程是極其相似的。我們需要利用這種相似性。b. 函數(shù)的遞歸調(diào)用 結(jié)構(gòu)化編程語言提供的最大好處無疑是函數(shù)的遞歸調(diào)用。如果把函數(shù)看成解決某個問題的過程，那么遞歸就可以看成把問題變成相似而更小 的問題的過程。注意 這兩個關(guān)鍵詞：相似、更小。遞歸的本質(zhì)是利用相似性。我們接著講上面提到的密碼鎖問題?，F(xiàn)在我們要把嘗試過的字母組合都輸出到屏幕 上。我們用遞歸法來完成這個過程。寫遞歸體一般分為兩步：把大問題化成小問題、解 決最小問題。charstring1000,n;voidcode(intLeft) / 遞歸體， Left 表示還需要決定的位數(shù)，這個值隨問題的減小而遞減。11if

30、(Left>=1) / 把大問題化成小問題for(stringn-Left='a'stringn-Left<='z'stringn-Left+) code(Left-1);if(Left=0) / 解決最小問題printf("%s n ",string);intmain() fscanf("%d",&n);stringn=' 0 'code(n);return0;分析這個方法，得知其時間復雜度為 0（26八n）。補充一句，上面的過程也可用n個for的嵌套來實現(xiàn)（你能做到嗎？）。c. 棧與

31、深度優(yōu)先搜索 搜索分為深度優(yōu)先搜索、廣度優(yōu)先搜索兩種。下面用樹區(qū)分這兩種搜索方法。對于樹，從根節(jié)點開始，查找（遍歷）各節(jié)點，分兩種方式：廣度優(yōu)從某一節(jié)點向下擴展時，若先遍歷其子節(jié)點，再查找其子節(jié)點的子節(jié)點 先搜索。從某一節(jié)點向下擴展時，若遇到子節(jié)點就 “深入”到子節(jié)點的子節(jié)點，直到葉子節(jié)點再返回深度優(yōu)先搜索。對于7頂點的完全二叉樹，兩種方式所到達的頂點順序如下：11 2325 45673467廣度優(yōu)先深度優(yōu)先 注意：搜索面對的數(shù)據(jù)結(jié)構(gòu)往往不是樹。顯然，深度優(yōu)先搜索的擴展方式類似于上面敘述的函數(shù)遞歸。這里，我們先分析它。深度優(yōu)先搜索在實現(xiàn)時有兩種方式：遞歸形式、非遞歸形式。遞歸形式利用一個函數(shù)（

32、以整型為例）in tcal（）in tcal()intn;/ 運算n=cal();/遞歸，常在循環(huán)體中 / 運算returnn;/ 返回非遞歸形式利用一個棧，它可以被看作是遞歸形式的一個改變： 當要遞歸地調(diào)用cal(時，不立即調(diào)用cal()，而是將其參數(shù)壓入棧。等函數(shù)運行 完，再從棧中彈 出其參數(shù)并再次執(zhí)行函數(shù) cal( )。這樣，最后被調(diào)用的最先執(zhí)行。由于后查找的是深度最大的，這樣的結(jié)果是深度優(yōu) 先。深度優(yōu)先搜索往往采用遞歸方法。12一代算法宗師迪杰斯特拉( E.W.Dijkstra )極力推崇遞歸法。它編寫方便、清晰， 只是內(nèi)存消耗略 比非遞歸大。非遞歸法往往在擔心內(nèi)存溢出時使用。深度優(yōu)先

33、搜索的巨大優(yōu)勢就是可以率先到達葉子節(jié)點。 對于 “找出一種方法 ”、“找 出其中一個解 ”這樣的 問題有速度上的優(yōu)勢。這里舉例分析。八數(shù)碼問題：九宮格里有八個分別填上了數(shù)字 1-8 ，形成最初構(gòu)型。每步只能把空格 上下左右的數(shù)之一 與空格對調(diào)?，F(xiàn)要求找出一種方法，使若干步對調(diào)后呈現(xiàn)目標構(gòu)型。例如：5721234_1->456 63878思路：每次將一個構(gòu)型變?yōu)榱硪粋€，再遞歸地檢查后者能否到達目標構(gòu)型。時間復 雜度0（4八n）。偽代碼：intEightNumbers（構(gòu)型 ）這里返回步驟數(shù)，若需要知道具體步驟，則用另用棧儲存步驟。同源構(gòu)型則返回 32767同目標構(gòu)型則返回 0 step=n

34、1-4 最小值n1=EightNumbers(變化出的構(gòu)型1)n2=EightNumbers(變化出的構(gòu)型2)n3=EightNumbers(變化出的構(gòu)型3)n4=EightNumbers(變化出的構(gòu)型 4）step 為32767 則返回 32767返回 step+1d. 深度優(yōu)先搜索的優(yōu)化 顯然，以上代碼是可以優(yōu)化的。深搜的優(yōu)化過程也叫 “剪枝 ” ?？紤]到實用性，這 里我們只講最簡單的剪 枝方法。對于上面的偽代碼，將 “同源構(gòu)型則返回 32767” 改為 “同已查找構(gòu)型則返回32767 ”就可以顯著提高效率。但是這里需要開辟一個數(shù)組（棧），記錄之前 “經(jīng)過”的構(gòu)型。如果想避免遍歷數(shù) 組，可

35、以做成哈希表， 而且要壓縮儲存才行。還有的簡單方法，編寫的時候自然會想到的。關(guān)鍵是要權(quán)衡，用這樣的方法所增加 的編寫難度是否配得 上所節(jié)省的運行時間。編寫難度增大，調(diào)試的難度也會增大哦。e. 隊列與廣度優(yōu)先搜索 上面講過用棧來非遞歸地實現(xiàn)深搜。若是把棧改成隊列呢？ 經(jīng)過分析，你會發(fā)現(xiàn)，這樣修改后深搜變成了廣搜！ 用這樣的方法可以實現(xiàn)廣搜。用數(shù)組實現(xiàn)隊列時避免大量元素的移動。 實現(xiàn)時， 可以先算出隊列元素的上限 max ， 開辟 amax ，并 設(shè)ast為隊列起始（st初值為0），隊列的第i項儲存在a（st+i-1）%max。這樣，出隊列只用將 st=（+st%max） 即可。要注意的問題是，廣

36、搜類似于遞推，往往需要開辟空間儲存每一步 “遞推 ”所得到 的值。f. 廣度優(yōu)先搜索的優(yōu)化 廣度優(yōu)先搜索比較容易優(yōu)化，運行時間往往比深搜短一些（不過內(nèi)存占用比深搜大 得多）。另外，廣搜 有時可以清晰地反映搜索深度。若上面的八數(shù)碼問題改為 “現(xiàn)要求找出一種方法，使呈現(xiàn)目標構(gòu)型經(jīng)過的對調(diào)步數(shù) 最少”，則用廣搜更好。13廣搜常用的優(yōu)化方法： 哈希表法 記錄隊列中已有節(jié)點，用于判斷是否需要擴展節(jié)點。A*算法一一構(gòu)造估價函數(shù)。雙向廣度優(yōu)先搜索從源節(jié)點、目標節(jié)點一起開始搜索。由于NOIP提高組近年來幾乎不出搜索題； 可用搜索的題目，由于搜索時間復雜度太 高，數(shù)據(jù)規(guī)模太大， 搜索只能得部分分數(shù)。加之搜索思路

37、較簡單，搜索法這里不再詳細敘述。若想了解， 大家可以用搜索 引擎搜索。習題 搜索的習題 感謝深藍評測系統(tǒng)提供習題144. 貪心方法a. 工程計劃模型 我們常常碰到這樣的問題：完成一個工程需要若干個步驟，每個步驟都有若干種方 法，圖示 步驟a步驟b步驟c.步驟n 方法b1方法c1 方法a1方法b2方法c2方法n1 方法a2方法b3方法c3 方法c4 每個方法有一個權(quán)值（如效率、質(zhì)量），其大小往往和其他步驟中選取的方法有關(guān)。有些時候權(quán)值無意 義，表示方法不可選擇。要求給出一個方法組合，是權(quán)值和最大。在這里，暫且把它稱作 “工程計劃 ”。很多實際問題都可以歸納為這個模型。對于不同形式的工程計劃，我們

38、有不同的解法。時間復雜若權(quán)值與整個過程或前后步驟的方法選擇都有關(guān)，我們使用搜索算法 度高得嚇人。若每個權(quán)值只與上（或下）一步或少數(shù)幾步的方法選擇都有關(guān)，我們使用動態(tài)規(guī)劃有比較高的效率， 在下一章會講到。若每個權(quán)值與其他步驟的方法選擇都沒有關(guān)系，我們使用貪心方法。b. 部分背包與每步最優(yōu) 強調(diào)：每個權(quán)值與其他步驟的方法選擇都沒有關(guān)系。這樣每步最優(yōu)就可以得到全局 最優(yōu) 每一步都取最 大的權(quán)值就可以了。換而言之，貪心算法要求，局部的貪心選擇，可以組成全局的最優(yōu)解。在實際問題中，這是需要證明的。如果這個無法證明，貪心算法所得的解不是最優(yōu) 解，一般只是較優(yōu)解較優(yōu)解可為搜索剪枝提供方便）。面是貪心算法最經(jīng)

39、典的例子： 部分背包問題。下一章會講到另外兩種背包問題。 ）問題：有N件物品和一個最大載重為M的背包,每件物品都有相應(yīng)的重量和價值?，F(xiàn)要求給出一個存放方案，使背包中物品總價值最大。部分背包要求，每件物品都可只裝入它的一部分部分重量有成比 例的部分價值）。所涉及到的數(shù)字均為整數(shù)。注：有時該問題表述為體積形式，即背包體積有限，每件物品有體積和價值。在 本系列我選擇表述為重量形式。） 思路：背包中物品總價值最高，即單位重量物品價值最高。顯然，應(yīng)該多裝單位重 量價值高的物品。這 樣，我們先裝入單位重量價值最高的物品， 再裝入第二高的直到重量達到M （有 必要時最后一件物 品只裝一部分），已達到物品總價

40、值最高。這個證明應(yīng)該很嚴謹吧 該算法時間復雜度 O（n） ，效率很高；而且實現(xiàn)很容易。這些是貪心法最大的特點。很多競賽題看似可以用貪心法，其實貪心法得不到最優(yōu)解，原因是每一步的選擇對 其他步驟有影響。數(shù)字三角形問題：有一個數(shù)字三角形（如下圖）?，F(xiàn)有一只螞蟻從頂層開始向下走， 每走下一級時，可 向左下方向或右下方向走。求走到底層后它所經(jīng)過的數(shù)的最大值。63 826 2165 32476如果用貪心法，每次向最大的方向走，得到結(jié)果為 1+6+8+2+3=20 ?？墒敲髅鬟€ 有另一條路，1+3+6+6+7=23 。15問題出在哪？每次的選擇對后面的步驟會有影響！第三級選了8，就選不到第四、五級較大的數(shù)

41、了。這個問題正確的解法會在下一章介紹。有一個很實用的小技巧：競賽題會給出數(shù)據(jù)規(guī)模。通過數(shù)據(jù)規(guī)模，我們可以大致判 斷該用何種算法。貪 心算法可承受的數(shù)據(jù)規(guī)模很大， 一般都會上萬。 如果給出的數(shù)據(jù)規(guī)模是 100或1000 ， 優(yōu)先考慮動態(tài)規(guī) 劃吧。c. 構(gòu)造貪心算法 構(gòu)造與證明是貪心算法的難點，常常要求我們要有敏銳的觀察力、多角度思考的變 通能力、豐富的數(shù)學 知識和推理能力。面舉幾個貪心算法的例子，供大家揣摩、掌握規(guī)律。刪數(shù)問題：給出一個N位的十進制高精度數(shù)，要求從中刪掉 S個數(shù)字（其余數(shù)字相對位置不得改變）， 使剩余數(shù)字組成的數(shù)最小。算法構(gòu)造：1.每次找出最靠前的這樣的一對數(shù)字兩個數(shù)字緊鄰， 且

42、前面的數(shù)字大于后面的。刪除這對數(shù)字中靠前 的一個。2.重復步驟1，直至刪去了 S個數(shù)字或找不到這樣的一對數(shù)。3.若還未刪夠S個數(shù)字，則舍棄末尾的部分數(shù)字，取前 N-S個。證明思路：顯然，在只刪一個數(shù)字時，唯有步驟 1 的方法能使數(shù)變?。豢赏评淼贸?， 刪多個數(shù)字時，所 有最優(yōu)的方法都可看做是對步驟 1的重復。也就是說，以上方法是最優(yōu)策略之一。在文末的附件中給出了這個算法的源代碼。工序問題：n件物品，每件需依次在A、B機床上加工。已知第i件在A、B所需加工時 間分別為 Ai 、Bi ，設(shè)計一加工順序，使所需加工總時間最短。算法構(gòu)造：1.設(shè)置集合F、M、S:先加工F中的，再加工M中的，最后加工S中的

43、。2.對第i件，若AiBi，則歸入S;若Ai=Bi，則歸入M 。3.對F中的元素按Ai升序排列，S中的按Bi降序排列。證明思路：1.F中的能“拉開” A、B加工同一件工件的結(jié)束時刻，為后面的工件加工“拉開時 間差 ” ，利于節(jié)省總時 間。S中的剛好相反。因而，F(xiàn)中元素放在最前一定是最優(yōu)策略之一。2.F中Ai小的前置，可以縮短開始時B的空閑時間，但會使F所有工件“拉開的時間差”縮短。不過可以證明，后者帶來的損失不大于前者獲得的優(yōu)勢。對稱地，對S也一樣。因而步驟 3 是可行的。種樹問題：一條街道分為n個區(qū)域（按1-n編號），每個都可種一棵樹。有m戶居民, 每戶會要求在區(qū) 域i-j區(qū)間內(nèi)種至少一棵樹

44、?，F(xiàn)求一個能滿足所有要求且種樹最少的方案。算法構(gòu)造：1.對于要求，以區(qū)間右端（升序）為首要關(guān)鍵字，左端（升序）為次要關(guān)鍵字排序。2.按排好的序依次考察這些要求，若未滿足，則在其最右端的區(qū)域種樹，這時可能會滿足多個要求。證明思路：解法并不唯一， 關(guān)鍵是證明沒有比該解法更好的解法。 按步驟1排序之后， 會發(fā)現(xiàn)對于每個要求，在最右邊的區(qū)域內(nèi)種樹所得的結(jié)果總不會差于在其他區(qū)域種樹。至于為什么 這樣排序，留給你讀者們思考吧。在文末的附件中給出了這個算法的源代碼。習題貪心方法的習題感謝深藍評測系統(tǒng)提供習題165. 動態(tài)規(guī)劃a. 另一種形式的工程計劃b. 記憶化搜索c. 數(shù)字三角形：遞推地思考問題d. 石子

45、合并：狀態(tài)的確定e. 街道問題：狀態(tài)量維數(shù)的確定與無后效性f. 0-1 背包：巧妙地選取狀態(tài)量g. Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方式h. 最長非降子序列模型i. 構(gòu)造動態(tài)規(guī)劃算法j. 動態(tài)規(guī)劃、遞推、廣度優(yōu)先搜索的區(qū)別與轉(zhuǎn)化a. 另一種形式的工程計劃 上一章我們講過， 若工程計劃問題中某一步權(quán)值只和上一步或少數(shù)幾步的選擇有關(guān)， 我們可以使用效率 較高的動態(tài)規(guī)劃算法?？聪旅孢@個問題：4-9/ 1-2-5-3-1 / 1-7-8上圖的數(shù)字間連了線?，F(xiàn)要從最左邊的 “1” 走到最右邊的 “1” ，每次都只能沿線 向右走到右邊一列的某 個數(shù)上，要求找出一條路徑，路徑上的五個數(shù)之和最大。當然我們

46、可以把這理解為工程計劃問題的一種形式。這里，每一步的選擇與上一步相關(guān)；似乎也與前面幾步的選擇有關(guān)，但是注意，前 幾步的影響都可以表 現(xiàn)在上一步上，上一步方法的選擇已經(jīng)可以獨立決定這一步每種選擇的權(quán)值。此處 適用動態(tài)規(guī)劃。換句“專業(yè)”點的話，這里滿足 “無后效性原則 ”，即之后過程不受之前具體過程 的影響。這在后面會具體 說明。b. 記憶化搜索 再講動態(tài)規(guī)劃之前，我們先接觸一下記憶化搜索。注意到，在深度優(yōu)先搜索中，用于遞歸的函數(shù)cal(有時會被用同樣的參數(shù)調(diào)用多次。你可能很容易 想到，如果在第一次調(diào)用時把參數(shù)和對應(yīng)的函數(shù)值儲存起來，若以后再以同樣的參 數(shù)調(diào)用，就不用執(zhí) 行遞歸函數(shù)，直接取出所得的

47、值，不是快得多？ 如果你能想到這些，你就已經(jīng)學會記憶化搜索了。事實上，記憶化搜索能大幅提高效率的地方，往往是在動態(tài)規(guī)劃的題目中。動態(tài)規(guī)劃能解決的問題，往往可以用記憶化搜索替代動態(tài)規(guī)劃解決。如果你實在無 法掌握動態(tài)規(guī)劃，你 可以選擇使用記憶化搜索。不過你要注意以下事實： 動態(tài)規(guī)劃程序?qū)崿F(xiàn)較容易，程序段短，便于調(diào)試；記憶化搜索實現(xiàn)就比較繁瑣。雖然記憶化搜索可以把時間復雜度降低到動態(tài)規(guī)劃的水平，但是實際執(zhí)行時間會大 于動態(tài)規(guī)劃，甚至有 幾倍到十幾倍的差距。這里不給出記憶化搜索的代碼了。我們還是首選動態(tài)規(guī)劃吧17c. 數(shù)字三角形：遞推地思考問題 上一章中我們講過數(shù)字三角形問題： 有一個數(shù)字三角形（如下

48、圖）?，F(xiàn)有一只螞蟻從頂層開始向下走，每走下一級時， 可向左下方向或右下 方向走。求走到底層后它所經(jīng)過的數(shù)的最大值。63 826 2165 32476對于這個問題，貪心法得不到最優(yōu)解，搜索法效率太低。我們知道，深度優(yōu)先搜索 利用了遞歸式的思維， 動態(tài)規(guī)劃中，我們使用遞推式的思維。遞歸：要知道第五層時的最大值，就要知道第四層時的最大值；要知道第四層時的三層時的最大值 而每一步推導的方法是相似的。遞推：知道第一層的最大值，就能知道第二層的最大值，也就能知道第三層的最大 值而每一步推導的 方法是相似的。對比之下，遞推思維不是從結(jié)論入手的，有時容易失去方向；但是有時卻可以有很 高的效率。動態(tài)規(guī)劃和普通遞

49、推的區(qū)別在于動態(tài)規(guī)劃需要在每一步作比較、取最優(yōu)值。對于數(shù)字三角形問題，我們可以這樣思考：設(shè)二維數(shù)組Aij，表示走到第i行的第j個數(shù)時所經(jīng)實現(xiàn)過的數(shù)字和的最大值。例如對圖中三角形， A32=max1+6+2,1+3+2這樣，我們又可以得到遞推關(guān)系 Aij=pij+maxAi-1j-1,Ai-1j時注 意Ai-1j-1或Ai-1j不存在時的處理），其中pij表示第i行的第j個數(shù)的數(shù)值。此外，我們還需要一些初始值： pij （輸入）， A11=p11。最終我們可以求出A5j，結(jié)論自然是maxA5j 啦 分析這個算法，若層數(shù)大于5，則時間復雜度為0（n八2）。若用搜索，時間復雜度為0（2八n）。顯然動

50、態(tài)規(guī)劃效率高很多。為了更清楚地說明動態(tài)規(guī)劃算法，我們先引入一些概念。階段 我們把問題劃分為幾步，在動態(tài)規(guī)劃中，這叫做 “劃分階段 ”。數(shù)字三角 形中，每一層可看作是 個階段。狀態(tài) 每一階段有多種選擇，不同的選擇會有不同的結(jié)果，我們把每階段的不同 情形叫做 “狀態(tài)”。每一階段包括多個狀態(tài)。數(shù)字三角形中，表示走到第 j 個數(shù)時所經(jīng)過的數(shù)字和的最大值的 變量叫做狀態(tài)。動態(tài)轉(zhuǎn)移方程我們可以用一個遞推式表示某階段到下一階段的遞推關(guān)系，這個 遞推式叫做動態(tài)轉(zhuǎn)移方 程。動態(tài)轉(zhuǎn)移方程一般含有 max 或 min 。決策 即對方法的選擇。每個階段都有一個決策。這樣的選擇是有范圍的，這個 范圍叫做 “ 決策允許集

51、 合”。策略 一套完整的決策的組合。 “最優(yōu)策略 ”即最佳的決策組成的策略。還有一些概念因為使用較少，這里不再詳細介紹。注意可以運用動態(tài)規(guī)劃解決的問題的兩個必需特性： 最優(yōu)化原理 簡單地說，最優(yōu)策略某幾個連續(xù)階段上的決策組合，也是這幾個階 段組成的子問題的最優(yōu)策略。無后效性原則某階段以后的決策，與該階段之前的具體決策無關(guān)，只與該階段這正是動這決定了的狀態(tài)有關(guān)。注意，有些時候我們認為不滿足這兩點的問題，換個角度看又是滿足的。態(tài)規(guī)劃的難點。接下 來我們就是要尋找合適的角度，找出滿足這兩個關(guān)系的算法。d. 石子合并：狀態(tài)的確定 用動態(tài)規(guī)劃解決問題，首要也是最重要的步驟就是劃分階段、確定狀態(tài)。是否能成

52、功運用動態(tài) 規(guī)劃方法。因此。確定一個可行的遞推思路是成功的關(guān)鍵。在這一過程中，要善于變通。石子合并： N 堆石子圍成一圈，每堆石子的量 ai 已知。每次可以將相鄰兩堆合并為 一堆，將合并后 石子的總量記為這次合并的得分。 N-1 次合并后石子成為一堆。 求這 N-1 次合并的得 分之和可能的最大 值。數(shù)據(jù)規(guī)模：N< 100 , 算法構(gòu)造：分析數(shù)據(jù)規(guī)模算法可承受的最大數(shù)據(jù)規(guī)模0（N八3），搜索必然超時，貪心可承 受數(shù)據(jù)規(guī)模太大，優(yōu)先 考慮動態(tài)規(guī)劃。遞推思路一一計算將第i堆至第j堆完全合并所能獲得的最大得分。這是此題的關(guān)鍵?？紤]模擬每種合并 后的具體情形是行不通的。把問題變成這樣后就好解決了。劃分階段 以合并的次數(shù)作為標準劃分階段。確定狀態(tài)一一第i堆至第j堆合并所能獲得的最大價值。< kvj <n狀態(tài)轉(zhuǎn)移方程 f(i,j)=maxf(i,k)+f(k+1,j),0<i邊界狀態(tài) f(i,i)=ai分析知時間復雜度為0（n八3），滿足要求。遞推求出