阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 给定一个字符序列B=b1b2…bn,其中bi∈{A,C,G,U}。B上的二级结构是一组字符对集合S={(bi,bj)},其中i,j∈{1,2,…,n},并满足

admin2019-10-08  31

问题 阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
    【说明】
    给定一个字符序列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)和(GC)四种组合之一;
    (2)S中的每对字符之间至少有四个字符将其隔开,即f<j-4;
    (3)S中每一个字符(记为bk)的配对存在两种情况:bk不参与任何配对;bk和字符bt配对,其中t<k-4;
    (4)(不交叉原则)若(bi,bj)和(bk,bt)是S中的两个字符对,且i<k,则i<k<j<1不成立。
    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)
    {
    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) {
    int i,j,k,t;
    int max;
    int C[LEN][LEN]={0};
    for(k=5;k<=n.1;k++)
{
    for(i=1;i<=n-k;i++)
    {
    j=i+k;
    ______(1);
    for(______(2);t<=j-4;t++)
    {
    if(______(3))&& max<C[t-1]+1+C[t+1][j-1])
    max=C[t-1]+1+C[t+1][j-1];
    }
    C[j]=max;
    printf(’’c[%d][%d]=%d--’’,i,j,C[j]);
    }
}
  return ______(4)
}
根据题干说明和C代码,算法采用的设计策略为______(5)。
算法的时间复杂度为______(6),(用O表示)。

选项

答案(5)动态规划 (6)O(n3)

解析
转载请注明原文地址:https://jikaoti.com/ti/dZa7FFFM
0

相关试题推荐
最新回复(0)