數(shù)據(jù)結(jié)構(gòu)上海交通大學

1、1第第15章章 算法設(shè)計技術(shù)算法設(shè)計技術(shù) 枚舉法枚舉法 貪婪法貪婪法 分而治之法分而治之法 動態(tài)規(guī)劃動態(tài)規(guī)劃 回溯法回溯法 隨機算法隨機算法介紹通用的算法設(shè)計模式介紹通用的算法設(shè)計模式2枚舉法枚舉法 枚舉法適合于解的候選者是有限、可枚舉枚舉法適合于解的候選者是有限、可枚舉的場合。的場合。 枚舉法就是對可能是解的眾多候選者按某枚舉法就是對可能是解的眾多候選者按某種順序進行逐一枚舉和檢驗，從中找出符種順序進行逐一枚舉和檢驗，從中找出符合要求的候選解作為問題的解。合要求的候選解作為問題的解。 基于枚舉法的算法一般都比較直觀，容易基于枚舉法的算法一般都比較直觀，容易理解。但由于要檢查所有的候選解，因此

2、理解。但由于要檢查所有的候選解，因此時間性能較差時間性能較差 3枚舉法實例枚舉法實例 用用5050元錢買了三種水果：西瓜、蘋果和元錢買了三種水果：西瓜、蘋果和桔子。各種水果加起來一共桔子。各種水果加起來一共100100個。假如，個。假如，西瓜西瓜5 5元一個，蘋果元一個，蘋果1 1元一個，桔子元一個，桔子1 1元元3 3個，設(shè)計一算法輸出每種水果各買了幾個，設(shè)計一算法輸出每種水果各買了幾個。個。 4約束條件約束條件 三種水果一共三種水果一共100100個；個； 買三種水果一共花了買三種水果一共花了5050元。元。 如果西瓜有如果西瓜有mellonmellon個，蘋果有個，蘋果有appleapp

3、le個，桔個，桔子有子有orangeorange個，那么：個，那么： mellon + apple + orange 等于等于100 5 * mellon + 1 * apple + orange /3等于等于50。 5直觀的枚舉直觀的枚舉For (mellon = 1, mellon 99; + mellon) For (apple = 1, apple 99; +apple) For (orange = 1; orange 99; orange) If （mellon + apple + orange 等于等于100 并且并且 5 * mellon + 1 * apple + orange

4、 /3等于等于50） 輸出此方案；輸出此方案；列出所有的情況，檢查是否滿足兩個約束條件列出所有的情況，檢查是否滿足兩個約束條件6改進的方案改進的方案int main() int mellon, apple, orange; for (mellon=1; mellon10; +mellon) for ( apple=1; apple 50 - 5 * mellon; +apple) orange = 3*(50-5*mellon-apple); if (mellon+apple+orange = 100) cout mellon: mellon ; cout apple: apple ; cou

5、t orange: orange 0 ? aleft : 0; maxLeft = maxSum(a, left, center); maxRight = maxSum(a, center + 1, right); 19for (int i = center; i = left; -i) leftSum += ai; if (leftSum maxLeftTmp) maxLeftTmp = leftSum; for (int i = center + 1; i maxRightTmp) maxRightTmp = rightSum; return max3(maxLeft, maxRight,

6、 maxLeftTmp + maxRightTmp);20分治法實例分治法實例 最長連續(xù)子序列問題最長連續(xù)子序列問題 最近點問題最近點問題 數(shù)學計算問題數(shù)學計算問題21最近點問題最近點問題 在二維平面上有在二維平面上有N N個點，試找出距離最短個點，試找出距離最短的兩個點。的兩個點。 蠻力算法：計算兩兩之間的距離，從中蠻力算法：計算兩兩之間的距離，從中找出最小的一個。找出最小的一個。N N個點有個點有N N（N-1N-1）/2/2對對距離，因此時間復(fù)雜度為距離，因此時間復(fù)雜度為O(NO(N2 2) )22分治法解法分治法解法 將所有的點按將所有的點按x x值排序。取一個合適的值排序。取一個合適

7、的x x值，值，把所有點分成兩半把所有點分成兩半P PL L和和P PR R。距離最近的兩個。距離最近的兩個點可能出現(xiàn)在點可能出現(xiàn)在P PL L中中(d(dL L) )，也可能出現(xiàn)在，也可能出現(xiàn)在P PR R(d(dR R) )中，也可能一個點在中，也可能一個點在P PL L，一個點在，一個點在P PR R(d(dC C) ) d dL L和和d dR R可用遞歸得到可用遞歸得到 d dC C的計算：的計算：設(shè)設(shè)=min(=min(d dL L,d,dR R) )如果如果d dC C比比大，則沒必要計算。因此用于計算大，則沒必要計算。因此用于計算d dC C的點必須落在分界線的點必須落在分界線

