PHP program to count the number of binary strings that do not contain consecutive 1's

#What is the count of binary strings without consecutive 1's?

Let us consider an example to explain the concept of counting a binary string without consecutive ones.

Example

Suppose we want to count the number of binary strings whose length is 3 and does not contain consecutive 1's. A binary string is a string consisting only of 0s and 1s.

Possible binary strings of length 3 are: 000, 001, 010, 011, 100, 101, 110 and 111.

However, we only need to count those binary strings that do not have consecutive 1's. Therefore, we need to exclude the strings 011, 101, and 111 from the count.

Let’s analyze the remaining binary string:

• 000: This is a valid string because it has no consecutive 1's.

• 001: This is a valid string because it has no consecutive 1's.

• 010: This is a valid string because it has no consecutive 1's.

• 100: This is a valid string because it has no consecutive 1's.

• 110: This is an invalid string because it has consecutive 1's.

As can be seen from the above analysis, there are 4 valid binary strings of length 3, and there are no consecutive 1s.

PHP program counts the number of binary strings without consecutive 1's

Method 1 - Using Dynamic Programming

Example

<?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;

?>

Output

Number of binary strings without consecutive 1's: 13

Code description

This PHP code defines a function called countBinaryStrings that uses dynamic programming to count the number of binary strings of length $n that do not contain consecutive 1's. It initializes the array $dp using the base case $dp[0] = 1 and $dp[1] = 2, indicating that the counts are for length 0 respectively and 1 string. It then uses a loop to fill in the remaining counts of length 2 to $n by summing the counts of length $i - 1 and $. >i - 2. Finally, it returns the count of length $n and prints it. In this particular example, the code counts the number of binary strings of length 5 that do not have consecutive 1's and displays the result.

Method 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) ;

?>

Output

Number of binary strings without consecutive 1's: 13

Code description

This PHP code counts the number of distinct binary strings of length $n that do not contain two consecutive 1's. It defines two arrays, $a and $b, to store the counts. The base case is set to $a[0] = $b[0] = 1. Then, use a loop to calculate lengths 1 to $n-1. The count of length $i is obtained by adding the count of length $i-1 in array $a to the count of length a . >$i-1 comes from array $b. In addition, the count of length $i in array $b is from array $ The count of length $i-1 is obtained by a. Finally, the code returns the count and length of length $n-1 in array $a. The sum of the counts of ##$n-1 comes from the array $b and represents the total number of binary strings without consecutive 1's. In this particular example, the code calculates a count of length 5 and displays the result.

in conclusion

In summary, the first method utilizes dynamic programming, initializing the array with the base case and iteratively calculating counts for larger lengths. It calculates the result efficiently by adding the counts of the first two lengths. The second approach takes a simpler approach, using two arrays to store the counts and iteratively updating them based on the previous length's counts. It calculates the total count directly without having to sum the two arrays separately. Both methods provide accurate counting of binary strings without consecutive ones, and the choice between them may depend on specific requirements and performance considerations.

The above is the detailed content of PHP program to count the number of binary strings that do not contain consecutive 1's. For more information, please follow other related articles on the PHP Chinese website!