數(shù)據(jù)結(jié)構(gòu)-第五部分

數(shù)據(jù)結(jié)構(gòu)-第五部分朗讀前明確讀的要求：讀準(zhǔn)字音，讀出節(jié)奏；朗讀后同學(xué)間評(píng)價(jià)朗讀情況。三、學(xué)生自學(xué)，二讀課文１、一邊默讀課文，一邊運(yùn)用書下注釋解釋重點(diǎn)詞，并練習(xí)翻譯，看誰(shuí)做得最好。２、學(xué)生自學(xué)，教師巡視，了解學(xué)情。３、檢查自學(xué)效果：（請(qǐng)一位學(xué)生回答，其他同學(xué)認(rèn)真聽，如有錯(cuò)，請(qǐng)幫忙糾正）。（學(xué)生依次回答，如有錯(cuò)，請(qǐng)學(xué)生更正，學(xué)生不會(huì)，教師更正。）⑶學(xué)生快速對(duì)照相關(guān)譯文，自我檢查。四、字詞小結(jié)。隨堂練習(xí)（投影出示練習(xí)）數(shù)據(jù)結(jié)構(gòu)-第五部分?jǐn)?shù)據(jù)結(jié)構(gòu)-第五部分朗讀前明確讀的要求：讀準(zhǔn)字音，讀出節(jié)奏；朗讀后同學(xué)間評(píng)價(jià)朗讀情況。三、學(xué)生自學(xué)，二讀課文１、一邊默讀課文，一邊運(yùn)用書下注釋解釋重點(diǎn)詞，并練習(xí)翻譯，看誰(shuí)做得最好。２、學(xué)生自學(xué)，教師巡視，了解學(xué)情。３、檢查自學(xué)效果：（請(qǐng)一位學(xué)生回答，其他同學(xué)認(rèn)真聽，如有錯(cuò)，請(qǐng)幫忙糾正）。（學(xué)生依次回答，如有錯(cuò)，請(qǐng)學(xué)生更正，學(xué)生不會(huì)，教師更正。）⑶學(xué)生快速對(duì)照相關(guān)譯文，自我檢查。四、字詞小結(jié)。隨堂練習(xí)（投影出示練習(xí)）枚舉法枚舉法適合于解的候選者是有限、可枚舉的場(chǎng)合。枚舉法就是對(duì)可能是解的眾多候選者按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，從中找出符合要求的候選解作為問(wèn)題的解?；诿杜e法的算法一般都比較直觀，容易理解。但由于要檢查所有的候選解，因此時(shí)間性能較差2數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第2頁(yè)。3枚舉法實(shí)例用50元錢買了三種水果：西瓜、蘋果和桔子。各種水果加起來(lái)一共100個(gè)。假如，西瓜5元一個(gè)，蘋果1元一個(gè)，桔子1元3個(gè)，設(shè)計(jì)一算法輸出每種水果各買了幾個(gè)。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第3頁(yè)。4約束條件三種水果一共100個(gè)；買三種水果一共花了50元。如果西瓜有mellon個(gè)，蘋果有apple個(gè)，桔子有orange個(gè)，那么：

