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。

從上面的分析可以看出，有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 和 $i - 的長度計數求和來填充長度 2 到 $n 的剩餘計數。 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 的計數與長度$i-1 來自數組 $b。此外，數組$b 中的長度$i 的計數是從數組$ 中的長度$i-1 的計數獲得的一個。最後，程式碼傳回陣列 $a 中長度 $n-1 的計數和陣列 $n-1 的計數總和。 🎜>$b，表示不連續1的二進位串的總數。在此特定範例中，程式碼計算長度為 5 的計數並顯示結果。 結論

總之，第一種方法利用動態編程，用基本情況初始化數組並迭代計算較大長度的計數。它透過將前兩個長度的計數相加來有效地計算結果。第二種方法採用更簡單的方法，使用兩個陣列來儲存計數，並根據先前長度的計數迭代更新它們。它直接計算總計數，無需分別對兩個數組求和。這兩種方法都為沒有連續 1 的二進位字串提供準確的計數，並且它們之間的選擇可能取決於特定要求和效能考慮。

以上是PHP 程式計算沒有連續 1 的二進位字串的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！