Рубрики

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

Рассмотрим данные, приведенные в предыдущем вопросе . Значения l (i, j) могут быть получены динамическим программированием на основе правильного рекурсивного определения l (i, j) формы, приведенной выше, с использованием массива L [M, N], где M = m + 1 и N = n + 1, так что L [i, j] = l (i, j).
Какое из следующих утверждений будет ИСТИННО в отношении решения динамического программирования для рекурсивного определения l (i, j)?
(A) Все элементы L должны быть инициализированы в 0, чтобы значения l (i, j) были правильно рассчитаны
(B) Значения l (i, j) могут быть вычислены в главном порядке строки или в главном порядке столбца L (M, N)
(C) Значения l (i, j) не могут быть вычислены ни в мажорном порядке строки, ни в мажорном порядке столбца L (M, N)
(D) L [p, q] необходимо вычислять до L [r, s], если либо p <r, либо q <s.

Ответ: (Б)
Объяснение: Значение может быть вычислено либо в мажорном ряду, либо в мажорном столбце, см. Http://espressocode.top/dynamic-programming-set-4-longest-common-subsequence/ .
Мы можем поменять местами два цикла, не влияя на результат.
Тест на этот вопрос

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

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

0.00 (0%) 0 votes