mellon+apple+orange等于1005*mellon+1*apple+orange/3等于50。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第4頁(yè)。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/3等于50）輸出此方案；列出所有的情況，檢查是否滿足兩個(gè)約束條件數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第5頁(yè)。6改進(jìn)的方案intmain(){intmellon,apple,orange;for(mellon=1;mellon<10;++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<<''; cout<<"orange:"<<orange<<endl; }}return0;}按一個(gè)約束條件列出所有可行的情況，然后對(duì)每個(gè)可能解檢查它是否滿足第二個(gè)約束條件。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第6頁(yè)。7執(zhí)行結(jié)果Mellon：1apple：18orange：81Mellon：2apple：11orange：87Mellon：3apple：4orange：93數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第7頁(yè)。8第15章算法設(shè)計(jì)技術(shù)枚舉法貪婪法分而治之法動(dòng)態(tài)規(guī)劃回溯法隨機(jī)算法介紹通用的算法設(shè)計(jì)模式數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第8頁(yè)。9貪婪法貪婪法適合于分階段完成的工作。在每一階段都選擇當(dāng)前最好的答案，而不管將來(lái)如何。Dijkstra算法，prim算法和Kruskal算法都是貪婪算法貪婪法不一定能得到最優(yōu)解，但是一個(gè)可行的、較好的解。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第9頁(yè)。10最少背包問(wèn)題假設(shè)有許多盒子，每個(gè)盒子能保存的總重量為1.0。有N個(gè)項(xiàng)i1,i2,…,iN，它們的重量分別是w1,w2,…,wN。目的是用盡可能少的盒子放入所有的項(xiàng)，任何盒子的重量不能超過(guò)他的容量。例如，如果項(xiàng)的重量為0.4,0.4,0.6和0.6，最佳的方案是用兩個(gè)盒子。但要得到最佳方案，必須嘗試所有種組合情況。當(dāng)n很大時(shí)，這是不可能的。一種解決方案使用貪婪法數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第10頁(yè)。11解決策略按給定的次序掃描每一個(gè)項(xiàng)，把每一個(gè)項(xiàng)放入能夠容納他而不至于溢出的最滿的盒子。如果項(xiàng)的重量為0.4,0.4,0.6和0.6，貪婪法的方案是用三個(gè)盒子。其裝載的重量分別為0.8,0.6,0.6數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第11頁(yè)。12第15章算法設(shè)計(jì)技術(shù)枚舉法貪婪法分而治之法動(dòng)態(tài)規(guī)劃回溯法隨機(jī)算法介紹通用的算法設(shè)計(jì)模式數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第12頁(yè)。13分而治之法分而治之法的思想分：遞歸解決若干個(gè)較小的問(wèn)題治：從子問(wèn)題的答案中形成原始問(wèn)題的解分治法的的算法至少有兩個(gè)遞歸調(diào)用已見(jiàn)過(guò)的分治法算法：快速排序，樹的遍歷數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第13頁(yè)。14分治法實(shí)例最長(zhǎng)連續(xù)子序列問(wèn)題最近點(diǎn)問(wèn)題數(shù)學(xué)計(jì)算問(wèn)題數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第14頁(yè)。15最長(zhǎng)連續(xù)子序列問(wèn)題假設(shè)輸入是{4，－3，5，－2，－1，2，6，－2}。我們把這個(gè)輸入劃分成兩部分，前四個(gè)和后四個(gè)。這樣最大連續(xù)子序列的和可能出現(xiàn)在下面三種情況中。情況1：整個(gè)位于前半部，可遞歸計(jì)算。情況2：整個(gè)位于后半部，可遞歸計(jì)算。情況3：從前半部開始但在后半部結(jié)束。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第15頁(yè)。16情況3的解決方法從兩半部分的邊界開始，通過(guò)從右到左的掃描來(lái)找到左半段的最長(zhǎng)序列。類似地，從左到右的掃描找到右半段的最長(zhǎng)序列。把這兩個(gè)子序列組合起來(lái)，形成跨越分割邊界的最大連續(xù)子序列。在這個(gè)實(shí)例中，結(jié)果序列是從第一部分的第一個(gè)元素到第二部分的其余元素?？偤褪莾蓚€(gè)子序列的和，即4+7=11.數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第16頁(yè)。17算法總結(jié)遞歸地計(jì)算整個(gè)位于前半部的最大連續(xù)子序列。遞歸地計(jì)算整個(gè)位于后半部的最大連續(xù)子序列。通過(guò)兩個(gè)連續(xù)循環(huán)，計(jì)算從前半部開始但在后半部結(jié)束的最大連續(xù)子序列的和。選擇三個(gè)和中的最大值。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第17頁(yè)。18IntmaxSum(inta[],intleft,intright){intmaxLeft,maxRight,center;intleftSum=0,rightSum=0;intmaxLeftTmp=NEGMAX,maxRightTmp=NEGMAX;center=(left+right)/2;if(left==right)returna[left]>0?a[left]:0;maxLeft=maxSum(a,left,center);maxRight=maxSum(a,center+1,right);數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第18頁(yè)。19for(inti=center;i>=left;--i){leftSum+=a[i];if(leftSum>maxLeftTmp)maxLeftTmp=leftSum;}for(inti=center+1;i<=right;++i){rightSum+=a[i];if(rightSum>maxRightTmp)maxRightTmp=rightSum;}returnmax3(maxLeft,maxRight,maxLeftTmp+maxRightTmp);}數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第19頁(yè)。20分治法實(shí)例最長(zhǎng)連續(xù)子序列問(wèn)題最近點(diǎn)問(wèn)題數(shù)學(xué)計(jì)算問(wèn)題數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第20頁(yè)。21最近點(diǎn)問(wèn)題在二維平面上有N個(gè)點(diǎn)，試找出距離最短的兩個(gè)點(diǎn)。蠻力算法：計(jì)算兩兩之間的距離，從中找出最小的一個(gè)。N個(gè)點(diǎn)有N（N-1）/2對(duì)距離，因此時(shí)間復(fù)雜度為O(N2)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第21頁(yè)。22分治法解法將所有的點(diǎn)按x值排序。取一個(gè)合適的x值，把所有點(diǎn)分成兩半PL和PR。距離最近的兩個(gè)點(diǎn)可能出現(xiàn)在PL中(dL)，也可能出現(xiàn)在PR(dR)中，也可能一個(gè)點(diǎn)在PL，一個(gè)點(diǎn)在PR(dC)dL和dR可用遞歸得到dC的計(jì)算：設(shè)δ=min(dL,dR)如果dC比δ大，則沒(méi)必要計(jì)算。因此用于計(jì)算dC的點(diǎn)必須落在分界線±δ的范圍內(nèi)，計(jì)算此范圍中點(diǎn)對(duì)的距離中的最小值數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第22頁(yè)。23dLdRdCδδ數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第23頁(yè)。24優(yōu)化在最壞的情況下，所有的點(diǎn)都落在分界線δ以內(nèi)。但此時(shí)不一定要計(jì)算所有點(diǎn)對(duì)的距離。只要兩點(diǎn)的y坐標(biāo)大于δ，這兩點(diǎn)之間的距離也不用算了。假設(shè)該區(qū)間中的點(diǎn)按y坐標(biāo)排序，則可得下列算法數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第24頁(yè)。25for(i=0;i<n;++i)if(pj+1的y-pj的y>=δ)break;elseif(dist(pj,pj+1)<δ)δ=dist(pj,pj+1);數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第25頁(yè)。26分治法實(shí)例最長(zhǎng)連續(xù)子序列問(wèn)題最近點(diǎn)問(wèn)題數(shù)學(xué)計(jì)算問(wèn)題數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第26頁(yè)。27數(shù)學(xué)計(jì)算問(wèn)題設(shè)X和Y是兩個(gè)N位的整數(shù)，假如一位乘法花費(fèi)一個(gè)單位時(shí)間，那么計(jì)算X*Y的時(shí)間復(fù)雜性為O(N2)分治法計(jì)算將X和Y均分成兩半，分別稱為XL，XR，YL，YR。則X=XL10N/2+XR，Y=YL10N/2+YR。那么，XY=XLYL10N+(XLYR+XRYL)10N/2+XRYR時(shí)間復(fù)雜度：T(N)=4T(N/2)+O(N)=O(N2)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第27頁(yè)。28進(jìn)一步改進(jìn)上述算法的問(wèn)題是需要太多次（4次）的遞歸調(diào)用。如果能減少遞歸調(diào)用，則能提高時(shí)間性能注意：XLYR+XRYL=(XL–XR)(YR–YL)+XLYL+XRYR

