Program PHP untuk Mengira Bilangan Rentetan Perduaan tanpa 1 Berturut-turut

Apakah Bilangan Bilangan Rentetan Binari tanpa 1 Berturut-turut?

Mari kita pertimbangkan contoh untuk menerangkan konsep mengira rentetan binari tanpa 1 berturut-turut.

Contoh

Katakan kita ingin mengira bilangan rentetan binari panjang 3 yang tidak mengandungi 1 berturut-turut. Rentetan binari ialah rentetan yang terdiri daripada hanya 0 dan 1.

Rentetan binari yang mungkin panjang 3 ialah: 000, 001, 010, 011, 100, 101, 110, dan 111.

Walau bagaimanapun, kita perlu mengira hanya rentetan binari yang tidak mempunyai 1 berturut-turut. Jadi, kita perlu mengecualikan rentetan 011, 101, dan 111 daripada kiraan.

Mari kita analisa rentetan binari yang tinggal:

• 000: Ini adalah rentetan yang sah kerana ia tidak mempunyai 1 berturut-turut.

• 001: Ini adalah rentetan yang sah kerana ia tidak mempunyai 1 berturut-turut.

• 010: Ini adalah rentetan yang sah kerana ia tidak mempunyai 1 berturut-turut.

• 100: Ini adalah rentetan yang sah kerana ia tidak mempunyai 1 berturut-turut.

• 110: Ini adalah rentetan yang tidak sah kerana ia mempunyai 1 berturut-turut.

Dari analisis di atas, kita dapat melihat bahawa terdapat 4 rentetan binari yang sah dengan panjang 3 tanpa 1 berturut-turut.

Program PHP untuk Mengira Bilangan Rentetan Perduaan tanpa 1 Berturut-turut

Kaedah 1- Menggunakan Pengaturcaraan Dinamik

Contoh

<?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;

?>

Output

Number of binary strings without consecutive 1's: 13

Penjelasan kod

Kod PHP ini mentakrifkan fungsi yang dipanggil countBinaryStrings yang mengira bilangan rentetan binari panjang $n tanpa 1 berturut-turut menggunakan pengaturcaraan dinamik. Ia memulakan tatasusunan $dp dengan kes asas $dp[0] = 1 dan $dp[1] = 2, masing-masing mewakili kiraan untuk rentetan panjang 0 dan 1. Ia kemudian menggunakan gelung untuk mengisi kiraan yang tinggal untuk panjang 2 hingga $n, dengan menjumlahkan kiraan untuk panjang $i - 1 dan $i - 2. Akhirnya, ia mengembalikan kiraan untuk panjang $ n dan mencetaknya. Dalam contoh khusus ini, kod mengira bilangan rentetan binari tanpa 1 berturut-turut untuk panjang 5 dan memaparkan hasilnya.

Kaedah 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) ;

?>

Output

Number of binary strings without consecutive 1's: 13

Penjelasan kod

Kod PHP ini mengira bilangan rentetan binari yang berbeza dengan panjang $n tanpa dua 1 berturut-turut. Ia mentakrifkan dua tatasusunan, $a dan $b, untuk menyimpan kiraan. Kes asas ditetapkan sebagai $a[0] = $b[0] = 1. Kemudian, gelung digunakan untuk mengira kiraan bagi panjang 1 hingga $n-1. Kiraan untuk panjang $i diperoleh dengan menjumlahkan kiraan untuk panjang $i-1 daripada tatasusunan $a dan kiraan untuk panjang $i-1 daripada tatasusunan $b. Selain itu, kiraan untuk panjang $i dalam tatasusunan $b diperoleh daripada kiraan untuk panjang $i-1 dalam tatasusunan $a. Akhir sekali, kod itu mengembalikan jumlah kiraan untuk panjang $n-1 daripada tatasusunan $a dan kiraan untuk panjang $n-1 daripada tatasusunan $b, mewakili jumlah kiraan rentetan binari tanpa 1 berturut-turut. Dalam contoh khusus ini, kod mengira kiraan untuk panjang 5 dan memaparkan hasilnya.

Kesimpulan

Sebagai kesimpulan, kaedah pertama menggunakan pengaturcaraan dinamik, memulakan tatasusunan dengan kes asas dan secara berulang mengira kiraan untuk panjang yang lebih besar. Ia cekap mengira keputusan dengan menjumlahkan kiraan untuk dua panjang sebelumnya. Kaedah kedua menggunakan pendekatan yang lebih mudah, menggunakan dua tatasusunan untuk menyimpan kiraan dan mengemas kininya secara berulang berdasarkan kiraan dari panjang sebelumnya. Ia secara langsung mengira jumlah kiraan tanpa perlu menjumlahkan dua tatasusunan secara berasingan. Kedua-dua kaedah menyediakan kiraan yang tepat untuk rentetan binari tanpa 1 berturut-turut, dan pilihan antara kaedah tersebut mungkin bergantung pada keperluan khusus dan pertimbangan prestasi.

Atas ialah kandungan terperinci Program PHP untuk Mengira Bilangan Rentetan Perduaan tanpa 1 Berturut-turut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!