연속되는 1 없이 바이너리 문자열의 개수를 계산하는 PHP 프로그램

王林
풀어 주다: 2024-08-28 12:02:03
원래의
199명이 탐색했습니다.

PHP Program to Count Number of Binary Strings without Consecutive 1’s

What is Count Number of Binary Strings without Consecutive 1’s?

Let's consider an example to explain the concept of counting binary strings without consecutive 1's.

Example

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

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

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

Let's analyse the remaining binary strings:

  • 000: This is a valid string because it doesn't have consecutive 1's.

  • 001: This is a valid string because it doesn't have consecutive 1's.

  • 010: This is a valid string because it doesn't have consecutive 1's.

  • 100: This is a valid string because it doesn't have consecutive 1's.

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

From the above analysis, we can see that there are 4 valid binary strings of length 3 without consecutive 1's.

PHP Program to Count 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
로그인 후 복사

Explanation of code

This PHP code defines a function called countBinaryStrings that calculates the number of binary strings of length $n without consecutive 1's using dynamic programming. It initializes an array $dp with the base cases $dp[0] = 1 and $dp[1] = 2, representing the counts for strings of length 0 and 1, respectively. It then uses a loop to fill in the remaining counts for lengths 2 to $n, by summing the counts for lengths $i - 1 and $i - 2. Finally, it returns the count for length $n and prints it. In this specific example, the code calculates the number of binary strings without consecutive 1's for a length of 5 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
로그인 후 복사

Explanation of code

This PHP code calculates the number of distinct binary strings of length $n without two consecutive 1's. It defines two arrays, $a and $b, to store the counts. The base cases are set as $a[0] = $b[0] = 1. Then, a loop is used to calculate the counts for lengths 1 to $n-1. The count for length $i is obtained by summing the count for length $i-1 from array $a and the count for length $i-1 from array $b. Additionally, the count for length $i in array $b is obtained from the count for length $i-1 in array $a. Finally, the code returns the sum of the count for length $n-1 from array $a and the count for length $n-1 from array $b, representing the total count of binary strings without consecutive 1's. In this particular example, the code calculates the count for a length of 5 and displays the result.

Conclusion

In conclusion, the first method utilizes dynamic programming, initializing an array with base cases and iteratively calculating the counts for larger lengths. It efficiently computes the result by summing the counts for the previous two lengths. The second method employs a simpler approach, using two arrays to store counts and iteratively updating them based on the counts from the previous length. It directly calculates the total count without the need for summing the two arrays separately. Both methods provide accurate counts for binary strings without consecutive 1's, and the choice between them may depend on specific requirements and performance considerations.

위 내용은 연속되는 1 없이 바이너리 문자열의 개수를 계산하는 PHP 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
php
원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!