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

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

方法2

雷雷

输出

雷雷

代码解释

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

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