8、 的范圍內(nèi)，計算此的范圍內(nèi)，計算此范圍中點對的距離中的最小值范圍中點對的距離中的最小值23dLdRdC24優(yōu)化優(yōu)化 在最壞的情況下，所有的點都落在分界在最壞的情況下，所有的點都落在分界線線以內(nèi)。但此時不一定要計算所有點以內(nèi)。但此時不一定要計算所有點對的距離。只要兩點的對的距離。只要兩點的y y坐標大于坐標大于，這，這兩點之間的距離也不用算了。兩點之間的距離也不用算了。 假設(shè)該區(qū)間中的點按假設(shè)該區(qū)間中的點按y y坐標排序，則可得坐標排序，則可得下列算法下列算法25 for( i= 0; i= ) break; else if( dist(pj, pj+1) ) = dist(pj, pj+1);

9、26分治法實例分治法實例 最長連續(xù)子序列問題最長連續(xù)子序列問題 最近點問題最近點問題 數(shù)學計算問題數(shù)學計算問題27數(shù)學計算問題數(shù)學計算問題 設(shè)設(shè)X X和和Y Y是兩個是兩個N N位的整數(shù)，假如一位乘法花位的整數(shù)，假如一位乘法花費一個單位時間，那么計算費一個單位時間，那么計算 X X* *Y Y 的時間復(fù)的時間復(fù)雜性為雜性為O(NO(N2 2) ) 分治法計算分治法計算將將X X和和Y Y均分成兩半，分別稱為均分成兩半，分別稱為X XL L，X XR R，Y YL L，Y YR R。則則 X = XX = XL L1010N/2N/2+X+XR R， Y = YY = YL L1010N/2N/

10、2+Y+YR R。那么，。那么，XY=XXY=XL LY YL L1010N N+(X+(XL LY YR R+X+XR RY YL L) 10) 10N/2N/2+X+XR RY YR R時間復(fù)雜度：時間復(fù)雜度：T(N) = 4T(N/2) + O(N) =O(NT(N) = 4T(N/2) + O(N) =O(N2 2) )28進一步改進進一步改進 上述算法的問題是需要太多次（上述算法的問題是需要太多次（4 4次）的遞歸調(diào)用。如果次）的遞歸調(diào)用。如果能減少遞歸調(diào)用，則能提高時間性能能減少遞歸調(diào)用，則能提高時間性能 注意：注意：X XL LY YR R+X+XR RY YL L = (X =

11、 (XL L X XR R)(Y)(YR R Y YL L) + X) + XL LY YL L + X+ XR RY YR R 代入前式，代入前式，XY=XXY=XL LY YL L1010N N+(X+(XL LY YR R+X+XR RY YL L) 10) 10N/2N/2+X+XR RY YR R= = X XL LY YL L1010N N+(X+(XL L X XR R)(Y)(YR R Y YL L) + X) + XL LY YL L + X+ XR RY YR R ) ) 1010N/2N/2+X+XR RY YR R 可見只需可見只需3 3次遞歸調(diào)用次遞歸調(diào)用 時間復(fù)雜性

12、：時間復(fù)雜性：)()()()2/(3)(59. 13log2NONONONTNT29第第15章章 算法設(shè)計技術(shù)算法設(shè)計技術(shù) 枚舉法枚舉法 貪婪法貪婪法 分而治之法分而治之法 動態(tài)規(guī)劃動態(tài)規(guī)劃 回溯法回溯法 隨機算法隨機算法介紹通用的算法設(shè)計模式介紹通用的算法設(shè)計模式30動態(tài)規(guī)劃動態(tài)規(guī)劃 用表代替遞歸用表代替遞歸 例：斐波那契函數(shù)例：斐波那契函數(shù)f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)。計算計算f(n)f(n)需要計算需要計算f(n-1)f(n-1)和和f(n-2)f(n-2)。當計。當計算算f(n-1)f(n-1)時要計算時要計算f(n-2)f(n-2)和和f(

13、n-3)f(n-3)。因此。因此在計算在計算f(n)f(n)中中f(n-2)f(n-2)被計算了兩次。被計算了兩次。 為了減少重復(fù)的遞歸調(diào)用，我們可以反過為了減少重復(fù)的遞歸調(diào)用，我們可以反過來計算。先計算來計算。先計算f(2)f(2)，有了，有了f(2)f(2)再計算再計算f(3)f(3)，以此類推，計算到，以此類推，計算到f(n)f(n)。在此過程。在此過程中不需要任何遞歸中不需要任何遞歸31動態(tài)規(guī)劃動態(tài)規(guī)劃 硬幣找零問題硬幣找零問題 最優(yōu)二叉查找樹最優(yōu)二叉查找樹32找零問題找零問題 對于一種貨幣，有面值為對于一種貨幣，有面值為C1, C2, , C1, C2, , CN(CN(分分) )的

