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

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

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

3、le個(gè)，桔個(gè)，桔子有子有orangeorange個(gè)，那么：個(gè)，那么： 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） 輸出此方案；輸出此方案；列出所有的情況，檢查是否滿(mǎn)足兩個(gè)約束條件列出所有的情況，檢查是否滿(mǎn)足兩個(gè)約束條件6改進(jìn)的方案改進(jìn)的方案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分治法實(shí)例分治法實(shí)例 最長(zhǎng)連續(xù)子序列問(wèn)題最長(zhǎng)連續(xù)子序列問(wèn)題 最近點(diǎn)問(wèn)題最近點(diǎn)問(wèn)題 數(shù)學(xué)計(jì)算問(wèn)題數(shù)學(xué)計(jì)算問(wèn)題21最近點(diǎn)問(wèn)題最近點(diǎn)問(wèn)題 在二維平面上有在二維平面上有N N個(gè)點(diǎn)，試找出距離最短個(gè)點(diǎn)，試找出距離最短的兩個(gè)點(diǎn)。的兩個(gè)點(diǎn)。 蠻力算法：計(jì)算兩兩之間的距離，從中蠻力算法：計(jì)算兩兩之間的距離，從中找出最小的一個(gè)。找出最小的一個(gè)。N N個(gè)點(diǎn)有個(gè)點(diǎn)有N N（N-1N-1）/2/2對(duì)對(duì)距離，因此時(shí)間復(fù)雜度為距離，因此時(shí)間復(fù)雜度為O(NO(N2 2) )22分治法解法分治法解法 將所有的點(diǎn)按將所有的點(diǎn)按x x值排序。取一個(gè)合適的值排序。取一個(gè)合適

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

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

9、26分治法實(shí)例分治法實(shí)例 最長(zhǎng)連續(xù)子序列問(wèn)題最長(zhǎng)連續(xù)子序列問(wèn)題 最近點(diǎn)問(wèn)題最近點(diǎn)問(wèn)題 數(shù)學(xué)計(jì)算問(wèn)題數(shù)學(xué)計(jì)算問(wèn)題27數(shù)學(xué)計(jì)算問(wèn)題數(shù)學(xué)計(jì)算問(wèn)題 設(shè)設(shè)X X和和Y Y是兩個(gè)是兩個(gè)N N位的整數(shù)，假如一位乘法花位的整數(shù)，假如一位乘法花費(fèi)一個(gè)單位時(shí)間，那么計(jì)算費(fèi)一個(gè)單位時(shí)間，那么計(jì)算 X X* *Y Y 的時(shí)間復(fù)的時(shí)間復(fù)雜性為雜性為O(NO(N2 2) ) 分治法計(jì)算分治法計(jì)算將將X X和和Y Y均分成兩半，分別稱(chēng)為均分成兩半，分別稱(chēng)為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時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(N) = 4T(N/2) + O(N) =O(NT(N) = 4T(N/2) + O(N) =O(N2 2) )28進(jìn)一步改進(jìn)進(jìn)一步改進(jìn) 上述算法的問(wèn)題是需要太多次（上述算法的問(wèn)題是需要太多次（4 4次）的遞歸調(diào)用。如果次）的遞歸調(diào)用。如果能減少遞歸調(diào)用，則能提高時(shí)間性能能減少遞歸調(diào)用，則能提高時(shí)間性能 注意：注意：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 可見(jiàn)只需可見(jiàn)只需3 3次遞歸調(diào)用次遞歸調(diào)用 時(shí)間復(fù)雜性

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

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

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

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

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

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

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

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

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

21、1函數(shù)原型函數(shù)原型 Void makechange( int coins, int differentCoins, int maxChange, int coinUsed ) Coins存放所有不同的硬幣值，不同的硬存放所有不同的硬幣值，不同的硬幣個(gè)數(shù)為幣個(gè)數(shù)為differentCoins。 maxChange為要找的零錢(qián)數(shù)為要找的零錢(qián)數(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動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 硬幣找零問(wèn)題硬幣找零問(wèn)題 最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù)44最優(yōu)二叉查找樹(shù)最優(yōu)二叉查找樹(shù) 有一組詞有一組詞 w1,w2,wNw1,w2,wN，他們的出現(xiàn)概率分別，他們的出現(xiàn)概率分別為為p1,p2,pNp1,p2,pN。構(gòu)建一

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

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

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

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

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

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

