1、算法設(shè)計與分析1、(1)證明：O(f)+O(g)=O(f+g)(7分)(2)求下列函數(shù)的漸近表達式：(6分) 3n2+10n; 21+1/n;2、對于下列各組函數(shù)f(n)和g(n),確定f(n)=O(g(n)或f(n)=Q(g(n)或f(n)=0(g(n),并簡述理由。(15分)(1)f(n)2logn;g(n)logn5;f(n)logn2;g(n)、n;f(n)n;g(n)log2n;3、試用分治法對數(shù)組An實現(xiàn)快速排序。(13分)4、試用動態(tài)規(guī)劃算法實現(xiàn)最長公共子序列問題。(15分)5、試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設(shè)計一個有效

2、算法，指出應在哪些加油站?？考佑?，使加油次數(shù)最少。(12分)6、試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)A和B是兩個字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B,這里所說的字符操作包括：(1) 刪除一個字符。(2) 插入一個字符。(3) 將一個字符改為另一個字符。將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d(A,B)。試設(shè)計一個有效算法，對任給的兩個字符串A和B,計算出它們的編輯距離d(A,B)。(16分)7、試用回溯法解決下列整數(shù)變換問題：關(guān)于整數(shù)i的變換f和g定義如下：f(i)3i;g(i)i/2。對于給定的兩個整數(shù)n和m，要求用最少的變換f和g變換次

3、數(shù)將n變?yōu)閙。(16分)1、(1)證明：令F(n)=0,則存在自然數(shù)ni、ci,使得對任意的自然數(shù)n>ni,有：F(n)wcif(n).(2分)同理可令G(n)=O(g)則存在自然數(shù)n2、C2,使得對任意的自然數(shù)nn2,有：G(n)<C2g(n).(3分)令C3=maxci,C2,n3=maxni,n2，則對所有的nn3,有：F(n)wcif(n)Wc3f(n)G(n)<C2g(n)wag(n).(5分)故有：O(f)+O(g)=F(n)+G(n)<c3f(n)+C3g(n)=c3(f(n)+g(n)因此有：O(f)+O(g)=O(f+g).(7分)解：(3n210n)

4、3n2nlim20;因為n3n10n由漸近表達式的定義易知：3n2是3n2+10n的漸近表達式。.(3分)12121因為亍0,n，由漸近表達式的定義易知:21-n.(6分)21是211的漸近表達式nT(n)t(n)0,n說明：函數(shù)T(n)的漸近表達式t(n)定義為:T(n)2、解：經(jīng)分析結(jié)論為:(1)logn2(logn5);(5分)logn2Cn)(10分)(3)n(log2n)(15分)3、解：用分治法求解的算法代碼如下：intpartition(floatA,intp,intr)inti=p,j=r+1;floatx=ap;while(1)while(a+i<x);while(a-

5、j>x);if(i>=j)break;aiaj.(4分);ap=aj;aj=x;returnj;.(7分)voidQuicksortfloata,intp,intr)if(p<r)intq=partition(a,p,r);.(10分)Quicksort(a,p,q-1);Quicksort(a,q+1,r);Quicksort(a,0,n-1);.(13分)4、解：用動態(tài)規(guī)劃算法求解的算法代碼如下：intlcs_len(char*a,char*b,intcN)intm=strlen(a),n=strlen(b),i,j;for(i=0;i<=m;i+)ci0=0;fo

6、r(j=1;j<=n;j+)c0j=0;.(4分)for(i=1;i<=m;i+)for(j=1;j<=n;j+)if(ai-1=bj-1)cij=ci-1j-1+1;elseif(ci-1j>=cij-1)cij=ci-1j;elsecij=cij-1;.(7分)returncmn;.(8分);char*build_lcs(chars,char*a,char*b)intk,i=strlen(a),j=strlen(b),cNN;k=lcs_len(a,b,c);sk='0'while(k>0)if(cij=ci-1j)i-;.(11分)elsei

7、f(cij=cij-1)j-;elses-k=ai-1;i-,j-;returns;.(15分)5、解：intgreedy(vecter<int>x,intn)intsum=0,k=x.size();for(intj=0;j<k;j+)if(xj>n)cout<<”Nosolution”<<endl;return-1;.(6分)for(inti=0,s=0;i<k;i+)s+=xi;if(s>n)sum+;s=xi;.(9分)returnsum;.(12分)6、解：此題用動態(tài)規(guī)劃算法求解：intdist()intm=a.size();

8、intn=b.size();vector<int>d(n+1,0);for(inti=1;i<二n;i+)di=i;.(5分)for(i=1;i<=m;i+)inty=i-1;for(intj=1;j<=n;j+)intx=y;y=dj;intz=j>1?dj-1:i;.(10分)intdel=ai-1=bj-1?0:1;dj=min(x+del,y+1,z+1);.(13分)returndn;.(16分)7、解：解答如下：voidcompute()k=1;while(!search(1,n)k+;if(k>maxdep)break;init();；.(6分)if(found)output();.(9分)elsecout<<”NoSolution!”<<endl;boolsearch(intdep,intn)if(dep>k)retu