14、硬幣，最少需要多少個硬幣來的硬幣，最少需要多少個硬幣來找出找出K K分錢的零錢。分錢的零錢。33貪婪法解法貪婪法解法 我們不斷使用可能的最大面值的硬幣我們不斷使用可能的最大面值的硬幣 如：美元的硬幣有如：美元的硬幣有1 1、5 5、1010和和2525分的面值分的面值( (忽略流忽略流通頻率很低的通頻率很低的5050分硬幣分硬幣) )。我們可以通過使用。我們可以通過使用2 2個個2525分、一個分、一個1010分的硬幣以及三個分的硬幣以及三個1 1分來找出分來找出6363分錢，分錢，一共是一共是6 6個硬幣。個硬幣。 如果美元中包含一個如果美元中包含一個2121分硬幣時，貪心算法仍然分硬幣時，

15、貪心算法仍然給出一個用六個硬幣的解，但是最佳的解是用三給出一個用六個硬幣的解，但是最佳的解是用三個硬幣個硬幣( (三個都是三個都是2121分的硬幣。分的硬幣。) ) 34解法解法1分治法分治法如果我們可以用一個硬幣找零，這就是如果我們可以用一個硬幣找零，這就是最小的。最小的。否則，對于每個可能的值否則，對于每個可能的值i i，我們可以獨，我們可以獨立計算找立計算找i i分錢零錢和分錢零錢和K-iK-i分錢需要的最分錢需要的最小硬幣數(shù)。然后選擇這個和最小的小硬幣數(shù)。然后選擇這個和最小的i i。 35怎樣找出怎樣找出63分錢零錢分錢零錢 找出找出1 1分錢零錢和分錢零錢和6262分錢零錢分別需要的

16、硬幣數(shù)是分錢零錢分別需要的硬幣數(shù)是1 1和和4 4。因此，。因此，6363分錢需要使用五個硬幣。分錢需要使用五個硬幣。 找出找出2 2分錢和分錢和6161分錢分別需要分錢分別需要2 2和和4 4個硬幣，一共是個硬幣，一共是六個硬幣。六個硬幣。 我們繼續(xù)嘗試所有的可能性。我們看到一個我們繼續(xù)嘗試所有的可能性。我們看到一個2121分分和和4242分的分解，它可以分別用一個和兩個硬幣來分的分解，它可以分別用一個和兩個硬幣來找開，因此，這個找零問題就可以用三個硬幣解找開，因此，這個找零問題就可以用三個硬幣解決。決。 我們需要嘗試的最后一種分解是我們需要嘗試的最后一種分解是3131分和分和3232分。我

17、分。我們可以用兩個硬幣找出們可以用兩個硬幣找出3131分零錢，用三個硬幣找分零錢，用三個硬幣找出出3232分零錢，一共是五個硬幣。分零錢，一共是五個硬幣。 因此最小值是三個硬幣。因此最小值是三個硬幣。36int coin(int k) int i, tmp, int coinNum = k; if （能用一個硬幣找零）（能用一個硬幣找零） return 1; for (i=1; i coinNum) coinNum = tmp; return coinNum;37上述解法分析上述解法分析 此算法的效率很低此算法的效率很低 事實上事實上6363分錢找零的問題是不會在一個分錢找零的問題是不會在一個

18、合理的時間內(nèi)解決的。就如合理的時間內(nèi)解決的。就如Finbonacci Finbonacci 函數(shù)一樣函數(shù)一樣38解法解法2 通過指定其中的一個硬幣來遞歸地簡化問題。通過指定其中的一個硬幣來遞歸地簡化問題。 例如，對于例如，對于6363分錢，我們可以給出以下找零的辦法。分錢，我們可以給出以下找零的辦法。一個一個1 1分的硬幣加上遞歸地分派分的硬幣加上遞歸地分派6262分錢分錢一個一個5 5分的硬幣加上遞歸地分派分的硬幣加上遞歸地分派5858分錢分錢一個一個1010分的硬幣加上遞歸地分派分的硬幣加上遞歸地分派5353分錢分錢一個一個2121分的硬幣加上遞歸地分派分的硬幣加上遞歸地分派4242分錢分

19、錢一個一個2525分的硬幣加上遞歸地分派分的硬幣加上遞歸地分派3838分錢分錢 該算法的問題仍然是效率問題該算法的問題仍然是效率問題39動態(tài)規(guī)劃解動態(tài)規(guī)劃解 效率低下主要是由于重復(fù)計算造成的。效率低下主要是由于重復(fù)計算造成的。因此，可把已有子問題的答案存放起來，因此，可把已有子問題的答案存放起來，當再次遇到此子問題時就不用重復(fù)計算當再次遇到此子問題時就不用重復(fù)計算了。了。 在本例中，我們用在本例中，我們用coinsUsedicoinsUsedi代表了代表了找找i i分零錢所需的最小硬幣數(shù)。分零錢所需的最小硬幣數(shù)。40算法思想算法思想 先找出一分錢的找零方法，把最小硬幣數(shù)先找出一分錢的找零方法，