代入前式，XY=XLYL10N+(XLYR+XRYL)10N/2+XRYR=XLYL10N+((XL–XR)(YR–YL)+XLYL+XRYR)10N/2+XRYR

可見(jiàn)只需3次遞歸調(diào)用時(shí)間復(fù)雜性：數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第28頁(yè)。29第15章算法設(shè)計(jì)技術(shù)枚舉法貪婪法分而治之法動(dòng)態(tài)規(guī)劃回溯法隨機(jī)算法介紹通用的算法設(shè)計(jì)模式數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第29頁(yè)。30動(dòng)態(tài)規(guī)劃用表代替遞歸例：斐波那契函數(shù)f(n)=f(n-1)+f(n-2)。計(jì)算f(n)需要計(jì)算f(n-1)和f(n-2)。當(dāng)計(jì)算f(n-1)時(shí)要計(jì)算f(n-2)和f(n-3)。因此在計(jì)算f(n)中f(n-2)被計(jì)算了兩次。為了減少重復(fù)的遞歸調(diào)用，我們可以反過(guò)來(lái)計(jì)算。先計(jì)算f(2)，有了f(2)再計(jì)算f(3)，以此類推，計(jì)算到f(n)。在此過(guò)程中不需要任何遞歸數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第30頁(yè)。31動(dòng)態(tài)規(guī)劃硬幣找零問(wèn)題最優(yōu)二叉查找樹數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第31頁(yè)。32找零問(wèn)題對(duì)于一種貨幣，有面值為C1,C2,…,CN(分)的硬幣，最少需要多少個(gè)硬幣來(lái)找出K分錢的零錢。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第32頁(yè)。33貪婪法解法我們不斷使用可能的最大面值的硬幣如：美元的硬幣有1、5、10和25分的面值(忽略流通頻率很低的50分硬幣)。我們可以通過(guò)使用2個(gè)25分、一個(gè)10分的硬幣以及三個(gè)1分來(lái)找出63分錢，一共是6個(gè)硬幣。如果美元中包含一個(gè)21分硬幣時(shí)，貪心算法仍然給出一個(gè)用六個(gè)硬幣的解，但是最佳的解是用三個(gè)硬幣(三個(gè)都是21分的硬幣。)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第33頁(yè)。34解法1－－分治法如果我們可以用一個(gè)硬幣找零，這就是最小的。否則，對(duì)于每個(gè)可能的值i，我們可以獨(dú)立計(jì)算找i分錢零錢和K-i分錢需要的最小硬幣數(shù)。然后選擇這個(gè)和最小的i。

