PHP-Programm zum Zählen der Anzahl binärer Zeichenfolgen ohne aufeinanderfolgende Einsen

Was ist die Anzahl der Binärzeichenfolgen ohne aufeinanderfolgende Einsen?

Betrachten wir ein Beispiel, um das Konzept des Zählens von Binärzeichenfolgen ohne aufeinanderfolgende Einsen zu erklären.

Beispiel

Angenommen, wir möchten die Anzahl der Binärzeichenfolgen der Länge 3 zählen, die keine aufeinanderfolgenden Einsen enthalten. Eine binäre Zeichenfolge ist eine Zeichenfolge, die nur aus Nullen und Einsen besteht.

Die möglichen Binärzeichenfolgen der Länge 3 sind: 000, 001, 010, 011, 100, 101, 110 und 111.

Wir müssen jedoch nur die Binärzeichenfolgen zählen, die keine aufeinanderfolgenden Einsen haben. Daher müssen wir die Zeichenfolgen 011, 101 und 111 von der Zählung ausschließen.

Lassen Sie uns die verbleibenden Binärzeichenfolgen analysieren:

• 000: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 001: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 010: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 100: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 110: Dies ist eine ungültige Zeichenfolge, da sie aufeinanderfolgende Einsen enthält.

Aus der obigen Analyse können wir erkennen, dass es 4 gültige Binärzeichenfolgen der Länge 3 ohne aufeinanderfolgende Einsen gibt.

PHP-Programm zum Zählen der Anzahl binärer Zeichenfolgen ohne aufeinanderfolgende Einsen

Methode 1 – Dynamische Programmierung verwenden

Beispiel

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

?>

Ausgabe

Number of binary strings without consecutive 1's: 13

Erklärung des Codes

Dieser PHP-Code definiert eine Funktion namens countBinaryStrings, die mithilfe dynamischer Programmierung die Anzahl der Binärzeichenfolgen der Länge $n ohne aufeinanderfolgende Einsen berechnet. Es initialisiert ein Array $dp mit den Basisfällen $dp[0] = 1 und $dp[1] = 2, die die Anzahlen für Zeichenfolgen der Länge 0 bzw. 1 darstellen. Anschließend werden mithilfe einer Schleife die verbleibenden Zählwerte für die Längen 2 bis $n ausgefüllt, indem die Zählwerte für die Längen $i - 1 und $i - 2 summiert werden. Schließlich wird der Zählwert für die Länge $ zurückgegeben n und druckt es aus. In diesem speziellen Beispiel berechnet der Code die Anzahl der Binärzeichenfolgen ohne aufeinanderfolgende Einsen für eine Länge von 5 und zeigt das Ergebnis an.

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

?>

Ausgabe

Number of binary strings without consecutive 1's: 13

Erklärung des Codes

Dieser PHP-Code berechnet die Anzahl unterschiedlicher Binärzeichenfolgen der Länge $n ohne zwei aufeinanderfolgende Einsen. Es definiert zwei Arrays, $a und $b, um die Zählungen zu speichern. Die Basisfälle werden als $a[0] = $b[0] = 1 festgelegt. Anschließend wird eine Schleife verwendet, um die Anzahlen für die Längen 1 bis $n-1 zu berechnen. Die Anzahl für die Länge $i wird durch Summieren der Anzahl für die Länge $i-1 aus dem Array $a und der Anzahl für die Länge $i-1 aus dem Array $b erhalten. Zusätzlich wird die Anzahl für die Länge $i im Array $b aus der Anzahl für die Länge $i-1 im Array $a ermittelt. Schließlich gibt der Code die Summe der Anzahl der Längen $n-1 aus Array $a und der Anzahl der Längen $n-1 aus Array $b zurück, was die Gesamtzahl der Binärzeichenfolgen ohne darstellt aufeinanderfolgende Einsen. In diesem speziellen Beispiel berechnet der Code die Anzahl für eine Länge von 5 und zeigt das Ergebnis an.

Fazit

Zusammenfassend lässt sich sagen, dass die erste Methode dynamische Programmierung nutzt, ein Array mit Basisfällen initialisiert und die Anzahl für größere Längen iterativ berechnet. Das Ergebnis wird effizient berechnet, indem die Anzahl der beiden vorherigen Längen summiert wird. Die zweite Methode verwendet einen einfacheren Ansatz, indem sie zwei Arrays zum Speichern von Zählwerten verwendet und diese basierend auf den Zählwerten der vorherigen Länge iterativ aktualisiert. Die Gesamtzahl wird direkt berechnet, ohne dass die beiden Arrays separat summiert werden müssen. Beide Methoden liefern genaue Zählungen für Binärzeichenfolgen ohne aufeinanderfolgende Einsen, und die Wahl zwischen ihnen kann von spezifischen Anforderungen und Leistungsaspekten abhängen.

Das obige ist der detaillierte Inhalt vonPHP-Programm zum Zählen der Anzahl binärer Zeichenfolgen ohne aufeinanderfolgende Einsen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!