20、把最小硬幣數(shù)存入存入coinUsed1 coinUsed1 依次找出依次找出2 2分錢、分錢、3 3分錢分錢的找零方法，知的找零方法，知道到達要找零的錢為止：道到達要找零的錢為止：對每個要找的零錢對每個要找的零錢i i，可以把，可以把i i分解成某個分解成某個coinsjcoinsj和和 i - coinsji - coinsj，所需硬幣數(shù)為所需硬幣數(shù)為coinUsedi-coinsj+1coinUsedi-coinsj+1。對所。對所有的有的j j，取最小的，取最小的coinUsedi-coinsj+1coinUsedi-coinsj+1作作為為i i元錢找零的的答案。元錢找零的的答案。 4

21、1函數(shù)原型函數(shù)原型 Void makechange( int coins, int differentCoins, int maxChange, int coinUsed ) Coins存放所有不同的硬幣值，不同的硬存放所有不同的硬幣值，不同的硬幣個數(shù)為幣個數(shù)為differentCoins。 maxChange為要找的零錢數(shù)為要找的零錢數(shù)42void makechange( int coins , int differentCoins, int maxChange, int coinUsed ) coinUsed0 = 0; for (int cents = 1; cents = maxCha

22、nge; cents+) int minCoins = cents; for (int j = 1; j cents) continue; if (coinUsed cents - coinsj + 1 minCoins) minCoins = coinUsed cents - coinsj + 1; coinUsedcents = minCoins; 43動態(tài)規(guī)劃動態(tài)規(guī)劃 硬幣找零問題硬幣找零問題 最優(yōu)二叉查找樹最優(yōu)二叉查找樹44最優(yōu)二叉查找樹最優(yōu)二叉查找樹 有一組詞有一組詞 w1,w2,wNw1,w2,wN，他們的出現(xiàn)概率分別，他們的出現(xiàn)概率分別為為p1,p2,pNp1,p2,pN。構(gòu)建一