數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第34頁(yè)。35怎樣找出63分錢零錢找出1分錢零錢和62分錢零錢分別需要的硬幣數(shù)是1和4。因此，63分錢需要使用五個(gè)硬幣。找出2分錢和61分錢分別需要2和4個(gè)硬幣，一共是六個(gè)硬幣。我們繼續(xù)嘗試所有的可能性。我們看到一個(gè)21分和42分的分解，它可以分別用一個(gè)和兩個(gè)硬幣來(lái)找開，因此，這個(gè)找零問(wèn)題就可以用三個(gè)硬幣解決。我們需要嘗試的最后一種分解是31分和32分。我們可以用兩個(gè)硬幣找出31分零錢，用三個(gè)硬幣找出32分零錢，一共是五個(gè)硬幣。因此最小值是三個(gè)硬幣。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第35頁(yè)。36intcoin(intk){inti,tmp,intcoinNum=k;

if（能用一個(gè)硬幣找零）return1;for(i=1;i<k;++i)if((tmp=coin(i)+coin(k-i))<coinNum)

coinNum=tmp;returncoinNum;}數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第36頁(yè)。37上述解法分析此算法的效率很低事實(shí)上63分錢找零的問(wèn)題是不會(huì)在一個(gè)合理的時(shí)間內(nèi)解決的。就如Finbonacci函數(shù)一樣數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第37頁(yè)。38解法2通過(guò)指定其中的一個(gè)硬幣來(lái)遞歸地簡(jiǎn)化問(wèn)題。例如，對(duì)于63分錢，我們可以給出以下找零的辦法。一個(gè)1分的硬幣加上遞歸地分派62分錢一個(gè)5分的硬幣加上遞歸地分派58分錢一個(gè)10分的硬幣加上遞歸地分派53分錢一個(gè)21分的硬幣加上遞歸地分派42分錢一個(gè)25分的硬幣加上遞歸地分派38分錢該算法的問(wèn)題仍然是效率問(wèn)題數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第38頁(yè)。39動(dòng)態(tài)規(guī)劃解效率低下主要是由于重復(fù)計(jì)算造成的。因此，可把已有子問(wèn)題的答案存放起來(lái)，當(dāng)再次遇到此子問(wèn)題時(shí)就不用重復(fù)計(jì)算了。在本例中，我們用coinsUsed[i]代表了找i分零錢所需的最小硬幣數(shù)。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第39頁(yè)。40算法思想先找出一分錢的找零方法，把最小硬幣數(shù)存入coinUsed[1]依次找出2分錢、3分錢…的找零方法，知道到達(dá)要找零的錢為止：對(duì)每個(gè)要找的零錢i，可以把i分解成某個(gè)coins[j]和i-coins[j]，所需硬幣數(shù)為coinUsed[i-coins[j]]+1。對(duì)所有的j，取最小的coinUsed[i-coins[j]]+1作為i元錢找零的的答案。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第40頁(yè)。41函數(shù)原型Voidmakechange(intcoins[],intdifferentCoins,intmaxChange,intcoinUsed[])Coins存放所有不同的硬幣值，不同的硬幣個(gè)數(shù)為differentCoins。maxChange為要找的零錢數(shù)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第41頁(yè)。42voidmakechange(intcoins[],intdifferentCoins,intmaxChange,intcoinUsed[]){coinUsed[0]=0;for(intcents=1;cents<=maxChange;cents++){intminCoins=cents;for(intj=1;j<differentCoins;j++){if(coins[j]>cents)continue;if(coinUsed[cents-coins[j]]+1<minCoins)minCoins=coinUsed[cents-coins[j]]+1;}coinUsed[cents]=minCoins;}}

