O que é o número de contagem de strings binárias sem 1s consecutivos?

Vamos considerar um exemplo para explicar o conceito de contagem de strings binárias sem 1's consecutivos.

Exemplo

Suponha que queremos contar o número de strings binárias de comprimento 3 que não contêm 1's consecutivos. Uma string binária é uma string que consiste apenas em 0 e 1.

As strings binárias possíveis de comprimento 3 são: 000, 001, 010, 011, 100, 101, 110 e 111.

No entanto, precisamos contar apenas as strings binárias que não possuem 1's consecutivos. Portanto, precisamos excluir as strings 011, 101 e 111 da contagem.

Vamos analisar as strings binárias restantes:

• 000: Esta é uma string válida porque não possui 1s consecutivos.

• 001: Esta é uma string válida porque não possui 1s consecutivos.

• 010: Esta é uma string válida porque não possui 1s consecutivos.

• 100: Esta é uma string válida porque não possui 1s consecutivos.

• 110: Esta é uma string inválida porque possui 1s consecutivos.

A partir da análise acima, podemos ver que existem 4 strings binárias válidas de comprimento 3 sem 1's consecutivos.

Programa PHP para contar o número de strings binárias sem 1's consecutivos

Método 1 - Usando Programação Dinâmica

Exemplo

Saída

Number of binary strings without consecutive 1's: 13

Explicação do código

Este código PHP define uma função chamada countBinaryStrings que calcula o número de strings binárias de comprimento $n sem 1s consecutivos usando programação dinâmica. Ele inicializa um array $dp com os casos base $dp[0] = 1 e $dp[1] = 2, representando as contagens para strings de comprimento 0 e 1, respectivamente. Em seguida, ele usa um loop para preencher as contagens restantes para comprimentos 2 a $n, somando as contagens para comprimentos $i - 1 e $i - 2. Por fim, ele retorna a contagem do comprimento $n e a imprime. Neste exemplo específico, o código calcula o número de strings binárias sem 1s consecutivos para um comprimento de 5 e exibe o resultado.

Método 2

Saída

Number of binary strings without consecutive 1's: 13

Explicação do código

Este código PHP calcula o número de strings binárias distintas de comprimento $n sem dois 1's consecutivos. Ele define dois arrays, $a e $b, para armazenar as contagens. Os casos base são definidos como $a[0] = $b[0] = 1. Em seguida, um loop é usado para calcular as contagens para comprimentos de 1 a $ n-1. A contagem para comprimento $i é obtida somando a contagem para comprimento $i-1 da matriz $a e a contagem para comprimento $i-1 da matriz $b. Além disso, a contagem do comprimento $i na matriz $b é obtida a partir da contagem do comprimento $i-1 na matriz $ um. Por fim, o código retorna a soma da contagem do comprimento $n-1 do array $a e a contagem do comprimento $n-1 do array $b, representando a contagem total de strings binárias sem 1's consecutivos. Neste exemplo específico, o código calcula a contagem para um comprimento de 5 e exibe o resultado.

Conclusão

Concluindo, o primeiro método utiliza programação dinâmica, inicializando um array com casos base e calculando iterativamente as contagens para comprimentos maiores. Ele calcula o resultado com eficiência, somando as contagens dos dois comprimentos anteriores. O segundo método emprega uma abordagem mais simples, usando dois arrays para armazenar contagens e atualizando-as iterativamente com base nas contagens do comprimento anterior. Ele calcula diretamente a contagem total sem a necessidade de somar as duas matrizes separadamente. Ambos os métodos fornecem contagens precisas para cadeias binárias sem 1s consecutivos, e a escolha entre eles pode depender de requisitos específicos e de considerações de desempenho.