Program PHP untuk mengira bilangan rentetan binari yang tidak mengandungi 1 berturut-turut

Apakah kiraan 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 hanya terdiri daripada 0s dan 1s.

Kemungkinan rentetan binari panjang 3 ialah: 000, 001, 010, 011, 100, 101, 110 dan 111.

Namun, kita hanya perlu mengira rentetan binari yang tidak mempunyai rentetan berturut-turut. Oleh itu, 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 rentetan yang berturutan.

• 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, dan tidak ada 1 berturut-turut.

Program PHP untuk mengira bilangan rentetan binari tanpa 1 berturut-turut

Kaedah 1 - Gunakan 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

Perihalan kod

Kod PHP ini mentakrifkan fungsi yang dipanggil countBinaryStrings yang menggunakan pengaturcaraan dinamik untuk mengira bilangan rentetan binari panjang $n yang tidak mengandungi rentetan berturut-turut. Ia memulakan tatasusunan $dp menggunakan 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 baki kiraan panjang 2 hingga $n dengan menjumlahkan kiraan panjang $i - 1 dan $. >i - 2. Akhirnya, ia mengembalikan kiraan panjang $n dan mencetaknya. Dalam contoh khusus ini, kod mengira bilangan rentetan binari dengan panjang 5 yang tidak mempunyai 1 berturut-turut 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

Perihalan kod

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

Kesimpulan

Ringkasnya, pendekatan pertama menggunakan pengaturcaraan dinamik, memulakan tatasusunan dengan huruf asas dan secara berulang mengira kiraan untuk panjang yang lebih besar. Ia mengira hasil dengan cekap dengan menambah kiraan dua panjang pertama. Pendekatan kedua mengambil pendekatan yang lebih mudah, menggunakan dua tatasusunan untuk menyimpan kiraan dan mengemas kininya secara berulang berdasarkan kiraan panjang sebelumnya. Ia mengira jumlah kiraan secara langsung tanpa perlu menjumlahkan dua tatasusunan secara berasingan. Kedua-dua kaedah menyediakan pengiraan rentetan binari yang tepat tanpa rentetan berturut-turut, dan pilihan antara mereka mungkin bergantung pada keperluan khusus dan pertimbangan prestasi.

Atas ialah kandungan terperinci Program PHP untuk mengira bilangan rentetan binari yang tidak mengandungi 1 berturut-turut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!