算法設(shè)計(jì)與分析基礎(chǔ)課后習(xí)題答案中文版(編輯修改稿)
2025-07-21 22:15 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 如果沒(méi)有發(fā)生交換位置,那么: BetterBubblesort(A[0..n1])//用改進(jìn)的冒泡算法對(duì)數(shù)組A[0..n1]排序//輸入:數(shù)組A[0..n1]//輸出:升序排列的數(shù)組A[0..n1]count←n1 //進(jìn)行比較的相鄰元素對(duì)的數(shù)目flag←true //交換標(biāo)志while flag do flag←false for i=0 to count1 do if A[i+1]A[i] swap(A[i],A[i+1]) flag←true count←count1c最差情況是數(shù)組是嚴(yán)格遞減的,那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來(lái)的冒泡排序.?(穩(wěn)定)1. 對(duì)限位器版的順序查找算法的比較次數(shù):a. 在最差情況下b. (0=p=1)Hints:a. Cworst(n)=n+1b. 在成功查找下,對(duì)于任意的I,第一次匹配發(fā)生在第i個(gè)位置的可能性是p/n,比較次數(shù)是n+1,可能性是1p.,對(duì)于這樣的輸入需要做多少次字符比較運(yùn)算.Hints:文本:由n個(gè)0組成的文本模式:前m1個(gè)是0,最后一個(gè)字符是1比較次數(shù): m(nm+1),對(duì)于給定的模式,它能夠返回給定的文本中所有匹配子串的數(shù)量.Algorithms BFStringmatch(T[0..n1],P[0..m1])//蠻力字符匹配//輸入:數(shù)組T[0..n1]—長(zhǎng)度為n的文本,數(shù)組P[0..m1]—長(zhǎng)度為m的模式//輸出:在文本中匹配成功的子串?dāng)?shù)量count←0for i←0 to nm do j←0 while jm and P[j]=T[i+j] j←j+1 if j=m count←count+1return count,我們應(yīng)該如何修改該蠻力算法來(lái)利用這個(gè)信息.Hint:每次都從這些少見字符開始比較,如果匹配, 則向左邊和右邊進(jìn)行其它字符的比較. ,該算法求一個(gè)n個(gè)元素?cái)?shù)組中最大元素的位置.,該算法的輸出是怎樣的呢?.解:a.Algorithms MaxIndex(A[l..r]){Input:A portion of array A[0..n1] between indices l and r(l≤r)Output: The index of the largest element in A[l..r]if l=r return lelse temp1←MaxIndex(A[l..(l+r)/2])temp2←MaxIndex(A[(l+r)/2..r])if A[temp1]≥A[temp2] return temp1else return temp2}.: C(n)=C( n/2 )+C( n/2 )+1 for n1 C(1)=0 設(shè)n=2k，C(2k)=2C(2k1)+1 =2[2 C(2k2)+1]+1=22C(2k2)+2+1 =2[22C(2k3)+1]+2+1=23C(2k3)+ 22+2+1 =... =2iC(2ki)+ 2i1+2 i2 +...+2+1 =... =2kC(2kk)+ 2k1+2 k2 +...+2+1=2k－1=n1可以證明C(n)=n1對(duì)所有n1的情況都成立（n是偶數(shù)或奇數(shù)），但蠻力算法不用遞歸調(diào)用。該算法同時(shí)求出一個(gè)n元數(shù)組的最大元素和最小元素的值。解答： ，只需要將原數(shù)組一分為二，再使用相同的方法找出這兩個(gè)部分中的最大值和最小值，然后經(jīng)過(guò)比較就可以得到整個(gè)問(wèn)題的最大值和最小值。 算法 MaxMin(A[l..r],Max,Min) //該算法利用分治技術(shù)得到數(shù)組A中的最大值和最小值//輸入：數(shù)值數(shù)組A[l..r]//輸出：最大值Max和最小值Minif(r=l) Max←A[l]；Min←A[l]。 //只有一個(gè)元素時(shí)elseif r－l=1 //有兩個(gè)元素時(shí)if A[l]≤A[r]Max←A[r]。 Min←A[l] elseMax←A[l]。 Min←A[r] else //r－l1MaxMin(A[l,(l+r)/2],Max1,Min1)。 //遞歸解決前一部分MaxMin(A[(l+r/)2..r],Max2,Min2)。 //遞歸解決后一部分if Max1＜Max2 Max= Max2 //從兩部分的兩個(gè)最大值中選擇大值if Min2Min1 Min=Min2。 //從兩部分的兩個(gè)最小值中選擇小值}=2k,比較次數(shù)的遞推關(guān)系式:C(n)=2C(n/2)+2 for n2C(1)=0, C(2)=1C(n)=C(2k)=2C(2k1)+2=2[2C(2k2)+2]+2=22C(2k2)+22+2=22[2C(2k3)+2]+22+2=23C(2k3)+23+22+2...=2k1C(2)+2k1+2k2+...+2 //C(2)=1=2k1+2k1+2k2+...+2 //后面部分為等比數(shù)列求和=2k1+2k2 //2(k1)=n/2,2k=n=n/2+n2=3n/2－2： 算法 simpleMaxMin(A[l..r])//用蠻力法得到數(shù)組A的最大值和最小值//輸入：數(shù)值數(shù)組A[l..r]//輸出：最大值Max和最小值MinMax=Min=A[l]。for i=l+1 to r do if A[i]Max Max←A[i]。else if A[i]Min Min←A[i]return Max,Min}時(shí)間復(fù)雜度t(n)=2(n1)算法MaxMin的時(shí)間復(fù)雜度為3n/22，simpleMaxMin的時(shí)間復(fù)雜度為2n2，都屬于Θ(n)，但比較一下發(fā)現(xiàn)，MaxMin的速度要比simpleMaxMin的快一些。 ,X,A,M,P,L,E按字母順序排序.321.(for n=2k).(for n=2k),是否會(huì)影響它的效率類型呢?解:a. .b. 最好情況(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2 for n1 (n=2k)Cbest(1)=0c. 鍵值比較次數(shù)M(n)M(n)=2M(n)+2n for n1M(1)=0,X,A,M,P,L,E按字母順序排序4. 請(qǐng)舉一個(gè)n個(gè)元素?cái)?shù)組的例子,使得我們有必須對(duì)它使用本節(jié)提到的”限位器”.限位器的值應(yīng)是多少年來(lái)?為什么一個(gè)限位器就能滿足所有的輸入呢? Hints: With the pivot being the leftmost element, the lefttoright scan will get o
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1