Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 53

Подпоследовательность данной последовательности — это просто заданная последовательность с некоторыми опущенными элементами (возможно, не всеми или всеми). Нам даны две последовательности X [m] и Y [n] длин m и n соответственно с индексами X и Y, начинающимися с 0.
Мы хотим найти длину самой длинной общей подпоследовательности (LCS) для X [m] и Y [n] как l (m, n), где неполное рекурсивное определение для функции l (i, j) для вычисления длина LCS из X [m] и Y [n] приведена ниже:

l(i,j) = 0, if either i=0 or j=0
       = expr1, if i,j > 0 and X[i-1] = Y[j-1]
       = expr2, if i,j > 0 and X[i-1] != Y[j-1] 

(A) expr1≡l (i-1, j) + 1
(B) expr1 ≡ l (i, j-1)
(C) expr2 ≡ max (l (i-1, j), l (i, j-1))
(D) expr2 ≡ max (l (i-1, j-1), l (i, j))

Ответ: (с)
Объяснение: В задаче с самой длинной общей подпоследовательностью есть два случая для X [0..i] и Y [0..j]

1) The last characters of two strings match. 
   The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]
2) The last characters don't match.
   The length of lcs is max of following two lcs values
   a) LCS of X[0..i-1] and Y[0..j]
   b) LCS of X[0..i] and Y[0..j-1]

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2009 | Вопрос 53

0.00 (0%) 0 votes