1、算法设计与分析1、(1) 证明： O(f)+O(g)=O(f+g)（7 分）(2) 求下列函数的渐近表达式：（6 分） 3n 2+10n; 21+1/n;2、对于下列各组函数 f(n)和 g(n)，确定 f(n)=O(g(n)或 f(n)=(g(n)或 f(n)=(g(n)，并简述理由。 （15 分）(1) ;5log)(;log)(2nnf(2)(3) ;l)(;)(2f3、试用分治法对数组 An实现快速排序。 （13 分）4、试用动态规划算法实现最长公共子序列问题。 （15 分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法
2、，指出应在哪些加油站停靠加油，使加油次数最少。 （12 分）6、试用动态规划算法实现下列问题：设 A 和 B 是两个字符串。我们要用最少的字符操作，将字符串 A 转换为字符串 B，这里所说的字符操作包括：(1)删除一个字符。(2)插入一个字符。(3)将一个字符改为另一个字符。将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A到 B 的编辑距离，记为 d(A,B)。试设计一个有效算法，对任给的两个字符串 A 和 B，计算出它们的编辑距离 d(A,B)。（16 分）7、试用回溯法解决下列整数变换问题：关于整数 i的变换 f和 g定义如下： 2/)(;3)(igif。对于给定的两个整
3、数 n和 m，要求用最少的变换 和 变换次数将 n变为 m。 （16 分）1、证明：令 F(n)=O(f),则存在自然数 n1、c 1，使得对任意的自然数 nn 1，有：F(n) c1f(n).（2 分）同理可令 G(n)=O(g),则存在自然数 n2、c 2，使得对任意的自然数nn 2，有：G(n)c 2g(n).（3 分）令 c3=maxc1,c2,n3=maxn1,n2,则对所有的 nn 3，有：F(n) c1f(n)c 3f(n)G(n)c 2g(n)c 3g(n).（5 分）故有：O(f)+O(g)=F(n)+G(n)c 3f(n)+c3g(n)=c3(f(n)+g(n)因此有：O(
4、f)+O(g)=O(f+g).（7 分） 解： 因为 ;013)(lim22nn由渐近表达式的定义易知：3n2 是 3n2+10n 的渐近表达式。.（3 分） 因为 ，由渐近表达式的定义易知：n,01221 是 的渐近表达式。.（6 分）n说明：函数 T(n)的渐近表达式 t(n)定义为： nTtn,0)(2、解：经分析结论为：（1） );5(logl2n.（5 分）（2） )(log2n；.（10 分）（3） ；.（15 分）3、解：用分治法求解的算法代码如下：int partition(float A,int p,int r)int i=p,j=r+1;float x=ap;while(1
5、)while(a+ix);if(i=j) break;ai aj.（4 分）;ap=aj;aj=x;return j;.（7 分）void Quicksort(float a,int p,int r)if(p=cij-1)cij=ci-1j;elsecij=cij-1;.（7 分）return cmn;.（8 分）;char* build_lcs(char s,char* a,char* b)int k,i=strlen(a),j=strlen(b),cNN;k=lcs_len(a,b,c);sk=0;while(k0)if(cij=ci-1j)i-;.（11 分）else if(cij=ci
6、j-1)j-;elses-k=ai-1;i-,j-;return s;.（15 分）5、解：int greedy(vecter x,int n)int sum=0,k=x.size();for(int j=0;jn)coutn)sum+;s=xi;.（9 分）return sum;.（12 分）6、解：此题用动态规划算法求解：int dist()int m=a.size();int n=b.size();vector d(n+1,0);for(int i=1;i1?dj-1:i;.（10 分）int del=ai-1=bj-1?0:1;dj=min(x+del,y+1,z+1);.（13 分）return dn;.（16 分）7、解：解答如下：void compute()k=1;while(!search(1,n)k+;if(kmaxdep)break;init();.（6 分）if(found)output();.（9 分）else coutk)return false;.（11 分）for(int i=0;i2;i+)int n1=f(n,i);tdep=I;.（13 分）if(n1=m|search(dep+1,n1)found=true;out();return true;return false;.（16 分）
