计算两个字符串x和y的最长公共子串(Longest Common Substring)。
假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。
c[i][j]满足最优子结构,其递归定义为:
计算所有c[i][j](0≤i≤m,0≤j≤n)的值,值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j,确定一个最长公共子串。
【C代码】
(1)常量和变量说明
x,y:长度分别为m和n的字符串
c[i][j]:记录x中前i个字符和y中前j个字符的最长公共子串的长度
max:x和y的最长公共子串的长度
maxi,maXj:分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置(序号)
(2)C程序
#include<stdio.h>
#include<string.h>
int c[50][50];
int maxi;
int maxj;
int lcs(char*x,int m,char*y,int n){
int i,j;
int max=0;
maxi=0;
maxj=0;
for(i=0;i<=m;i++)c[i][0]=0;
for(i=1;i<=n;i++)c[0][i]=0;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if((1)){
c[i][j]=c[i-1][j-1]+1;
if(max<c[i][j]){
(2);
maxi=i;
maxj=j;
}
}
else(3);
}
}
return max;
}
void printLCS(int max,char*x){
int i=0;
if(max==0)return;
for((4);i<maxi;i++)
printf("%c",x[i]);
}
void main( ){
char*x="ABCADAB";
char*y="BDCABA";
int max=0;
int m=strlen(x);
int n=strlen(y);
max=lcs(x,m,y,n);
printLCS(max,x);
}
【问题1】(8分)
根据以上说明和C代码,填充C代码中的空(1)~(4)。
【问题2】(4分)
根据题干说明和以上C代码,算法采用了(5)设计策略。
分析时间复杂度为(6)(用O符号表示)。
【问题3】(3分)
根据题干说明和以上C代码,输入字符串x="ABCADAB','y="BDCABA",则输出为(7)。
【问题1】
(1)x[i-1]==y[j-1]
(2)max=c[i][j]
(3)c[i][j]=0
(4)i=maxi-max
【问题2】
(5)动态规划法
(6)O(m*n)
【问题3】
(7)AB
首先对于C语言算法题,一般的解题思路是先解决除程序填空以外的问题,这些问题弄清楚,有利于程序填空部分的分析。
第一步,分析程序所采用的算法,常见的算法包括:分治法、动态规划法、回溯法、贪心法。本题中要求的是两个串的最长公共子串,在程序中采用了数组来记录子问题的中间结果,这一特征与动态规划法的做法非常吻合,所以应选动态规划法。
第二步,解决“输入字符串x="ABCADAB’,'y="BDCABA",则输出为(7)”的问题,该问题相对容易解决,因为题目已告知程序的作用是求最长公共子串,而且从程序的输出函数可以看出,要输出的,只有子串,没有其他信息,所以我们只需要手动求两个串的公共子串,并写出答案即可。两个串第一个公共子串明显是“AB”,所以输出的结果为“AB”。
第三步,求时间复杂度,由于程序中最多双重循环,其中外层循环的规模为m,而内层循环的规模为n,所以时间复杂度为O(m*n)。
第四步,也是最难的一步,是解决程序填空的问题。动态规划的问题,一般都会给出递归定义式,这个式子,往往是多个空的关键点。以本题为例:
第1空是判断的条件,输出的结果是c[i][j]=c[i-1][j-1]+1,此时根据递归式可以看到,所需的条件是x[i-1]=y[j-1],因此第1空填写判断条件x[i-1]==y[j-1]。
第2空是在if(max<c[i][j])跟随的大括号中,根据前后代码和此处的判断条件,当max小于当前时,应该改变max的值,并记录此时的maxi和maxj,此处缺少改变max的值,因此,第2空应该将当前最大值赋值给max,即max=c[i][j]。
第3空是第一个if语句的else选择,根据递归式,if(x[i-1]==y[j-1])不满足时,属于其他情况,应该赋值为0,因此第3空填写c[i][j]=0。
而第4空是用于打印结果,由于maxi记录了子串末尾+1的位置信息,子串长度为max,所以用maxi-max定位至子串开始位置,以便打印子串,因此第4空填写i=maxi-max。
( )is the process of transforming information so it is unintelligible to anyone but the intended recipient.
As each application module is completed,it undergoes( )to ensure that it operates correctly and reliably.
( )algorithm specifies the way to arrange data in a particular order.
After analyzing the source code,( )generates machine instructions that will carry out the meaning of the program at a later time.
( )can help organizations to better understand the information contained within the data and will also help identify the data that is most important to the business and future business decisions.
浏览器开启无痕浏览模式后,( )依然会被保存下来。
下列协议中,不属于TCP/IP协议簇的是( )。
下列传输介质中,带宽最宽、抗干扰能力最强的是( )。
数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要( )个独立的参数。
某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为( )。