計算不含連續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中文網其他相關文章！