计算不含连续1的二进制字符串的数量的PHP程序

没有连续 1 的二进制字符串的计数是多少？

让我们考虑一个例子来解释计算没有连续 1 的二进制字符串的概念。

示例

假设我们要统计长度为 3 且不包含连续 1 的二进制字符串的数量。二进制字符串是仅由 0 和 1 组成的字符串。

长度为 3 的可能二进制字符串为：000、001、010、011、100、101、110 和 111。

但是，我们只需要计算那些没有连续 1 的二进制字符串。因此，我们需要从计数中排除字符串 011、101 和 111。

让我们分析一下剩余的二进制字符串：

• 000：这是一个有效的字符串，因为它没有连续的 1。

• 001：这是一个有效的字符串，因为它没有连续的 1。

• 010：这是一个有效的字符串，因为它没有连续的 1。

• 100：这是一个有效的字符串，因为它没有连续的 1。

• 110：这是一个无效字符串，因为它有连续的 1。

从上面的分析可以看出，有4个长度为3的有效二进制串，且没有连续的1。

PHP 程序计算没有连续 1 的二进制字符串的数量

方法 1 - 使用动态规划

示例

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

?>

输出

Number of binary strings without consecutive 1's: 13

代码说明

此 PHP 代码定义了一个名为 countBinaryStrings 的函数，该函数使用动态编程计算长度为 $n 且不包含连续 1 的二进制字符串的数量。它使用基本情况 $dp[0] = 1 和 $dp[1] = 2 初始化数组 $dp，表示计数分别用于长度为 0 和 1 的字符串。然后，它使用循环通过对长度 $i - 1 和 $ 的计数求和来填充长度 2 到 $n 的剩余计数。 >i - 2. 最后，它返回长度 $n 的计数并打印它。在此特定示例中，代码计算长度为 5 且没有连续 1 的二进制字符串的数量并显示结果。

方法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) ;

?>

输出

Number of binary strings without consecutive 1's: 13

代码说明

此 PHP 代码计算长度为 $n 且不含两个连续 1 的不同二进制字符串的数量。它定义了两个数组，$a 和 $b，来存储计数。基本情况设置为 $a[0] = $b[0] = 1。然后，使用循环计算长度 1 到 $n-1。长度 $i 的计数是通过将数组 $a 中的长度 $i-1 的计数与长度 a 的计数相加获得的。 >$i-1 来自数组 $b.另外，数组$b中长度$i的计数是从数组$中长度$i-1的计数获得的a.最后，代码返回数组 $a 中长度 $n-1 的计数与长度 $n-1 的计数之和来自数组$b，表示没有连续1的二进制字符串的总数。在此特定示例中，代码计算长度为 5 的计数并显示结果。

结论

总之，第一种方法利用动态编程，用基本情况初始化数组并迭代计算较大长度的计数。它通过将前两个长度的计数相加来有效地计算结果。第二种方法采用更简单的方法，使用两个数组来存储计数，并根据先前长度的计数迭代更新它们。它直接计算总计数，无需分别对两个数组求和。这两种方法都为没有连续 1 的二进制字符串提供准确的计数，并且它们之间的选择可能取决于具体要求和性能考虑。

以上是计算不含连续1的二进制字符串的数量的PHP程序的详细内容。更多信息请关注PHP中文网其他相关文章！