¿Cuál es el número de recuento de cadenas binarias sin unos consecutivos?

Consideremos un ejemplo para explicar el concepto de contar cadenas binarias sin unos consecutivos.

Ejemplo

Supongamos que queremos contar el número de cadenas binarias de longitud 3 que no contienen unos consecutivos. Una cadena binaria es una cadena que consta únicamente de ceros y unos.

Las posibles cadenas binarias de longitud 3 son: 000, 001, 010, 011, 100, 101, 110 y 111.

Sin embargo, necesitamos contar solo aquellas cadenas binarias que no tienen unos consecutivos. Por lo tanto, debemos excluir las cadenas 011, 101 y 111 del recuento.

Analicemos las cadenas binarias restantes:

• 000: esta es una cadena válida porque no tiene unos consecutivos.

• 001: Esta es una cadena válida porque no tiene unos consecutivos.

• 010: Esta es una cadena válida porque no tiene unos consecutivos.

• 100: esta es una cadena válida porque no tiene unos consecutivos.

• 110: Esta es una cadena no válida porque tiene unos consecutivos.

Del análisis anterior, podemos ver que hay 4 cadenas binarias válidas de longitud 3 sin unos consecutivos.

Programa PHP para contar el número de cadenas binarias sin unos consecutivos

Método 1: uso de programación dinámica

Ejemplo

Producción

Number of binary strings without consecutive 1's: 13

Explicación del código

Este código PHP define una función llamada countBinaryStrings que calcula el número de cadenas binarias de longitud $n sin unos consecutivos usando programación dinámica. Inicializa una matriz $dp con los casos base $dp[0] = 1 y $dp[1] = 2, que representan los recuentos de cadenas de longitud 0 y 1, respectivamente. Luego utiliza un bucle para completar los recuentos restantes para las longitudes 2 a $n, sumando los recuentos para las longitudes $i - 1 y $i - 2. Finalmente, devuelve el recuento de longitud $n y lo imprime. En este ejemplo específico, el código calcula el número de cadenas binarias sin unos consecutivos para una longitud de 5 y muestra el resultado.

Método 2

Producción

Number of binary strings without consecutive 1's: 13

Explicación del código

Este código PHP calcula el número de cadenas binarias distintas de longitud $n sin dos unos consecutivos. Define dos matrices, $a y $b, para almacenar los recuentos. Los casos base se establecen como $a[0] = $b[0] = 1. Luego, se utiliza un bucle para calcular los recuentos de longitudes de 1 a $ n-1. El recuento de longitud $i se obtiene sumando el recuento de longitud $i-1 de la matriz $a y el recuento de longitud $i-1 de la matriz $b. Además, el recuento de longitud $i en la matriz $b se obtiene del recuento de longitud $i-1 en la matriz $ a. Finalmente, el código devuelve la suma del recuento de longitud $n-1 de la matriz $a y el recuento de longitud $n-1 de la matriz $b, que representa el recuento total de cadenas binarias sin unos consecutivos. En este ejemplo particular, el código calcula el recuento para una longitud de 5 y muestra el resultado.

Conclusión

En conclusión, el primer método utiliza programación dinámica, inicializando una matriz con casos base y calculando iterativamente los recuentos para longitudes mayores. Calcula eficientemente el resultado sumando los recuentos de las dos longitudes anteriores. El segundo método emplea un enfoque más simple, utilizando dos matrices para almacenar recuentos y actualizándolos iterativamente en función de los recuentos de la longitud anterior. Calcula directamente el recuento total sin la necesidad de sumar las dos matrices por separado. Ambos métodos proporcionan recuentos precisos para cadenas binarias sin unos consecutivos, y la elección entre ellos puede depender de requisitos específicos y consideraciones de rendimiento.