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

Qu'est-ce que le nombre de chaînes binaires sans 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 n'a pas de 1 consécutifs.

• 010 : Il s'agit d'une chaîne valide car elle n'a 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 invalide 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

<?php
function countBinaryStrings($n) {
   $dp = array();
   $dp[0] = 1;
   $dp[1] = 2;

   for ($i = 2; $i <= $n; $i++) {
      $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
   }

   return $dp[$n];
}

$n = 5; // Number of digits in the binary string
$count = countBinaryStrings($n);
echo "Number of binary strings without consecutive 1's: " . $count;

?>

Sortie

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 décomptes pour les 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 compte pour 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

<?php
// PHP program to count all distinct
// binary stringswithout two
// consecutive 1's

function countStrings($n)
{
	$a[$n] = 0;
	$b[$n] = 0;
	$a[0] = $b[0] = 1;
	for ($i = 1; $i < $n; $i++)
	{
		$a[$i] = $a[$i - 1] +
				$b[$i - 1];
		$b[$i] = $a[$i - 1];
	}
	return $a[$n - 1] +
		$b[$n - 1];
}

	// Driver Code
	echo "Number of binary strings without consecutive 1's: " . countStrings(5) ;

?>

Sortie

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 nombre de longueur $i est obtenu en additionnant le nombre de longueur $i-1 du tableau $a et le nombre de 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 $a. 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 des 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.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!