數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第42頁(yè)。43動(dòng)態(tài)規(guī)劃硬幣找零問(wèn)題最優(yōu)二叉查找樹數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第43頁(yè)。44最優(yōu)二叉查找樹有一組詞w1,w2,…,wN，他們的出現(xiàn)概率分別為p1,p2,…pN。構(gòu)建一棵二叉排序樹使得訪問(wèn)時(shí)間的期望值最小。即如果wi所在的層次是di，那么該問(wèn)題類似于哈夫曼樹，概率大的靠近根，概率小的遠(yuǎn)離根。但它比哈夫曼樹更復(fù)雜。因?yàn)樗€要滿足二叉排序樹的特性數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第44頁(yè)。45貪婪法的解法選擇出現(xiàn)概率最大的詞作為樹根，把剩余的詞分成兩組：小于根的和大于根的。遞歸構(gòu)建左子樹和右子樹。A0.22Am0.18And0.20Egg0.05If0.25The0.02two0.08iftwotheaandamegg顯然不是最優(yōu)的，代價(jià)為：2.43數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第45頁(yè)。46最優(yōu)解法假如要對(duì)wleft到wright構(gòu)建一棵最優(yōu)二叉排序樹，那么這棵樹的形式一定是根為wi，左子樹的節(jié)點(diǎn)為left到i-1，右子樹的節(jié)點(diǎn)為i+1到right，左子樹和右子樹也是最優(yōu)的設(shè)Cleft，right是樹的代價(jià)，那么數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第46頁(yè)。47最優(yōu)解法對(duì)a,am.and,egg,if,the,two對(duì)所有的可能的情況計(jì)算它的代價(jià)，從中找出最小的：根為a，左子樹為空，右子樹為am，…，two。根為am，左子樹為a，右子樹為and,…，two。根為and，左子樹為a，am,右子樹為egg,…，two。根為egg，左子樹為a,am,and,右子樹為if,…，two。…在上述每一種情況中，我們需要繼續(xù)遞歸。如：在嘗試根為egg，左子樹為a,am,and,右子樹為if,…，two的情況時(shí)，要找出最優(yōu)的左子樹，我們又要嘗試根節(jié)點(diǎn)為a，左子樹為空，右子樹為am和and根節(jié)點(diǎn)為am，左子樹為a，右子樹為and根節(jié)點(diǎn)為and，左子樹為a和am，右子樹為空。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第47頁(yè)。48動(dòng)態(tài)規(guī)劃解法從上述分析可以看出，在找出由a到two組成的最優(yōu)樹時(shí)，由a組成的樹，由a和am組成的樹，由am和and組成的樹，…，會(huì)分別被計(jì)算很多次。解決方法：從小到大計(jì)算由n個(gè)節(jié)點(diǎn)組成的最優(yōu)樹，并把它保存在一個(gè)表中。當(dāng)所有的節(jié)點(diǎn)形成了一棵樹時(shí)，任務(wù)就完成了。每棵樹的保存用兩個(gè)信息：根和代價(jià)。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第48頁(yè)。49生成過(guò)程先生成由一個(gè)節(jié)點(diǎn)組成的樹。樹的代價(jià)就是節(jié)點(diǎn)的權(quán)值。保存這些樹和相應(yīng)的代價(jià)。生成所有由兩個(gè)節(jié)點(diǎn)組成的樹：將第一個(gè)節(jié)點(diǎn)作為根，第二個(gè)節(jié)點(diǎn)作為右子樹。計(jì)算代價(jià)。將第二個(gè)節(jié)點(diǎn)作為根，第一個(gè)節(jié)點(diǎn)作為右子樹。計(jì)算代價(jià)。取代價(jià)小的樹作為最終的樹保存下來(lái)。生成由三個(gè)節(jié)點(diǎn)組成的樹，四個(gè)節(jié)點(diǎn)組成的樹…數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第49頁(yè)。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..ifif0.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=7andaamifeggtwothe數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第50頁(yè)。51第15章算法設(shè)計(jì)技術(shù)枚舉法貪婪法分而治之法動(dòng)態(tài)規(guī)劃回溯法隨機(jī)算法介紹通用的算法設(shè)計(jì)模式數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第51頁(yè)。52第15章算法設(shè)計(jì)技術(shù)枚舉法貪婪法分而治之法動(dòng)態(tài)規(guī)劃回溯法隨機(jī)算法介紹通用的算法設(shè)計(jì)模式數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第52頁(yè)。53回溯法八皇后問(wèn)題分書問(wèn)題首先暫時(shí)放棄問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)候選解不可能是解時(shí)，就選擇下一候選解。如果當(dāng)前候選解除了不滿足規(guī)模要求外，滿足其他所有要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前的候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第53頁(yè)。54八皇后問(wèn)題在一個(gè)8*8的棋盤上放8個(gè)皇后，使8個(gè)皇后中沒(méi)有兩個(gè)以上的皇后會(huì)在同一行、同一列或同一對(duì)角線上數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第54頁(yè)。55八皇后問(wèn)題的求解過(guò)程求解過(guò)程從空配置開始，在第一列到第m列為合理配置的基礎(chǔ)上再配置m+1列，直到第n列的配置也時(shí)合理時(shí)，就找到了一個(gè)解。另外在一列上也有n種配置。開始時(shí)配置在第一行，以后改變時(shí)，順序選擇第二行、第三行、。。、第n行。當(dāng)配置到第n行時(shí)還找不到一個(gè)合理的配置時(shí)，就要回朔，去改變前一列的配置。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第55頁(yè)。56算法{m=0;/*從空配置開始*/good=true;/*配置中的皇后不沖突*/do{if(good)if(m==8){輸出解；重新尋找下一可行的解；

}else向前試探，擴(kuò)展至下一列；

else回朔，形成下一候選解；

good=檢查當(dāng)前候選解的合理性；

}while(m!=0);}數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第56頁(yè)。57棋盤的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)比較直觀的方法是采用一個(gè)二維數(shù)組，但仔細(xì)考察，就會(huì)發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性會(huì)帶來(lái)困難。對(duì)于本題來(lái)說(shuō)，我們關(guān)心的并不是皇后的具體位置，而是“一個(gè)皇后是否已經(jīng)在某行和某條斜線合理地安置好了”。因?yàn)樵诿恳涣猩锨『梅乓粋€(gè)皇后，所以引入一個(gè)一維數(shù)組(設(shè)為col（9）)，值col[j]表示在棋盤第j列上的皇后位置。如col[3]的值為4，就表示第三列的皇后在第四行。另外，為了使程序在找完了全部解后回溯到最初位置，設(shè)定col[0]的初值為0。當(dāng)回溯到第0列時(shí)，說(shuō)明程序已求得全部解(或無(wú)解)，結(jié)束程序執(zhí)行。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第57頁(yè)。58候選解的合理性檢查引入以下三個(gè)工作數(shù)組數(shù)組a[9]，a[A]=true表示第A行上還沒(méi)有皇后；數(shù)組b[16]，b[A]=true表示第A條右高左低斜線上沒(méi)有皇后；從左上角依次編到右下角(1-15)。數(shù)組c[16]，c[A]=true表示第A條左高右低斜線上沒(méi)有皇后。從左下角依次編到右上角(1-15)。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第58頁(yè)。59

