Qu'est-ce que le nombre de chaînes binaires sans les 1 consécutifs ?

Prenons un exemple pour expliquer le concept de comptage de chaînes binaires sans 1 consécutifs.

Exemple

Supposons que nous voulions compter le nombre de chaînes binaires de longueur 3 qui ne contiennent pas de 1 consécutifs. Une chaîne binaire est une chaîne composée uniquement de 0 et de 1.

Les chaînes binaires possibles de longueur 3 sont : 000, 001, 010, 011, 100, 101, 110 et 111.

Cependant, nous devons compter uniquement les chaînes binaires qui n'ont pas de 1 consécutifs. Nous devons donc exclure les chaînes 011, 101 et 111 du décompte.

Analysons les chaînes binaires restantes :

• 000 : il s'agit d'une chaîne valide car elle ne comporte pas de 1 consécutifs.

• 001 : il s'agit d'une chaîne valide car elle ne comporte pas de 1 consécutifs.

• 010 : il s'agit d'une chaîne valide car elle ne comporte pas de 1 consécutifs.

• 100 : il s'agit d'une chaîne valide car elle ne comporte pas de 1 consécutifs.

• 110 : il s'agit d'une chaîne non valide car elle comporte des 1 consécutifs.

D'après l'analyse ci-dessus, nous pouvons voir qu'il existe 4 chaînes binaires valides de longueur 3 sans 1 consécutifs.

Programme PHP pour compter le nombre de chaînes binaires sans 1 consécutifs

Méthode 1 - Utilisation de la programmation dynamique

Exemple

Sortir

Number of binary strings without consecutive 1's: 13

Explication du code

Ce code PHP définit une fonction appelée countBinaryStrings qui calcule le nombre de chaînes binaires de longueur $n sans 1 consécutifs en utilisant la programmation dynamique. Il initialise un tableau $dp avec les cas de base $dp[0] = 1 et $dp[1] = 2, représentant les nombres de chaînes de longueur 0 et 1, respectivement. Il utilise ensuite une boucle pour remplir les comptes restants pour les longueurs 2 à $n, en additionnant les comptes pour les longueurs $i - 1 et $i - 2. Enfin, il renvoie le décompte de la longueur $n et l'imprime. Dans cet exemple spécifique, le code calcule le nombre de chaînes binaires sans 1 consécutifs pour une longueur de 5 et affiche le résultat.

Méthode 2

Sortir

Number of binary strings without consecutive 1's: 13

Explication du code

Ce code PHP calcule le nombre de chaînes binaires distinctes de longueur $n sans deux 1 consécutifs. Il définit deux tableaux, $a et $b, pour stocker les décomptes. Les cas de base sont définis comme $a[0] = $b[0] = 1. Ensuite, une boucle est utilisée pour calculer les comptes pour les longueurs 1 à $ n-1. Le décompte pour la longueur $i est obtenu en additionnant le décompte pour la longueur $i-1 du tableau $a et le décompte pour la longueur $i-1 du tableau $b. De plus, le décompte de la longueur $i dans le tableau $b est obtenu à partir du décompte de la longueur $i-1 dans le tableau $ un. Enfin, le code renvoie la somme du nombre de longueur $n-1 du tableau $a et du nombre de longueur $n-1 du tableau $b, représentant le nombre total de chaînes binaires sans 1 consécutifs. Dans cet exemple particulier, le code calcule le décompte pour une longueur de 5 et affiche le résultat.

Conclusion

En conclusion, la première méthode utilise la programmation dynamique, initialisant un tableau avec des cas de base et calculant de manière itérative les décomptes pour des longueurs plus grandes. Il calcule efficacement le résultat en additionnant les comptes des deux longueurs précédentes. La deuxième méthode utilise une approche plus simple, utilisant deux tableaux pour stocker les décomptes et les mettant à jour de manière itérative en fonction des décomptes de la longueur précédente. Il calcule directement le nombre total sans avoir besoin de additionner les deux tableaux séparément. Les deux méthodes fournissent des décomptes précis pour les chaînes binaires sans 1 consécutifs, et le choix entre elles peut dépendre d'exigences spécifiques et de considérations de performances.