Número:
Enunciado: Dados os algorimos LCS-LENGTH e PRINT-LCS, os quais não utilizam a matriz b. Seja também o algoritmo NEW-PRINT-LCS, que é uma modificação do PRINT-LCS original.
LCS-LENGTH (X,Y)
1 m=X.length
2 n=X.length
3 let C [0,...m,0...n] be new table
4 for i=1 to m
5 C[i,0]=0
6 for j=1 to n
7 C[0,j]=0
8 for i=1 to m
9 for j=1 to n
10 if X[i]=X[j]
11 C[i,j]=C[i-1,j-1]+1
12 elseif C[i-1,j]>=C[i-1,j-1]
13 C[i,j]=C[i-1,j-1]
14 else C[i,j]>=C[i,j-1]
15 return C
PRINT-LCS(C,X,Y,i,j)
1 if i == 0 or j == 0
2 return
3 if X[i]==Y[j]
4 PRINT-LCS(C,X,Y,i-1,j-1)
5 print X[i]
6 elseif C[i-1,j]>C[i,j-1]
7 PRINT-LCS(C,X,Y,i-1,j)
8 elseif C[i-1,j]<C[i,j-1]
9 PRINT-LCS(C, X,Y,i,j-1)
NEW-PRINT-LCS(C,X,Y,i,j)
1 if i == 0 or j == 0
2 return
3 if X[i]==Y[j]
4 NEW-PRINT-LCS(C,X,Y,i-1,j-1)
5 print X[i]
6 elseif C[i-1,j]>C[i,j-1]
7 NEW-PRINT-LCS(C,X,Y,i-1,j)
8 elseif C[i-1,j]<C[i,j-1]
9 NEW-PRINT-LCS(C, X,Y,i,j-1)
10 else
12 // A segunda metade de esta sub sequencia se encontra ao final da próxima subsequência
11 NEW-PRINT-LCS(C,X,Y,i-1,j)
12 NEW-PRINT-LCS(C, X,Y,i,j-1)
Dadas as seguintes afirmações em relação ao algoritmo NEW-PRINT-LCS:
I. O algoritmo encontra exatamente a mesma Longest common subsequence que o PRINT-LCS original, e utilizando maior tempo de execução.
II. O algoritmo encontra a Lesser common subsequence.
III. O algoritmo é uma extensão do PRINT-LCS, porque encontra todas as Longest common subsequence.
IV. O algoritmo encontra somente duas Longest common subsequence.
São corretas:
a. somente I
b. somente II
c. somente III
d. somente IV
e DNA
Ideia original de: Vladimir Jaime Rocca Layza
Nenhum comentário:
Postar um comentário