23、棵二叉排序樹使得訪問。構(gòu)建一棵二叉排序樹使得訪問時間的期望值最小。即如果時間的期望值最小。即如果wiwi所在的層次是所在的層次是didi，那么那么 該問題類似于哈夫曼樹，概率大的靠近根，概該問題類似于哈夫曼樹，概率大的靠近根，概率小的遠離根。但它比哈夫曼樹更復(fù)雜。因為率小的遠離根。但它比哈夫曼樹更復(fù)雜。因為它還要滿足二叉排序樹的特性它還要滿足二叉排序樹的特性Niiidp1)1 (45貪婪法的解法貪婪法的解法 選擇出現(xiàn)概率最大的詞作為樹根，把剩余的詞選擇出現(xiàn)概率最大的詞作為樹根，把剩余的詞分成兩組：小于根的和大于根的。遞歸構(gòu)建左分成兩組：小于根的和大于根的。遞歸構(gòu)建左子樹和右子樹。子樹和右子樹。

24、A0.22Am0.18And0.20Egg0.05If0.25The0.02two0.08iftwotheaandamegg顯然不是最優(yōu)的，代價為：顯然不是最優(yōu)的，代價為：2.4346最優(yōu)解法最優(yōu)解法 假如要對假如要對w wleftleft到到w wrightright構(gòu)建一棵最優(yōu)二叉排序樹，那么構(gòu)建一棵最優(yōu)二叉排序樹，那么這棵樹的形式一定是根為這棵樹的形式一定是根為w wi i，左子樹的節(jié)點為，左子樹的節(jié)點為leftleft到到i-1i-1，右子樹的節(jié)點為，右子樹的節(jié)點為i+1i+1到到rightright，左子樹和右子樹，左子樹和右子樹也是最優(yōu)的也是最優(yōu)的 設(shè)設(shè)C Cleftleft，ri

25、ghtright是樹的代價，那么是樹的代價，那么)(min)(min, 11,11, 11,rightleftjjrightiileftrightileftrightijjileftjjrightiileftirightileftrightleftpCCppCCpC47最優(yōu)解法最優(yōu)解法 對對 a,am.and,egg,if,the,twoa,am.and,egg,if,the,two對所有的可能的情況計算它對所有的可能的情況計算它的代價，從中找出最小的：的代價，從中找出最小的：根為根為a a，左子樹為空，右子樹為，左子樹為空，右子樹為amam，twotwo。根為根為amam，左子樹為，左子樹為

26、a a，右子樹為，右子樹為and,and,，twotwo。根為根為andand，左子樹為，左子樹為a a，am,am,右子樹為右子樹為egg,egg,，twotwo。根為根為eggegg，左子樹為，左子樹為a,am,and,a,am,and,右子樹為右子樹為if,if,，twotwo。 在上述每一種情況中，我們需要繼續(xù)遞歸。如：在嘗試根在上述每一種情況中，我們需要繼續(xù)遞歸。如：在嘗試根為為eggegg，左子樹為，左子樹為a,am,and,a,am,and,右子樹為右子樹為if,if,，twotwo的情況時，的情況時，要找出最優(yōu)的左子樹，我們又要嘗試要找出最優(yōu)的左子樹，我們又要嘗試根節(jié)點為根節(jié)點

27、為a a，左子樹為空，右子樹為，左子樹為空，右子樹為amam和和andand根節(jié)點為根節(jié)點為amam，左子樹為，左子樹為a a，右子樹為，右子樹為andand根節(jié)點為根節(jié)點為andand，左子樹為，左子樹為a a和和amam，右子樹為空。，右子樹為空。48動態(tài)規(guī)劃解法動態(tài)規(guī)劃解法 從上述分析可以看出，在找出由從上述分析可以看出，在找出由a a到到twotwo組成組成的最優(yōu)樹時，由的最優(yōu)樹時，由a a組成的樹，由組成的樹，由a a和和amam組成的組成的樹，由樹，由amam和和andand組成的樹，組成的樹，會分別被計算，會分別被計算很多次。很多次。 解決方法：從小到大計算由解決方法：從小到大計

28、算由n n個節(jié)點組成的最個節(jié)點組成的最優(yōu)樹，并把它保存在一個表中。當所有的節(jié)優(yōu)樹，并把它保存在一個表中。當所有的節(jié)點形成了一棵樹時，任務(wù)就完成了。點形成了一棵樹時，任務(wù)就完成了。 每棵樹的保存用兩個信息：根和代價。每棵樹的保存用兩個信息：根和代價。49生成過程生成過程 先生成由一個節(jié)點組成的樹。樹的代價就是節(jié)點先生成由一個節(jié)點組成的樹。樹的代價就是節(jié)點的權(quán)值。保存這些樹和相應(yīng)的代價。的權(quán)值。保存這些樹和相應(yīng)的代價。 生成所有由兩個節(jié)點組成的樹：生成所有由兩個節(jié)點組成的樹： 將第一個節(jié)點作為根，第二個節(jié)點作為右子樹。計算將第一個節(jié)點作為根，第二個節(jié)點作為右子樹。計算代價。代價。 將第二個節(jié)點作為

29、根，第一個節(jié)點作為右子樹。計算將第二個節(jié)點作為根，第一個節(jié)點作為右子樹。計算代價。代價。 取代價小的樹作為最終的樹保存下來。取代價小的樹作為最終的樹保存下來。 生成由三個節(jié)點組成的樹，四個節(jié)點組成的樹生成由三個節(jié)點組成的樹，四個節(jié)點組成的樹50two0.08the0.02if0.25egg0.05and0.20am0.18a0.22Two.twoThe.theIf.ifEgg.eggAnd.andAm.ama.aLeft=7Left=6Left=5Left=4Left=3Left=2Left=1a0.58a.amand0.56Am.andand0.30And.eggif0.35Egg.ifif

30、0.29If.thetwo0.12The.twoand0.66Am.eggand0.80And.ifif0.39Egg.theif0.47If.twoAm1.02a.andand1.21Am.ifif0.84And.theif0.57Egg.twoAm1.17a.eggand1.27Am.theif1.02And.twoAnd1.83a.ifand1.53Am.twoAnd1.89a.theAnd2.15a.twoi=1i=2i=3i=4i=5i=6i=7andaamifeggtwothe51第第15章章 算法設(shè)計技術(shù)算法設(shè)計技術(shù) 枚舉法枚舉法 貪婪法貪婪法 分而治之法分而治之法 動態(tài)規(guī)劃動態(tài)

31、規(guī)劃 回溯法回溯法 隨機算法隨機算法介紹通用的算法設(shè)計模式介紹通用的算法設(shè)計模式52第第15章章 算法設(shè)計技術(shù)算法設(shè)計技術(shù) 枚舉法枚舉法 貪婪法貪婪法 分而治之法分而治之法 動態(tài)規(guī)劃動態(tài)規(guī)劃 回溯法回溯法 隨機算法隨機算法介紹通用的算法設(shè)計模式介紹通用的算法設(shè)計模式53回溯法回溯法 八皇后問題八皇后問題 分書問題分書問題首先暫時放棄問題規(guī)模大小的限制，并將問題的候首先暫時放棄問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)候選解不選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)候選解不可能是解時，就選擇下一候選解。如果當前候選解可能是解時，就選擇下一候選解。如果當前候選解除了不滿足規(guī)模

32、要求外，滿足其他所有要求時，繼除了不滿足規(guī)模要求外，滿足其他所有要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前的候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該的候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。候選解就是問題的一個解。54八皇后問題八皇后問題 在一個在一個8 8* *8 8的棋盤上放的棋盤上放8 8個皇后，使個皇后，使8 8個皇個皇后中沒有兩個以上的皇后會在同一行、后中沒有兩個以上的皇后會在同一行、同一列或同一對角線上同一列或同一對角線上55八皇后問題的求解過程八皇后問題的求解過程 求解過程從空配置開始，在第一列到

