算法设计与分析试卷及答案

} };

Quicksort(a,0,n-1);……………………………..（13分） 4、解：用动态规划算法求解的算法代码如下： int lcs_len(char* a,char* b,int c[][N]) {

int m=strlen(a),n=strlen(b),i,j; for(i=0;i<=m;i++)c[i][0]=0;

for(j=1;j<=n;j++)c[0][j]=0;……………………………..（4分） for(i=1;i<=m;i++) for(j=1;j<=n;j++)

if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];

elsec[i][j]=c[i][j-1];……………………………..（7分） return c[m][n];……………………………..（8分） };

char* build_lcs(char s[],char* a,char* b) {

int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcs_len(a,b,c); s[k]=’\\0’; while(k>0){

if(c[i][j]==c[i-1][j])i--;……………………………..（11分）

else if(c[i][j]==c[i][j-1])j--; else{ s[--k]=a[i-1]; i--,j--; } }

return s;……………………………..（15分） }

5、解：int greedy(vecter x,int n) {

int sum=0,k=x.size(); for(int j=0;jn){

cout<<”Nosolution”<

return-1;……………………………..（6分） }

for(int i=0,s=0;i

if(s>n){sum++;s=x[i];}……………………………..（9分） }

return sum;……………………………..（12分） }

6、解：此题用动态规划算法求解： int dist()

{

int m=a.size(); int n=b.size(); vector d(n+1,0);

for(int i=1;i<=n;i++)d[i]=i;……………………………..（5分） for(i=1;i<=m;i++){ int y=i-1;

for(int j=1;j<=n;j++){ int x=y; y=d[j];

int z=j>1?d[j-1]:i;……………………………..（10分） int del=a[i-1]==b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1);……………………………..（13分） } }

return d[n];……………………………..（16分） }

7、解：解答如下： void compute() { k=1;

while(!search(1,n)){ k++;

if(k>maxdep)break;

init();

};……………………………..（6分）

if(found)output();……………………………..（9分） else cout<<”NoSolution!”<

bool search(int dep,int n) {

if(dep>k)return false;……………………………..（11分） for(int i=0;i<2;i++){

int n1=f(n,i);t[dep]=I;……………………………..（13分） if(n1==m||search(dep+1,n1)){ found=true; out(); return true; }

return false;……………………………..（16分） }