试题四（15分）
给定一个字符序列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){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;max=C[i][j-1];//填空1for(t=1;t<=j-4;t++){//填空2if(isMatch(B[t],B[j])&&max<C[i][t-1]+1+C[t+1][j-1])//填空3max=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 C[i][j];//填空4
}
问题1 (8分)
根据题干说明，填充 C 代码中的空(1)-(4)。
问题2 (4分)
根据题干说明和 C 代码，算法采用的设计策略为( 5 )。
算法的时间复杂度为( 6 )，(用O表示)。
问题3 (3分)
给定字符序列 ACCGGUAGU ,根据上述算法求得最大字符对数为( 7 )。
#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;max=C[i][j-1];//填空1for(t=1;t<=j-4;t++){//填空2if(isMatch(B[t],B[j])&&max<C[i][t-1]+1+C[t+1][j-1])//填空3max=C[i][t-1]+1+C[t+1][j-1];} C[i][j]=max;printf("C[%d][%d]=%d--",i,j,C[i][j]);}printf("\n");}return C[i][j];//填空4
}int main(){char B[LEN]="ACCGGUAGU";int r = RNA_2(B,9);return 0;
}
试题六（15分）
某航空公司的会员积分系统将其会员划分为:普卡 (Basic) 、银卡(Silver)和金卡 (Gold)
三个等级。非会员 (NonMember)可以申请成为普卡会员。会员的等级根据其 一年内累积的里程数进行调整。描述会员等级调整的状态图如图 6-1 所示 。现采用状态 (State) 模式
实现上述场景，得到如图 6-2 所示的类图。
【Java代码】
package test_2018_2;class FrequentFlyer{CState state;double flyMiles;public void setState(CState state) {this.state = state;}public FrequentFlyer() {this.state = new CNoCostomer();this.flyMiles = 0;this.setState(this.state);}public void travel(int miles){double bonusMiles = state.travel(miles, this);flyMiles=flyMiles+bonusMiles;}
}abstract class CState{public int flyMiles; //里程数public abstract double travel(int miles, FrequentFlyer context); //填空1//根据累积里程数调整会员等级
}class CNoCostomer extends CState{//非会员@Overridepublic double travel(int miles, FrequentFlyer context) {System.out.println("Your travel will not account for points.");return miles; //不累积里程数}
}class CBasic extends CState{ //普卡会员@Overridepublic double travel(int miles, FrequentFlyer context) {if (context.flyMiles>=25000&&context.flyMiles<5000){context.setState(new CSliver()); //填空2}if (context.flyMiles>=50000){context.setState(new CGold());//填空3}return miles;}
}class CGold extends CState{//金卡会员@Overridepublic double travel(int miles, FrequentFlyer context) {if (context.flyMiles>=25000&&context.flyMiles<50000){context.setState(new CSliver());//填空4}if (context.flyMiles<=25000){context.setState(new CBasic());//填空5}return miles+0.5*miles; //累积里程数}
}class CSliver extends CState{//银卡会员@Overridepublic double travel(int miles, FrequentFlyer context) {if (context.flyMiles<=25000){context.setState(new CBasic());}if (context.flyMiles>50000){context.setState(new CGold());}return miles+0.25*miles; //累积里程数}
}public class CardTest {public static void main(String[] args) {}
}