voidqueen_a11(intk)//在8x8棋盤的第k列上找合理的配置{inti,j;charawn;for(i=1;i<=9;i++)//依次在l至8行上配置k列的皇后if(a[i]&&b[k+i-1]&&c[8+k-i])//可行位置{col[k]=i;a[i]=b[k+i-1]=c[8+k-i]=false;//置對(duì)應(yīng)位置有皇后if(k==8)//找到一個(gè)可行解{for(j=1;j<=8;j++)cout<<j<<col[j]<<'\t'; cout<<endl;cin>>awn;if(awn=='Q'||awn=='q')exit(0);}elsequeen_a11(k+1);//遞歸至第k十1列a[i]=b[k+i-1]=c[8+k-i]=true;//恢復(fù)對(duì)應(yīng)位置無(wú)皇后

}}

數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第59頁(yè)。60主程序intcol[9];boola[9],b[17],c[17];intmain(){intj;for(j=0;j<=8;j++)a[j]=true;for(j=0;j<=16;j++)b[j]=c[j]=true;queen_a11(1);return0;}數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第60頁(yè)。61回溯法八皇后問(wèn)題分書問(wèn)題首先暫時(shí)放棄問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)候選解不可能是解時(shí)，就選擇下一候選解。如果當(dāng)前候選解除了不滿足規(guī)模要求外，滿足其他所有要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前的候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第61頁(yè)。62分書問(wèn)題有編號(hào)為0，1，2，3，4的5本書，準(zhǔn)備分給5個(gè)人A，B，C，D，E，每個(gè)人的閱讀興趣用一個(gè)二維數(shù)組描述：

