【正文】 for (int i=0。 for (int i=1。 for (int i=0。解答：要使平均讀取時(shí)間最小，則應(yīng)按照長(zhǎng)度的非遞減次序存放。W[4]=1095=4,則x[4]=4/10。 W[5]=4202=18則x[5]=1。2. 當(dāng)一個(gè)問題的最優(yōu)解算法的復(fù)雜度很高時(shí)，如果利用某種辦法產(chǎn)生的算法能很快地得到較好的解（或稱為次優(yōu)解、滿意解），可能就相當(dāng)滿意了。 if (temp 0) double temp = ((Point*)p)y ((Point*)q)y。 1。 else return 0。 while (i = m) { j = t。 { c[j].y c[i].y dm。 for (i = p。 if (b[i].index = m) i = q。 } return x3。 if (q p == 1) return 0。 scanf(%d, amp。 printf(%.2lf\n, d)。 d = closest(a, b, c, 0, n 1)。 qsort(b, n, sizeof(b[0]), cmp_y)。 memcpy(b, a, n *sizeof(a[0]))。 a[i].index = i。 i n。 for (i = 0。int merge(Point *, Point *, int, int, int)。double closest(Point *, Point *, Point *, int, int)。const double eps = 。其中，是1的n次主根。③ FFT(1, Pe(x),8,B) B[0]=p3。 B[0+1]= B[0] W[0] * C[0]= p1 p5。③ FFT(1, Pe(x),8,B) B[0]= p1。 Pe(x)=p1+ p5 x。 C[0+1]= B[0] W[0] * C[0]= p2p6。③ FFT(1, Pe(x),8,B) B[0]=p2。 B[0+1]= B[0] W[0] * C[0]= p0 p4。③ FFT(1, Pe(x),8,B) B[0]= p0。 Pe(x)=p0+ p4 x。 解答：=cos(2π/n)+sin(2π/n)= cos(2π/8)+ isin(2π/8)= 21/2(1+i)，則有：開始：FFT(8, P(x),A)N1=4。類似地，對(duì)44矩陣設(shè)計(jì)一種48次乘法的算法。10. Strassen算法的另一種形式是用下面的恒等式計(jì)算兩個(gè)2x2矩陣的乘積，如此處理共用了7次乘法和15次加法。為了求出兩個(gè)n矩陣的積，可以把一個(gè)n矩陣分成m m 個(gè)2k2k的子矩陣。 M9=Mult(AD,HG,n/4)。 M5=Mult(AD,HE,n/4)。 Else {A=X的最左邊n/4位； B=X的次左邊n/4位； C=X的次右邊n/4位； D=X的最右邊n/4位； E=Y的最左邊n/4位 F=Y的次左邊n/4位； G=Y的次右邊n/4位； H=Y的最右邊n/4位； M1=Mult(A,E,n/4)。Int Mult(X, Y, n){ s=sign(X)*sign(Y)。假定n是4的冪。 M4=Mult(B,E,n/3)。 If (n==1) Return X*Y。輸出：整數(shù)的乘積。解答：（1）三段。解析：m1＝(i1＋j1)／2＝3，m2 = (i2＋j2)／2＝3。解析：m1＝(i1＋j1)／2＝3，m2 = (i2＋j2)／2＝3。由算法中m1和m2的選取策略可知，在遞歸調(diào)用時(shí)，數(shù)組A和B的大小都減少了一半。當(dāng)A［m1］＞B［m2］時(shí)，設(shè)median2是A［i1：m1］和B［i2：j2］的中位數(shù)，類似地有median＝median2。由于j1—i1＝j(luò)2—i2，故(j1一i1)／2＋(j2一i2)／2＝j(luò)1一i1＝j(luò)2一i2。找出這兩個(gè)子數(shù)組中2(j1i1＋1)個(gè)數(shù)的中位數(shù)。5. 求有序數(shù)組A和B的中位數(shù)設(shè)A［0∶n1］和B［0∶n1］為兩個(gè)數(shù)組，每個(gè)數(shù)組中含有n個(gè)已排好序的數(shù)。A}：T={20，13，50，0，24，3，5}。因此，本算法在最壞情況下，時(shí)間復(fù)雜度為O（n）。A}；（3）找出T的第k小元素b；（4）根據(jù)b找出所要的解{ |a mid|≤b，a206。所以，中位數(shù)是指數(shù)組中能將數(shù)組劃分成兩個(gè)大小基本相同的兩個(gè)子數(shù)組的那個(gè)元素，即中位數(shù)是第 233。 SubMax4= Max(SubMax1, SubMax2) (Max,SubMax) (Max(Max1, Max2),SubMax(SubMax3, SubMax4)) } }時(shí)間分析：T(n)為算法的最壞時(shí)間。void Find(A)//遞歸算法{ if(|A|==2) { 設(shè)A={a,b} (Max,SubMax) (Max(a,b),SubMax(a,b))。 if (XA[j]) { k = i +1。 While (k=m) { i = (k + m )/3。A[0]未用。 return 0；}時(shí)間分析：比較次數(shù)2. 作一個(gè)“三分”檢索算法，它首先檢查1/3處的元素是否與X相等，然后檢查2/3處的元素，等等。 m=n。輸入：已按非減序分類的n個(gè)元素的數(shù)組A和X，X是被檢索的項(xiàng)。即每次檢索將與待查數(shù)據(jù)的比較次數(shù)減半。＋12. 2n1三、簡(jiǎn)答題1. 將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的類型相同問題，這些子問題相互獨(dú)立，以便各個(gè)擊破，分而治之。因此在移動(dòng)過程中，塔座B上圓盤不違反規(guī)則（3），而且塔座B上最底圓盤的編號(hào)與n具有相同奇偶性，塔座C上最底圓盤的編號(hào)與n具有不同奇偶性。① Hanoi（n－1，A，C，B）；② Move（A，B）；③ Hanoi（n－1，C，B，A）。用數(shù)學(xué)歸納法。圖A2 雙色漢諾塔問題的初始狀態(tài)在移動(dòng)紙盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則（1）：每次只能移動(dòng)一個(gè)紙盤；規(guī)則（2）：任何時(shí)刻都不允許將較大的紙盤壓在較小的紙盤之上；規(guī)則（3）：任何時(shí)刻都不允許將同色圓盤疊在一起；規(guī)則（4）：在滿足移動(dòng)規(guī)則（1）和（3）的前提下，可將紙盤移至A，B，C中任一根金針上。 （3）雙色漢諾塔問題：設(shè)A、B、C是三根金針。由數(shù)學(xué)歸納法知，產(chǎn)生的移動(dòng)序列均為：CC，O，CC，O，…，CC。由數(shù)學(xué)歸納法知，產(chǎn)生的移動(dòng)序列均為：C，O，C，O，…，C。當(dāng)n為奇數(shù)時(shí)，順時(shí)針非遞歸算法產(chǎn)生的移動(dòng)序列為：C，O，C，O，…，C；逆時(shí)針非遞歸算法產(chǎn)生的移動(dòng)序列為：CC，O，CC，O，…，CC。當(dāng)n＝1和n＝2時(shí)容易直接驗(yàn)證。 tower[top[y]+ 1][y] = tower[top[x]][x] 。 } else{ if(tower[top[x]][x]tower[top[y]]|y]) {int tmp=x。 while(top[1]n) { if(bb){ x=min。} top[0]=n。i=n。漢諾塔問題的非遞歸算法可描述如下： public static void Hanoi(int n) { int []top={0，0，0} int?。郏荩郏輙ower=new int[n+1][3]。 }}（2）漢諾塔問題的非遞歸算法。圖A1 漢諾塔問題的初始狀態(tài)在移動(dòng)紙盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則（1）：每次只能移動(dòng)一個(gè)紙盤；規(guī)則（2）：任何時(shí)刻都不允許將較大的紙盤壓在較小的紙盤之上；規(guī)則（3）：在滿足移動(dòng)規(guī)則（1）和（2）的前提下，可將紙盤移至A，B，C中任一根金針上。 Case 1: 2*x。 +1 +2 + k=T(k+1)即當(dāng)n=k+1時(shí)，命題成立。 )+2 + k =(k+1) 233。 – (2233。 －2233。－2233。 ) + T( 233。 – 2233。 – 2233。 ) – 2233。 k/2249。k/2249。 249。 249。 ) + k=2 T( 233。 ) +k+11= T(235。 +1當(dāng)n=k+1且k為奇數(shù)時(shí)，有T( 235。 ) +k1=k 233。當(dāng)n≤k時(shí), T(235。log(k+1) 249。 – 2 233。證明：（1）當(dāng)n=2時(shí)，由遞歸方程和初值，推得T（2）=T（1）+T（1）+21=0+0+21=1由方程的解，得 T（2）=22+1=1。 logn 249。 n/29. 設(shè)a0=1,a1=5,an=an1+6an2, 當(dāng)n≥2。8. 設(shè)有a0=0，a1=1，a2=1和an= an1+16 an220 an3，當(dāng)n≥3。6. 求序列2，5，13，35，…2n+3n的生成函數(shù)。即有：x mod (2(k+1)1) = k+1。用數(shù)學(xué)歸納法證明命題：當(dāng)n=2時(shí)，有x mod 3=2，成立。 (1)/28x/y 當(dāng)n=2m時(shí),m=0,1,2,3, …, 那么左端 = 0+1+1+2+2+3+3+…+(m1)+(m1)+m = 2*(1+m1)(m1)/2+m = m2右端 = 235。 (2m+1)2/4（4）若要使原等式成立，必有, 這里x = 235。log(n+1)249。 +1 = k+1, 所以，原等式成立。 （3）當(dāng)n為2k時(shí), 233。 y249。 y249。 249。 233。因?yàn)? ≤ ?x , ?y 1，所以有 0 ≤ ?x+?y 2。x249。 y249。 = 233。 y249。（2）當(dāng)x, y為整數(shù)時(shí)，原不等式成立。 x x x x x x +?x, y = 235。 +m)/n (x+m)/n log(n+1) 249。 y249。 y 1/2,所以左端小于右端。此時(shí),( 235。此時(shí)左端不一定為整數(shù)，而右端為整數(shù)。 = 233。（3）233。 x249。 )1/2 = 235。解答：（1）因?yàn)閙,n都是整數(shù)，所以n+m與nm同時(shí)為奇數(shù)或偶數(shù)。（2）233。四、計(jì)算題1. 求和：（1）（2）解答：（1）設(shè)和為S，則有S=a+2a2+3 a3+…+n an ①等式兩邊同乘a，得a S=a2+2 a3+…+n an+1 ② ①②得：(1 a)S= a+a2+a3+…+an nan+1整理得：S = a(1 an)/(1a)2 nan+1/(1a)（2）設(shè)和為S，則有當(dāng)n為偶數(shù)時(shí)，當(dāng)n為奇數(shù)時(shí)，2. 設(shè)m，n都是整數(shù)，計(jì)算（1）235。 //執(zhí)行查找　　(rt==1)?printf(“\nNot found.”):printf(“\nFound:%d.”,rt)。 //輸人數(shù)組元素, 元素可用空格分隔　　　　 printf(“input data searched”)。kn。Input all elermnts:39。　　printf(“input count( =50):”)。 //相等時(shí)绔束，返回元求下標(biāo)　　 else　　　if(x a[mid])　　　　m = midl。 include . defne N 50 int bsearch(int * a, int n, int x) //參數(shù)為數(shù)組、元素個(gè)數(shù)和被查找的值 { int k=0,m=n1,mid。編程時(shí)具體的實(shí)現(xiàn)方法是：將x與a的中間元素a［N／2］比較，如果相等則結(jié)束。 = 8n；（3）由于T（n）＝8為常數(shù)，因此算法可以為解任意規(guī)模的問題。的問題，則有T（n） = 32n = 32n39。n+log100=n+。3=100n3，\ n39。n39。證明： 7. 證明：如果一個(gè)算法在平均情況下的計(jì)算時(shí)間復(fù)雜度是Q（f（n）），則該算法在最壞情況下所需的計(jì)算時(shí)間是Ω（f（n））。5. 確定關(guān)系：對(duì)于下列各組函數(shù)f（n）和g（n），確定f（n）＝O（g（n））或f（n）＝Ω（g（n））或f（n）＝Q（g（n）），并簡(jiǎn)述理由。56 + 3/ n = O （1） // O （1）表示常數(shù)。是數(shù)值求和，即首項(xiàng)為n的n項(xiàng)等差為n的數(shù)列求和所以。同理，有：O(2n)O(n!)O(nn)。所以，O(g(n))之間的比較可以通過f(n)之間的比較得以實(shí)現(xiàn)。證明2：反證法。4. 當(dāng)問題的規(guī)模遞增時(shí)，將復(fù)雜度的極限稱為漸進(jìn)復(fù)雜度。（5）算法自然呈現(xiàn)模塊化，抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)可以封裝，便于移植和重用。（2）算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇，從中比較，優(yōu)化算法效率。 參考答案 61參考答案第1章一、選擇題1. C 2. A 3. C 4. C A D B 5. B 6. B7. D 8. B 9. B 10. B 11. D 12. B二、填空