軟件設(shè)計師案例分析每日一練試題內(nèi)容（2022/3/2）
給定一個字符序列B=b1b2...bn,其中bi∈{A,C,G,U}。B上的二級結(jié)構(gòu)是一組字符對集合S={(bi,bj)},其中i,j∈{1,2,….,n}，并滿足以下四個條件：
（1）S中的每對字符是(A,U),(U,A),(C,G)和(G,C)四種組合之一；
（2）S中的每對字符之間至少有四個字符隔開，即i<j-4；
（3）S中每一個字符（記為bk）的配對存在以下兩種情況：bk不參與任何配對；bk和字符bt配對，其中t<k-4;
（4）（不交叉原則）若（bi,bj）和（bk,bl）是S中的兩個字符對，且i<k，則i<k<j<l不成立。
B的具有最大可能字符對數(shù)的二級結(jié)構(gòu)S被稱為最優(yōu)配對方案，求解最優(yōu)配對方案中的字符對數(shù)的方法如下：
假設(shè)用C(i,j)表示字符序列bibi+1....bj的最優(yōu)配對方案（即二級結(jié)構(gòu)S）中的字符對數(shù)，則，C(i,j)可以遞歸定義為：
下面代碼是算法的C語言實現(xiàn)，其中
n:字符序列長度
B[]:字符序列
C[][]:最優(yōu)配對數(shù)量數(shù)組
【C代碼】
#include<stdio.h>
#include<stdlib.h>
#define LEN 100
/*判斷兩個字符是否配對*/
int isMatch(char a,char b){undefined
    if ((a=='A'&&b=='U')||( a=='U'&&b=='A'))
       return 1;
    if ((a=='C'&&b=='G')||( a=='G'&&b=='C'))
       return 1;
    return 0;
}
/*求最大配對數(shù)*/
int RNA_2(char B[LEN],int n){undefined
   int i,j,k,t;
   int max;
   int C[LEN][LEN]={0};
   for(k=5;k<=n-1;k++){undefined
     for(i=1;i<=n-k;i++){undefined
       j=i+k;
       (  1  )
       for((  2  );t<=j-4;t++){undefined
         if( (  3  )&&max<C[i][t-1]+1+C[t+1][j-1])
            max=C[i][t-1]+1+C[t+1][j-1];
       } 
       C[i][j]=max;
       printf("C[%d][%d]=%d--",i,j,C[i][j]);
     }
  }
  return(  4  );
}
問題1 (8分)
根據(jù)題干說明，填充 C 代碼中的空(1)-(4)。
問題2 (4分)
根據(jù)題干說明和 C 代碼，算法采用的設(shè)計策略為(  5  )。
算法的時間復(fù)雜度為(  6  )，(用O表示)。
問題3 (3分)
給定字符序列 ACCGGUAGU ,根據(jù)上述算法求得最大字符對數(shù)為(  7  )。
參考答案
【問題1】
（1）max=C[i][j-1]
（2）t=i
（3）isMatch(B[t],B[j])
（4）C[1][n]
【問題2】
（5）動態(tài)規(guī)劃
（6）0(n3)
【問題3】
（7）2