viernes, 27 de febrero de 2009

Problema...

¿Cuántas cadenas binarias de longitud n existen que no tengan dos ceros consecutivos?
Por ejemplo:
Con n = 1 tenemos el conjunto {0,1} es decir, hay dos cadenas que cumplen esa condición
Con n = 2 tenemos el conjunto {01,10,11}, tenemos tres elementos
Con n = 3 tenemos el conjunto {010, 011, 101, 110, 111}

En general podemos partir el conjunto en dos,

sea

cadenas(n)={Conjunto de todas las cadenas binarias de longitud n tal que no tienen dos ceros consecutivos}


Definamos

a*cadenas(x)={ a*x | a es 0 ó 1 y x está en cadenas(x)},


Por ejemplo:

1*cadenas(2) = {101, 110, 111}
0*cadenas(1) = {01, 00}


Entonces partamos el problema en dos casos. El conjunto de cadenas binarias de longitud n tal que no tienen dos ceros consecutivos es igual a, las cadenas que empiezan con 0 concatenadas con las cadenas de longitud n-1 binarias que no tienen dos ceros consecutivos, más las cadenas que empiezan con 10 concatenadas con las cadenas de longitud n-2 binarias que no tienen dos ceros consecutivos.

Podemos escribirlo así:

cadenas(n) = 1*cadenas(n-1) + 01*cadenas(n-2)


¿Te parece conocido? Es la sucesión de Fibonacci,

f(n) = f(n-1) + f(n-2)
f(1) = 1
f(0) = 1


sólo que las condiciones iniciales cambian,

c(n) = c(n-1) + c(n-2)
c(1) = 2
c(0) = 1

1 comentario:

adairstarkey dijo...

Hola que tal, que chido tu blog, en especial este blog me sirvió para mi tarea, estoy estudiando la maestría en ciencias de la computación en la UAM Azcapotzalco.

Saludos.