Sea n el número de strings de n bits que NO contienen dos 1 consecutivos. ¿Cuál de las siguientes es la relación de recurrencia para un n
(A) A
(B) B
(C) C
(D) D
Respuesta: (B)
Explicación: El valor mínimo de ‘n’ para la recurrencia sería 3.
Para n = 1, número de strings = 2 (0, 1)
Para n = 2, número de strings = 3 (00, 01, 10)
Para n = 3, número de strings = 5 (000, 001, 010, 100, 101)
Para n = 4, número de strings = 8 (0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001)
…
Esto parece seguir la serie de Fibonacci y la relación de recurrencia es a n = a n−1 + a n−2 .
Por lo tanto, B es la opción correcta.
https://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA