Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 78

Обозначим через xn количество двоичных строк длины n, которые не содержат последовательных 0. Какой из следующих рецидивов удовлетворяет Xn?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (D)
Объяснение:

  • Для n = 1, то есть двоичные строки длиной 1, строки «0», «1».
    Итак, X1 = 2
  • Для n = 2, т. Е. Двоичные строки длиной 2, это строки '01', '10', '11'.
    (здесь строка «00» будет отклонена, поскольку имеет последовательные нули).
    Итак, Х2 = 3
  • Для n = 3, то есть двоичные строки длиной 3, это «010», «011», «101», «110», «111».

0 01 (отклонено)
0 10
0 11
1 01
1 10
1 11
Итак, Х3 = 5
Это показывает, что X3 = X2 + X1
Следовательно, X (n) = X (n — 1) + X (n — 2)
Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

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

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

ВОРОТА | GATE CS 2008 | Вопрос 78

0.00 (0%) 0 votes