Like[i][j]=truei喜歡書jLike[i][j]=falsei不喜歡書j

寫一個(gè)程序，輸出所有皆大歡喜的分書方案0011011001011010001001001數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第62頁(yè)。63存儲(chǔ)設(shè)計(jì)用一個(gè)二維數(shù)組like存儲(chǔ)用戶的興趣用一個(gè)一維的整型數(shù)組take表示某本書分給了某人。Take[j]=i表示第j本書給了第i個(gè)人。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第63頁(yè)。64解題思路依次嘗試把書j分給人i。如果第i個(gè)人不喜歡第j本書，則嘗試下一本書，如果喜歡，并且第j本書尚未分配，則把書j分配給i。如果i是最后一個(gè)人，則方案數(shù)加1，輸出該方案。否則調(diào)用try（i+1)為第i+1個(gè)人分書。回溯。讓第i個(gè)人退回書j，嘗試下一個(gè)j，即尋找下一個(gè)可行的方案由于在每次try中都要用到like，take以及目前找到的方案數(shù)n，因此可將它們作為全局變量，以免每次函數(shù)調(diào)用時(shí)都要帶一大串參數(shù)。設(shè)計(jì)一個(gè)函數(shù)try(i)給第i個(gè)人分書。數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第64頁(yè)。65voidtrynext(inti){intj,k;for(j=0;j<5;++j){if(like[i][j]&&take[j]==-1){ take[j]=i;if(i==4){ n++;cout<<"\n第"<<n<<"種方案:"<<endl; cout<<"書\t人"<<endl;for(k=0;k<5;k++)cout<<k<<'\t'<<char(take[k]+'A')<<endl;}elsetrynext(i+1);take[j]=-1; }}}數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第65頁(yè)。66當(dāng)like矩陣的值為調(diào)用trynext(0);的結(jié)果為：第1種方案：書人0B1C2A3D4E第2種方案：書人0B1E2A3D4C數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第66頁(yè)。67第14章算法設(shè)計(jì)技術(shù)枚舉法貪婪法分而治之法動(dòng)態(tài)規(guī)劃回溯法隨機(jī)算法介紹通用的算法設(shè)計(jì)模式數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第67頁(yè)。68隨機(jī)算法在算法中，至少有一個(gè)地方使用隨機(jī)數(shù)作決策。隨機(jī)算法的時(shí)間復(fù)雜度取決于選擇的隨機(jī)數(shù)隨機(jī)算法的時(shí)間復(fù)雜度用期望的運(yùn)行時(shí)間來(lái)表示。一般假設(shè)隨機(jī)數(shù)的選擇是均勻分布的例如，在快速排序中將中間點(diǎn)用隨機(jī)數(shù)來(lái)選擇，則快速排序成為一個(gè)隨機(jī)算法。可以證明，期望的時(shí)間復(fù)雜度為O(NlogN)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第68頁(yè)。69隨機(jī)算法實(shí)例跳表素?cái)?shù)檢測(cè)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第69頁(yè)。70跳表以O(shè)(logN)的期望的時(shí)間復(fù)雜性支持插入和刪除的數(shù)據(jù)結(jié)構(gòu)跳表的概念：支持動(dòng)態(tài)查找必須用鏈表，但鏈表查找的時(shí)間為N?？梢杂迷黾渔湹姆绞教岣卟檎倚试黾右粭l鏈，讓頭節(jié)點(diǎn)指向第二個(gè)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)指向第四個(gè)節(jié)點(diǎn)，第四個(gè)節(jié)點(diǎn)指向第六個(gè)節(jié)點(diǎn)，…。查找時(shí)間為再增加一條鏈，讓頭節(jié)點(diǎn)指向第四個(gè)節(jié)點(diǎn)，第四個(gè)節(jié)點(diǎn)指向第八個(gè)節(jié)點(diǎn)，第八個(gè)節(jié)點(diǎn)指向第十二個(gè)節(jié)點(diǎn)，…。查找時(shí)間為推而廣之，對(duì)于2i<N≤2i+1個(gè)節(jié)點(diǎn)，設(shè)置i條鏈，第j條鏈指向其后的第2j個(gè)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第70頁(yè)。71821011131920222325821013192023251122821013192023251122數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第71頁(yè)。72查找過(guò)程（節(jié)點(diǎn)x）首先查找第i條鏈，如下一節(jié)點(diǎn)比x大，則查找第i-1條鏈，否則繼續(xù)查找第i條鏈。依次執(zhí)行，直到找到或找不到x最壞情況下的時(shí)間性能：數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第72頁(yè)。73插入過(guò)程當(dāng)插入一節(jié)點(diǎn)時(shí)，所有的節(jié)點(diǎn)都要變化。為了避免這個(gè)變化，插入采用隨機(jī)算法定義：有k條鏈的節(jié)點(diǎn)稱為level-k節(jié)點(diǎn)在跳表中，level-i的節(jié)點(diǎn)有N/2i個(gè)，即level-i的節(jié)點(diǎn)出現(xiàn)的概率為1/2i。插入過(guò)程：查找到插入點(diǎn)生成一個(gè)新節(jié)點(diǎn)按概率生成節(jié)點(diǎn)的level插入該節(jié)點(diǎn)因此跳表并不一定是嚴(yán)格的隔2i個(gè)節(jié)點(diǎn)有一條第i層的鏈，而只是從概率上講符合此分布數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第73頁(yè)。74隨機(jī)算法實(shí)例跳表素?cái)?shù)檢測(cè)數(shù)據(jù)結(jié)構(gòu)-第五部分全文共83頁(yè)，當(dāng)前為第74頁(yè)。75素?cái)?shù)檢測(cè)方法一：依次檢測(cè)1到N能否被N整除，如果能被整除的數(shù)的個(gè)數(shù)等于2，則N是素?cái)?shù)。時(shí)間復(fù)雜度為O（N）方法二：依次檢測(cè)2、3、5、7到sqrt(N)，只要有一個(gè)能整除N，則N為非素?cái)?shù)。最壞情況的時(shí)間復(fù)雜度O(N1/2)上述兩方法對(duì)小素?cái)?shù)適合，大素?cái)?shù)不適合方法三：隨機(jī)算法。該算