33、第求解過程從空配置開始，在第一列到第m m列為合理配置的基礎(chǔ)上再配置列為合理配置的基礎(chǔ)上再配置m+1m+1列，直列，直到第到第n n列的配置也時合理時，就找到了一列的配置也時合理時，就找到了一個解。另外在一列上也有個解。另外在一列上也有n n種配置。開始種配置。開始時配置在第一行，以后改變時，順序選擇時配置在第一行，以后改變時，順序選擇第二行、第三行、。、第第二行、第三行、。、第n n行。當配置行。當配置到第到第n n行時還找不到一個合理的配置時，行時還找不到一個合理的配置時，就要回朔，去改變前一列的配置。就要回朔，去改變前一列的配置。56算法 m = 0; /*從空配置開始從空配置開始*/

34、good = true; /*配置中的皇后不沖突配置中的皇后不沖突*/ do if (good) if (m = 8) 輸出解；輸出解； 重新尋找下一可行的解；重新尋找下一可行的解； else 向前試探，擴展至下一列；向前試探，擴展至下一列； else 回朔，形成下一候選解；回朔，形成下一候選解； good = 檢查當前候選解的合理性；檢查當前候選解的合理性； while (m != 0); 57棋盤的棋盤的數(shù)據(jù)結(jié)構(gòu)的設(shè)計數(shù)據(jù)結(jié)構(gòu)的設(shè)計 比較直觀的方法是采用一個二維數(shù)組，但仔細考察，就會發(fā)比較直觀的方法是采用一個二維數(shù)組，但仔細考察，就會發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性會帶來困難。

35、現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性會帶來困難。 對于本題來說，我們關(guān)心的并不是皇后的具體位置，而是對于本題來說，我們關(guān)心的并不是皇后的具體位置，而是“一個皇后是否已經(jīng)在某行和某條斜線合理地安置好了一個皇后是否已經(jīng)在某行和某條斜線合理地安置好了”。 因為在每一列上恰好放一個皇后，所以引入一個一維數(shù)組因為在每一列上恰好放一個皇后，所以引入一個一維數(shù)組( (設(shè)為設(shè)為colcol（9 9）) )，值，值coljcolj表示在棋盤第表示在棋盤第j j列上的皇后位置。列上的皇后位置。如如col3col3的值為的值為4 4，就表示第三列的皇后在第四行。另外，就表示第三列的皇后在第四行。另外，為了使程

36、序在找完了全部解后回溯到最初位置，設(shè)定為了使程序在找完了全部解后回溯到最初位置，設(shè)定col0col0的初值為的初值為0 0。當回溯到第。當回溯到第0 0列時，說明程序已求得全部解列時，說明程序已求得全部解( (或或無解無解) )，結(jié)束程序執(zhí)行。，結(jié)束程序執(zhí)行。58候選解的合理性檢查候選解的合理性檢查 引入以下三個工作數(shù)組引入以下三個工作數(shù)組 數(shù)組數(shù)組a9a9，aA=trueaA=true表示第表示第A A行上還沒有皇后；行上還沒有皇后；數(shù)組數(shù)組b16b16，bA=truebA=true表示第表示第A A條右高左低斜線條右高左低斜線上沒有皇后；從左上角依次編到右下角上沒有皇后；從左上角依次編到右

37、下角(1-15)(1-15)。數(shù)組數(shù)組c16c16，cA=truecA=true表示第表示第A A條左高右低斜線條左高右低斜線上沒有皇后。從左下角依次編到右上角上沒有皇后。從左下角依次編到右上角(1-15)(1-15)。59 void queen_a11(int k) /在在8x8棋盤的第棋盤的第k列上找合理的配置列上找合理的配置int i, j; char awn; for(i = 1; i = 9; i+) / 依次在依次在l至至8行上配置行上配置k列的皇后列的皇后 if ( ai & bk+i-1 & c8+k-i) /可行位置可行位置 colk = i; ai = bk

38、+i-1 = c8+k-i = false; /置對應(yīng)位置有皇后置對應(yīng)位置有皇后 if (k = 8) / 找到一個可行解找到一個可行解 for (j = 1; j = 8; j+) cout j colj t ; cout awn; if (awn=Q | awn=q) exit(0); else queen_a11(k+1);/遞歸至第遞歸至第k十十1列列 ai = bk+i-1 = c8+k-i = true; /恢復(fù)對應(yīng)位置無皇后恢復(fù)對應(yīng)位置無皇后 60主程序主程序int col9;bool a9, b17,c17;int main() int j; for(j = 0; j =8;

39、j+) aj = true; for(j = 0; j = 16; j+) bj = cj = true; queen_a11(1); return 0; 61回溯法回溯法 八皇后問題八皇后問題 分書問題分書問題首先暫時放棄問題規(guī)模大小的限制，并將問題的候首先暫時放棄問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)候選解不選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)候選解不可能是解時，就選擇下一候選解。如果當前候選解可能是解時，就選擇下一候選解。如果當前候選解除了不滿足規(guī)模要求外，滿足其他所有要求時，繼除了不滿足規(guī)模要求外，滿足其他所有要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。

