软件设计师案例分析每日一练试题内容（2022/3/2）
给定一个字符序列B=b1b2...bn,其中bi∈{A,C,G,U}。B上的二级结构是一组字符对集合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的具有最大可能字符对数的二级结构S被称为最优配对方案，求解最优配对方案中的字符对数的方法如下：
假设用C(i,j)表示字符序列bibi+1....bj的最优配对方案（即二级结构S）中的字符对数，则，C(i,j)可以递归定义为：
下面代码是算法的C语言实现，其中
n:字符序列长度
B[]:字符序列
C[][]:最优配对数量数组
【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;
}
/*求最大配对数*/
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分)
根据题干说明，填充 C 代码中的空(1)-(4)。
问题2 (4分)
根据题干说明和 C 代码，算法采用的设计策略为(  5  )。
算法的时间复杂度为(  6  )，(用O表示)。
问题3 (3分)
给定字符序列 ACCGGUAGU ,根据上述算法求得最大字符对数为(  7  )。
参考答案
【问题1】
（1）max=C[i][j-1]
（2）t=i
（3）isMatch(B[t],B[j])
（4）C[1][n]
【问题2】
（5）动态规划
（6）0(n3)
【问题3】
（7）2