29、根，第一個(gè)節(jié)點(diǎn)作為右子樹(shù)。計(jì)算將第二個(gè)節(jié)點(diǎn)作為根，第一個(gè)節(jié)點(diǎn)作為右子樹(shù)。計(jì)算代價(jià)。代價(jià)。 取代價(jià)小的樹(shù)作為最終的樹(shù)保存下來(lái)。取代價(jià)小的樹(shù)作為最終的樹(shù)保存下來(lái)。 生成由三個(gè)節(jié)點(diǎn)組成的樹(shù)，四個(gè)節(jié)點(diǎn)組成的樹(shù)生成由三個(gè)節(jié)點(diǎn)組成的樹(shù)，四個(gè)節(jié)點(diǎn)組成的樹(shù)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è)計(jì)技術(shù)算法設(shè)計(jì)技術(shù) 枚舉法枚舉法 貪婪法貪婪法 分而治之法分而治之法 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)

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

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

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

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

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

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

37、下角(1-15)(1-15)。數(shù)組數(shù)組c16c16，cA=truecA=true表示第表示第A A條左高右低斜線條左高右低斜線上沒(méi)有皇后。從左下角依次編到右上角上沒(méi)有皇后。從左下角依次編到右上角(1-15)(1-15)。59 void queen_a11(int k) /在在8x8棋盤(pán)的第棋盤(pán)的第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; /置對(duì)應(yīng)位置有皇后置對(duì)應(yīng)位置有皇后 if (k = 8) / 找到一個(gè)可行解找到一個(gè)可行解 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ù)對(duì)應(yīng)位置無(wú)皇后恢復(fù)對(duì)應(yīng)位置無(wú)皇后 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回溯法回溯法 八皇后問(wèn)題八皇后問(wèn)題 分書(shū)問(wèn)題分書(shū)問(wèn)題首先暫時(shí)放棄問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候首先暫時(shí)放棄問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)候選解不選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)候選解不可能是解時(shí)，就選擇下一候選解。如果當(dāng)前候選解可能是解時(shí)，就選擇下一候選解。如果當(dāng)前候選解除了不滿(mǎn)足規(guī)模要求外，滿(mǎn)足其他所有要求時(shí)，繼除了不滿(mǎn)足規(guī)模要求外，滿(mǎn)足其他所有要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。

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

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

42、方案數(shù)加1 1，輸出該方案。否則，輸出該方案。否則調(diào)用調(diào)用trytry（i+1)i+1)為第為第i+1i+1個(gè)人分書(shū)。個(gè)人分書(shū)?；厮?。讓第回溯。讓第i i個(gè)人退回書(shū)個(gè)人退回書(shū)j j，嘗試下一個(gè)，嘗試下一個(gè)j j，即尋找下一，即尋找下一個(gè)可行的方案?jìng)€(gè)可行的方案由于在每次由于在每次trytry中都要用到中都要用到likelike，taketake以及目前找以及目前找到的方案數(shù)到的方案數(shù)n n，因此可將它們作為全局變量，以免，因此可將它們作為全局變量，以免每次函數(shù)調(diào)用時(shí)都要帶一大串參數(shù)。每次函數(shù)調(diào)用時(shí)都要帶一大串參數(shù)。設(shè)計(jì)一個(gè)函數(shù)設(shè)計(jì)一個(gè)函數(shù)try(i)給第給第i個(gè)人分書(shū)。個(gè)人分書(shū)。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 書(shū)書(shū)t人人 endl; for (k=0; k5; k+) cout k t char(takek+A) endl; else trynext(i+1); takej = -1; 66truefalsefalsetruefalsefalsetruefalsefalsefalsetruefalsetruetruefalsetruefalsefal

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

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

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

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

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

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

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