40、如果當前續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前的候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該的候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。候選解就是問題的一個解。62分書問題分書問題 有編號為有編號為0，1，2，3，4的的5本書，準備分給本書，準備分給5個人個人A，B，C，D，E，每個人的閱讀興，每個人的閱讀興趣用一個二維數(shù)組描述：趣用一個二維數(shù)組描述： Likeij = true i喜歡書喜歡書j Likeij = false i不喜歡書不喜歡書j 寫一個程序，輸出所有皆大寫一個程序，輸出所有皆大歡喜的分書方案歡喜的分書方案00111001100001063存儲設(shè)計

41、存儲設(shè)計 用一個二維數(shù)組用一個二維數(shù)組likelike存儲用戶的興趣存儲用戶的興趣 用一個一維的整型數(shù)組用一個一維的整型數(shù)組taketake表示某本書分表示某本書分給了某人。給了某人。Takej = iTakej = i表示第表示第j j本書給了本書給了第第i i個人。個人。 64解題思路解題思路 依次嘗試把書依次嘗試把書j j分給人分給人i i。如果第如果第i i個人不喜歡第個人不喜歡第j j本書，則嘗試下一本書，如果喜本書，則嘗試下一本書，如果喜歡，并且第歡，并且第j j本書尚未分配，則把書本書尚未分配，則把書j j分配給分配給i i。如果如果i i是最后一個人，則方案數(shù)加是最后一個人，則

42、方案數(shù)加1 1，輸出該方案。否則，輸出該方案。否則調(diào)用調(diào)用trytry（i+1)i+1)為第為第i+1i+1個人分書。個人分書?；厮?。讓第回溯。讓第i i個人退回書個人退回書j j，嘗試下一個，嘗試下一個j j，即尋找下一，即尋找下一個可行的方案個可行的方案由于在每次由于在每次trytry中都要用到中都要用到likelike，taketake以及目前找以及目前找到的方案數(shù)到的方案數(shù)n n，因此可將它們作為全局變量，以免，因此可將它們作為全局變量，以免每次函數(shù)調(diào)用時都要帶一大串參數(shù)。每次函數(shù)調(diào)用時都要帶一大串參數(shù)。設(shè)計一個函數(shù)設(shè)計一個函數(shù)try(i)給第給第i個人分書。個人分書。65void t

43、rynext(int i) int j, k; for (j=0; j5; +j) if (likeij & takej = -1) takej = i; if (i = 4) n+; cout n第第 n 種方案種方案: endl; cout 書書t人人 endl; for (k=0; k5; k+) cout k t char(takek+A) endl; else trynext(i+1); takej = -1; 66truefalsefalsetruefalsefalsetruefalsefalsefalsetruefalsetruetruefalsetruefalsefal

44、setruetruefalsetruetruefalsefalse當當likelike矩陣的值為矩陣的值為調(diào)用調(diào)用trynext(0);trynext(0);的結(jié)果為：的結(jié)果為：第1種方案：書 人0 B1 C2 A3 D4 E第2種方案：書 人0 B1 E2 A3 D4 C67第第14章章 算法設(shè)計技術(shù)算法設(shè)計技術(shù) 枚舉法枚舉法 貪婪法貪婪法 分而治之法分而治之法 動態(tài)規(guī)劃動態(tài)規(guī)劃 回溯法回溯法 隨機算法隨機算法介紹通用的算法設(shè)計模式介紹通用的算法設(shè)計模式68隨機算法隨機算法 在算法中，至少有一個地方使用隨機數(shù)作決策。在算法中，至少有一個地方使用隨機數(shù)作決策。 隨機算法的時間復(fù)雜度取決于選擇的

45、隨機數(shù)隨機算法的時間復(fù)雜度取決于選擇的隨機數(shù) 隨機算法的時間復(fù)雜度用期望的運行時間來表示。隨機算法的時間復(fù)雜度用期望的運行時間來表示。一般假設(shè)隨機數(shù)的選擇是均勻分布的一般假設(shè)隨機數(shù)的選擇是均勻分布的 例如，在快速排序中將中間點用隨機數(shù)來選擇，例如，在快速排序中將中間點用隨機數(shù)來選擇，則快速排序成為一個隨機算法。可以證明，期望則快速排序成為一個隨機算法?？梢宰C明，期望的時間復(fù)雜度為的時間復(fù)雜度為O(NlogN)O(NlogN)69隨機算法實例隨機算法實例 跳表跳表 素數(shù)檢測素數(shù)檢測70跳表跳表 以以O(shè)(logN)O(logN)的期望的時間復(fù)雜性支持插入和刪除的數(shù)據(jù)結(jié)構(gòu)的期望的時間復(fù)雜性支持插入和

