PUERTA | PUERTA CS 2008 | Pregunta 78

Sea xn el número de strings binarias de longitud n que no contienen ceros consecutivos. ¿Cuál de las siguientes recurrencias satisface Xn?

(A) A
(B) B
(C) C
(D) D

Respuesta: (D)
Explicación:

• Para n = 1, es decir, strings binarias de longitud 1, las strings son ‘0’, ‘1’.
  Entonces, X1 = 2
• Para n = 2, es decir, strings binarias de longitud 2, las strings son ’01’, ’10’, ’11’.
  (aquí la string ’00’ será rechazada porque tiene ceros consecutivos).
  Entonces, X2 = 3
• Para n = 3, es decir, strings binarias de longitud 3, las strings son ‘010’, ‘011’, ‘101’, ‘110’, ‘111’.

0 01 (rechazado)
0 10
0 11
1 01
1 10
1 11
Entonces, X3 = 5
Esto muestra que X3 = X2 + X1
Por lo tanto, X(n) = X(n – 1) + X(n – 2)
Por favor comente a continuación si encuentra algo incorrecto en la publicación anterior.

Cuestionario de esta pregunta