中科大算法導(dǎo)論第一二次和第四次作業(yè)答案

1、中科大算法導(dǎo)論第一二次和第四次作業(yè)答案2.3-2改寫MERGE過程，使之不使用哨兵元素，而是在一旦數(shù)組L或R中的所有元素都被復(fù)制回?cái)?shù)組A后，就立即停止，再將另一個(gè)數(shù)組中余下的元素復(fù)制回?cái)?shù)組A中。MERGE(A,p,q,r)n1q-p+1n2 r-qcreate arrays L1.n1 and R1.n2for i 1 to n1 do Li Ap+i-1for j 1 to n2 do Rj Aq+ji 1j 1k pwhile(i=n1) and (j=n2) do if Li=Rj do Ak=Li i+ else do Ak=Rj j+ k+while(i=n1) do Ak+=Li+

2、while(j0時(shí)才進(jìn)行交換 交換flag=-flag2/)(rpq第四次作業(yè)int Partition(int A, int p, int r) int x = Ar,i=p-1; int flag = 1; for (int j = p;j=Ai&flag0)/x=Ai時(shí)，flag大于0和小于0的數(shù)量約為一半， swap(Ai,Aj); if (x =Ai) flag=-flag;/這樣就能讓i+次數(shù)減半。 swap(Ai + 1,Ar); return i + 1 7.2-3 證明：當(dāng)數(shù)組A包含不同的元素、且按降序排序時(shí)，QUICKSORT的運(yùn)行時(shí)間為(n2)。 證明：數(shù)組元素各

3、不相同，且按降序排列時(shí)，每次遞歸調(diào)用都會(huì)產(chǎn)生一個(gè)元素?cái)?shù)目為n-1的分塊和一個(gè)1的分塊。故有T(n)=T(n-1)+(n)有T(n)=T(n-1)+cn+d=T(n-2)+cn+c(n-1)+2d=T(n-3)+cn+c(n-1)+c(n-2)+3d=.=T(1)+cn+c(n-1)+c(n-2)+.+c(1)+nd=T(1)+cn(n+1)/2+nd=(n2)7.4-3 證明：在q=0,1,.n-1區(qū)間上，當(dāng)q=0或q=n-1時(shí),q2+(n-q-1)2取得最大值。求導(dǎo)，取極值?；蛘哌M(jìn)行變換在O(1)的時(shí)間內(nèi)，回答出輸入的整數(shù)中有多少個(gè)落在區(qū)間a.b內(nèi)。給出的算法的預(yù)處理時(shí)間為O(n+k)利用計(jì)

4、數(shù)排序，由于在計(jì)數(shù)排序中有一個(gè)存儲(chǔ)數(shù)值個(gè)數(shù)的臨時(shí)存儲(chǔ)區(qū)C0.k，利用這個(gè)數(shù)組即可a.b區(qū)間整數(shù)個(gè)數(shù)為Cb-Ca-1題目已經(jīng)提示運(yùn)用桶排序，主要是正確設(shè)置桶點(diǎn)均勻分布，則每個(gè)桶的尺寸應(yīng)相等，即每個(gè)桶在圓中所占據(jù)的面積相等。把圓分為n個(gè)部分，第一個(gè)部分是以原點(diǎn)為圓心的圓，其他部分是以原點(diǎn)為圓心的圓環(huán)。單位圓的面積是12=。那么我們選擇一系列的距離d0,d1,d2,.,dn滿足d0=0, *d12=/(n), *d22=2*/(n), *d32=3*/(n),.,*dn2=，得到，d0,d1,d2,.,dn=0,sqrt(1/n),sqrt(2/n),.,1這樣相當(dāng)于每個(gè)di到di+1所占的面積都是相同的，也即每個(gè)左邊點(diǎn)會(huì)均勻的落入這些區(qū)間中。所n個(gè)桶為d0,d1, d1,d2,.,dn-1,dn9.1-1證明：在最壞情況下，利用n+ceil(lgn)-2次比較，即可得到n個(gè)元素中的第2小元素。（提示：同時(shí)找最小元素） 先兩兩比較，較小的組成新的數(shù)組再兩兩比較，不斷如此，從而形成一個(gè)倒立的樹，終于找出最小的元素，由于最上一層是n/2次比較，這又能夠看做一個(gè)滿二叉樹，所以總的比較次數(shù)為n/2+n/2-1=n-1， 找出一個(gè)最小的元素須要n-1次比較，而n個(gè)元素中的第2小元素一定跟最小的元素比較