46、刪除的數(shù)據(jù)結(jié)構(gòu) 跳表的概念：支持動態(tài)查找必須用鏈表，但鏈表查找的時間為跳表的概念：支持動態(tài)查找必須用鏈表，但鏈表查找的時間為N N?？梢杂迷黾渔湹姆绞教岣卟檎倚?。可以用增加鏈的方式提高查找效率增加一條鏈，讓頭節(jié)點指向第二個節(jié)點，第二個節(jié)點指向增加一條鏈，讓頭節(jié)點指向第二個節(jié)點，第二個節(jié)點指向第四個節(jié)點，第四個節(jié)點指向第六個節(jié)點，第四個節(jié)點，第四個節(jié)點指向第六個節(jié)點，。查找時間。查找時間為為再增加一條鏈，讓頭節(jié)點指向第四個節(jié)點，第四個節(jié)點指再增加一條鏈，讓頭節(jié)點指向第四個節(jié)點，第四個節(jié)點指向第八個節(jié)點，第八個節(jié)點指向第十二個節(jié)點，向第八個節(jié)點，第八個節(jié)點指向第十二個節(jié)點，。查找。查找時間為時間

47、為推而廣之，對于推而廣之，對于2 2i iNN2i+1個節(jié)點，設(shè)置個節(jié)點，設(shè)置i i條鏈，第條鏈，第j j條鏈指條鏈指向其后的第向其后的第2 2j j個節(jié)點個節(jié)點12/N24/N7182101113192022232582101319202325112282101319202325112272查找過程（節(jié)點查找過程（節(jié)點x） 首先查找第首先查找第i i條鏈，如下一節(jié)點比條鏈，如下一節(jié)點比x x大，則查找大，則查找第第i-1i-1條鏈，否則繼續(xù)查找第條鏈，否則繼續(xù)查找第i i條鏈。依次執(zhí)行，條鏈。依次執(zhí)行，直到找到或找不到直到找到或找不到x x 最壞情況下的時間性能：最壞情況下的時間性能：)(l

48、oglog222222222)(12211NONiNNTiiiii73插入過程插入過程 當插入一節(jié)點時，所有的節(jié)點都要變化。為了避免當插入一節(jié)點時，所有的節(jié)點都要變化。為了避免這個變化，插入采用隨機算法這個變化，插入采用隨機算法 定義：有定義：有k k條鏈的節(jié)點稱為條鏈的節(jié)點稱為level-klevel-k節(jié)點節(jié)點 在跳表中，在跳表中，level-ilevel-i的節(jié)點有的節(jié)點有N/2N/2i i個，即個，即level-ilevel-i的的節(jié)點出現(xiàn)的概率為節(jié)點出現(xiàn)的概率為1/21/2i i。 插入過程：插入過程：查找到插入點查找到插入點生成一個新節(jié)點生成一個新節(jié)點按概率生成節(jié)點的按概率生成節(jié)點

49、的levellevel插入該節(jié)點插入該節(jié)點 因此跳表并不一定是嚴格的隔因此跳表并不一定是嚴格的隔2 2i i個節(jié)點有一條第個節(jié)點有一條第i i層層的鏈，而只是從概率上講符合此分布的鏈，而只是從概率上講符合此分布74隨機算法實例隨機算法實例 跳表跳表 素數(shù)檢測素數(shù)檢測75素數(shù)檢測素數(shù)檢測 方法一：依次檢測方法一：依次檢測1 1到到N N能否被能否被N N整除，如果能被整除整除，如果能被整除的數(shù)的個數(shù)等于的數(shù)的個數(shù)等于2 2，則，則N N是素數(shù)。時間復(fù)雜度為是素數(shù)。時間復(fù)雜度為O O（N N） 方法二：依次檢測方法二：依次檢測2 2、3 3、5 5、7 7到到sqrt(N)sqrt(N)，只要有一

50、，只要有一個能整除個能整除N N，則，則N N為非素數(shù)。最壞情況的時間復(fù)雜度為非素數(shù)。最壞情況的時間復(fù)雜度O(NO(N1/21/2) ) 上述兩方法對小素數(shù)適合，大素數(shù)不適合上述兩方法對小素數(shù)適合，大素數(shù)不適合 方法三：隨機算法。該算法能保證：當聲稱是非素數(shù)方法三：隨機算法。該算法能保證：當聲稱是非素數(shù)時，時，100%100%為非素數(shù)；當聲稱是素數(shù)時，有一個可以忽為非素數(shù)；當聲稱是素數(shù)時，有一個可以忽略不計的很小的誤差。略不計的很小的誤差。76理論基礎(chǔ)理論基礎(chǔ) 定理一：如果定理一：如果p p是素數(shù)，并且是素數(shù)，并且0 a p0 a p，那么，那么 A Ap-1p-1 1(mod p) 1(mod p) 定理二：如果定理二：如果p p是素數(shù)，并且是素數(shù)，并且0 xp0 xp，那么方程，那么方程x x2 21 (mod p)1 (m