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

什么是不包含连续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。

通过上述分析，我们可以看到长度为3的不包含连续1的有效二进制字符串有4个。

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 stringcount = 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来表示基本情况，dp[0]=1和dp[1]=2分别表示长度为0和1的字符串的个数。然后它使用循环来填充长度为2到n的字符串的个数，通过将长度为i-1和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];
    }
    returna[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的计数和数组 b中长度为 i-1的计数相加得到。另外，数组 b中长度为 i的计数从数组 a中长度为 i-1的计数得到。最后，代码返回数组 a中长度为 n-1的计数和数组 b中长度为 $ n-1的计数之和，表示不包含连续1的二进制串的总计数。在这个特定的例子中，代码计算长度为5的计数，并显示结果。

结论

总之，第一种方法利用动态规划，初始化一个带有基本情况的数组，并迭代计算较长长度的计数。通过将前两个长度的计数求和，它有效地计算结果。第二种方法采用了更简单的方法，使用两个数组来存储计数，并根据前一个长度的计数迭代更新它们。它直接计算总计数，无需单独求和这两个数组。两种方法都能准确计算不包含连续1的二进制串的计数，选择哪种方法可能取决于特定要求和性能考虑。