算法设计与分析复习题(3)

}

int main() { int a[M]; //

srand(time(0));

printf(\ for (int i=0;i

radixsort(m,5); a[i]=(int)rand()-5000;

a[i]=(a[i]+120000)0000; m.push(a[i]); if(i==0) printf(\else

printf(\

return 0; }

13、 编写一个算法，可以检测一个字符串是否回文（如：afaddafa，abwba等）。

int fun(char *A,int n){ int i ,j; i=0,j=n-1; while(i<=j){

if(A[i]!=A[j])break; i++;j--;

}

if(i<=j)return 0; else return 1; }

14、 如果是检测一个字符串中是否包含一个回文子串，应如何编写算法。如果是

找最大的回文子串呢？

int judge(char *A,int n0, int n1){ int i,j; i=n0;j=n1; while(i<=j){

if(A[i]!=A[j])break; i++;j--; }

if(i<=j)return 0; else return 1; }

int fun(char *A,int n){ int i,j,k;

for(i=1,i<=n-1;i--){ for(j=0;j

if(judge(&A,j,j+i)==1){output(&A,j,j+i);return 1;} } } return 0; }

如果找最大回文则需更改为； int fun(char *A,int n){ int i,j,k;

for(i=n-1;i>=1;i--){ for(j=0;j<=n-i-1;j++){

if(fun(&A,j,i+j)==1){output(&A,j,i+j);return 1;} } } return 0; }

此时最先找到的即为最大回文。

15、 设n个不同的整数排好序后存在数组T[1：n]中。若存在一个下标i，使得T[i]=i，

设计一个有效的算法找到该下标。要求时间复杂性是O(logn)。

因为整数数组已排好序，可以从数组的正中元素开始寻找T[i]，当T[(n+1)/2]>(n+1)/2时，要求的i一定在T[1:(n+1)/2-1]中，当T[(n+1)/2]<(n+1)/2时，要求的i一定在T[(n+1)/2+1:n]中，递归地使用此方法。 //初始Left=1 Right=n int find_i(T, Left, Right) {

if(Left>Right) return -1; (Left+Right)/2

if(T[(Left+Right)/2]>(Left+Right)/2) return find_i(T, (Left+Right)/2+1, Right); if(T[(Left+Right)/2]<(Left+Right)/2) return find_i(T, Left, (Left+Right)/2-1); else return (Left+Right)/2; }

16、 编写一个采用KMP的算法查找T的子串P，并判断匹配失败的字符是否在P

中，以此确定可滑动的最大距离。

int next[100]; int lenthT,lenthP; void get_next(char *P){ int i,j; i=1;j=0; next[1]=0; while(i<=lenthP){

} }

if(j==0||P[i]==P[j]){ }

else j=next[j];

++i;++j;

if(P[i]!=P[j]) next[i]=j; else next[i]=next[j];

int KMP(char *T,char *P){ int i,j; i=1;j=1; get_next(P);

while(i<=lenthT&&j<=lenthP){ }

if(j>lenthP)return i-lenthP; else return 0; }

17、 编写一个算法找出

if(j==0||T[i]==P[j]){++i;++j;} else j=next[j];

2个正文中的最长公共子序列，若要找

出3个正文中的最长公共子序列，应如何编写算法。

算法思想

X= Y=

的LCS为Z=

(1)若xm=yn,则zk=xm=yn,则z是xm-1和yn-1的LCS; (2)若xm!=yn,且zk!=xm,则z是xm-1和y的LCS; (3)若xm!=yn,且zk!=yn,则z是xm和yn-1的LCS 采用动态规划的思想,

?0 if i?0 or j?0 len(i,j)???len(i?1,j?1)?1 if i,j ?0 and ai?bj?max(len(i?1,j),len(i,j?1)) if i,j ?0 and ai?bj?

通过公共字串的长度以及公共字串的起始地址求出公共字串; 时间复杂度为O(mn); #include #include #define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])

{

int i, j;

for(i = 0; i <= m; i++) c[i][0] = 0; for(j = 1; j <= n; j++) c[0][j] = 0; for(i = 1; i<= m; i++) {

for(j = 1; j <= n; j++) {

if(x[i-1] == y[j-1]) {

c[i][j] = c[i-1][j-1] + 1; b[i][j] = 0; }

else if(c[i-1][j] >= c[i][j-1]) {

c[i][j] = c[i-1][j]; b[i][j] = 1; } else