没有连续 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 的二进制字符串提供准确的计数，并且它们之间的选择可能取决于具体要求和性能考虑。
